什么是STL的双端队列？

Question

什么是STL的双端队列？我正在查看STL容器并试图弄清楚它们到底是什么（即使用的数据结构），而deque阻止了我：我起初认为它是一个双链表，它允许从两端插入和删除恒定时间，但我对运营商[]在恒定时间内做出的承诺感到不安。在链表中，任意访问应该是O（n），对吗？如果它是一个动态数组，它如何在恒定时间内添加元素？应该提到的是，可能会发生重新分配，并且O（1）是一个摊销成本，就像向量一样。所以我想知道这个结构允许在恒定时间内任意访问，同时永远不需要移动到一个新的更大的地方。

Answer 1

deque在某种程度上是递归定义的：在内部它维护一个固定大小的块的双端队列。每个块都是一个向量，块本身的队列（下图中的“map”）也是一个向量。

还有的性能有很大的分析和如何比较的vector超过CodeProject上。

GCC标准库实现在内部使用a T**来表示地图。每个数据块都是一个T*固定大小__deque_buf_size（取决于sizeof(T)）的数据块。

Answer 2

想象它是矢量的矢量。只有他们不是标准std::vector的。

外部向量包含指向内部向量的指针。当通过重新分配改变其容量时，不是将所有空白空间分配到末尾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。

Answer 3

deque =双端队列

一个可以向任一方向生长的容器。

双端队列通常实现为vector的vectors（向量的列表不能给恒定时的随机接入）。虽然辅助向量的大小取决于实现，但常见的算法是使用以字节为单位的常量大小。