Deque =双端队列

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

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

Deque =双端队列

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

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

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

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

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

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

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

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

一幅图像胜过千言万语。

Deque可以实现为一个固定大小数组的循环缓冲区:

使用循环缓冲区，这样我们就可以通过添加/删除复杂度为O(1)的固定大小的数组在两端增加/缩小 使用固定大小的数组，这样很容易计算索引，因此通过索引访问两个指针解引用-也是O(1)

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