Deque =双端队列

可以向任意方向生长的容器。

Deque通常实现为向量的向量(向量列表不能提供常量时间随机访问)。虽然辅助向量的大小取决于实现，但常用的算法是使用以字节为单位的常量大小。

Deque =双端队列

可以向任意方向生长的容器。

Deque通常实现为向量的向量(向量列表不能提供常量时间随机访问)。虽然辅助向量的大小取决于实现，但常用的算法是使用以字节为单位的常量大小。

deque在某种程度上是递归定义的:在内部它维护一个由固定大小的块组成的双端队列。每个块都是一个向量，并且块的队列(下图中的“map”)本身也是一个向量。

在CodeProject中，有一个关于性能特征的很好的分析，以及它如何与矢量进行比较。

GCC标准库实现在内部使用T**来表示映射。每个数据块都是一个T*，它被分配了一个固定大小的__deque_buf_size(取决于sizeof(T))。

我读了Adam Drozdek的《c++中的数据结构和算法》，发现这本书很有用。 HTH。

STL deque的一个非常有趣的方面是它的实现。STL deque不是作为链表实现的，而是作为指向块或数据数组的指针数组实现的。块的数量根据存储需求动态变化，指针数组的大小也相应变化。

您可以注意到中间是指向数据的指针数组(右边的块)，还可以注意到中间的数组是动态变化的。

一幅图像胜过千言万语。

把它想象成向量的向量。只是它们不是标准的std::向量。

外部向量包含指向内部向量的指针。当它的容量通过重新分配而改变时，它不像std::vector那样将所有的空白空间分配到末尾，而是将空白空间在向量的开头和结尾分割成相等的部分。这允许这个向量上的push_front和push_back都在平摊O(1)时间内发生。

内部向量的行为需要根据它是在deque的前面还是后面而改变。在后面，它可以表现为标准的std::vector，它在最后增长，并且push_back在O(1)时间内发生。在前面，它需要做相反的事情，在每个push_front开始时增长。在实践中，这很容易实现，只需添加一个指向前端元素的指针，以及随着大小而增长的方向。通过这个简单的修改，push_front也可以是O(1)时间。

对任何元素的访问都需要偏移和除到O(1)中出现的适当的外部向量索引，并索引到也是O(1)的内部向量。这假设内部向量的大小都是固定的，除了在deque开始或结束的向量。

虽然标准没有强制要求任何特定的实现(只有常量时间随机访问)，但deque通常是作为连续内存“页”的集合实现的。根据需要分配新页面，但您仍然可以随机访问。与std::vector不同的是，你没有保证数据是连续存储的，但是像vector一样，中间的插入需要大量的重新定位。