deque

概述

vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空 间。所谓双向开口，意思是可以在头尾两端分别做元素的插人和删除操作，如图所示。vector当然也可以在头尾两端进行操作（从技术观点），但是其头部操作效率奇差，无法被接受。

deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量（capacity)观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。因此，deque没有必要提供所谓的空间保留（reserve)功能。

虽然deque也提供RamdonAccessIterator，但它的迭代器并不是普通指针， 其复杂度和vector不可以道里计，这当然影响了各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。 对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL sort算法），再复制回deque。

中控器

deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。 deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象， 并提供随机存取的接口。避开了 “重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

deque采用一块所谓的map (注意，不是STL的map容器）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node)都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区。

迭代器

deque是分段连续空间。维持其“整体连续”假象的任务，落在了迭代器的operators++和operator–两个运算子身上。

首先，它必须能够指出分段连续空间在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心。

数据结构

deque除了维护一个先前说过的指向m即的指针外,也维护 start, finish 两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，它当然也必须记住目前的map大小。因为一旦map所提供的节点不足，就必须重新配置更大的一块map.

deque的缓冲区扩充操作相当琐碎繁杂，以下将以分解操作的方式一步一步 进行图解说明。程序一开始声明了一个deque:

deque<int,alloc,32> ideq(20,9);

其缓冲区大小为32bytes，并令其保留20个元素空间，每个元素初值为9。

接下来范例程序以下标操作符为每个元素重新设值，然后在尾端插入三个新元素:

for(int i=0； i<ideq.size()； ++i)
	ideq[i] = i；
for(int i=0；i<3;i++)
	ideq-push_back(i)；

由于此时最后一个缓冲区仍有4个备用元素空间，所以不会引起缓冲区的再配置。

现在，如果再新增加一个新元素于尾端：

ideq,push_back(3);

由于尾端只剩一个元素备用空间，于是push_back()调用push_back_aux()，先配置一整块新的缓冲区，再设妥新元素内容，然后更改迭代器 finish 的状态：

接下来范例程序在deque的前端插入一个新元素:

ideq.push_front(99);

该函数一开始即调用reserve_map_at_front()，后者用来判断是否需要扩充map，如有需要就付诸行动。稍后我会呈现reserve_map_at_front()的函数内容。目前的状态不需要重新整治map,所以后继流程便配置了一块新缓冲区，并直接将节点安置于现有的m即上，然后设定新元素，改变迭代器start的状态，如图4-15所示。

接下来范例程序又在deque的最前端插入两个新元素:

ideq,push_front(98);
ideq.push_front(97);

这一次，由于第一缓冲区有备用空间，push_front()可以直接在备用空间上构造新元素，如图4-16所示。

stack

概述

stack是一种先进后出的数据结构。它只有一个出口，stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取stack的其它元素。换言之，stack 不允许有遍历行为。

定义完整列表

以某种既有容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack,是很容易做到的。deque是双向开口的数据结构，若以deque 为底部结构并封闭其头端开口，便轻而易举地形成了一个stack。因此，SGI STL 便以deque作为缺省情况下的stack底部结构，

由于stack系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter (配接器），因此，STL stack往往不被 归类为container (容器），而被归类为container adapter。

stack没有迭代器

stack所有元素的进出都必须符合“先进后出”的条件，只有stack顶端的元素，才有机会被外界取用。stack不提供走访功能，也不提供迭代器.

queue

概述

queue是一种先进先出的数据结构。它有两个出口.queue允许新增元素、移除元素、从最底端加人元素、 取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法 可以存取queue的其它元素。换言之，queue不允许有遍历行为。

定义完整列表

以某种既有容器为底部结构，将其接口改变，使其符合“先进先出”的特性， 形成一个queue，是很容易做到的。deque是双向开口的数据结构，若以deque为 底部结构并封闭其底端的出口和前端的入口，便轻而易举地形成了一个queue。因此，STL便以deque作为缺省情况下的queue底部结构.

由于queue系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter (配接器），因此，STL queue往往不被归类为container (容器），而被归类为container adapter。

queue没有迭代器

queue所有元素的进出都必须符合“先进先出”的条件，只有queue顶端的元素，才有机会被外界取用。queue不提供遍历功能，也不提供迭代器。