gcqcc 2017-01-24
deque是double ended queue(即双端队列)的简称。 就像C++中的大部分容器的一样,deque具有以下属性:
容器的顺序性(或序列性)和内存分配器我们留到以后再说,这里我们先来探讨下容器的动态增长需求所带来的动态内存分配性质。
动态内存分配在这里的意思是容器的大小会随着需要而增长,这经常伴随着一些内存需求性的操作而发生(例如insert操作,插入一个元素势必需要为这个元素预留内存空间,不然它会成为一个无处息身的流浪狗-^-)。 每个容器都有其实际上的容量(capacity),当容量耗尽,没有多余的空间时,就需要为这个容器动态地增长(正方形单元表示内存单元,深色表示已使用,白色表示未使用):
之所以称之为动态,是因为这个操作发生在运行时。
这里就涉及到resize factor, 也就是重新分配内存时应该分配的内存大小问题。 分配因子太小很可能会造成后续频繁的内存分配需求,因为当前剩下的内存太少;太大又可能造成内存浪费(尤其是当原内存本身就很大时)。
sgi stl的扩大因子好像是2(即新的内存大小是原内存的2倍),但有研究指出值为1.5的factor在实际中似乎拥有更好的效果。
在实现上,容器内存的动态增长本质上由以下几步完成:
用过C语言的人都知道,C代码中充斥着各种各样的静态内存分配,大部分都以数组的形式出现:
char buffer[1024] = {0};
然而,使用静态内存会带来很多问题:
如果有那么一种机制,让我在调用各种插入、串接操作时都不用考虑这些问题就好了。 不用想了,那就是动态内存分配!! 动态内存分配的重要性对于C++来说,就像是Garbage Collector对于Java那样重要!
好了,言归正传。 实际上,deque想要实现的是一种概念----双端队列。 它是一种LIFO (last in first out)队列,具有以下特性:
双端分别是头端和尾端,在deque类中对应front和back字样。 带有这两个字样的操作,也即成员函数,都是与端口相关的。
至于为什么采用这两个名称,而不采用诸如headPort、tailPort这样的,我猜想是为了保持各个容器接口之间的一致性与简洁性, 便于记忆。 因为有很多容器都具有 第一个 元素和 最后一个 元素这两个通用概念,front和back刚好对应了它们。 同时,front和back也在一定程度上反映了容器的方向与位置信息,适合用来投射概念上的东西(例如双向链表和双端队列)。
入队、出队操作分别为带有push、pop操作,道理与双端概念大致相似,这里不再赘述。
但这两个操作非常重要的一点就是----不管是在头端还是尾端,时间复杂度都是O(1),即常数时间。
理论与实践总是会有不小的距离,容器在实际使用中的易用性有时候更重要。 所以deque类提供的接口远远不止理论上的那几个, 还包括普遍出现在其它容器中的一些接口。 例如Iterator系列、插入、swap、clear等。