(This is an answer I've given in another thread. Essentially I'm arguing that even fairly naive implementations, using a single vector, conform to the requirements of "constant non-amortized push_{front,back}". You might be surprised, and think this is impossible, but I have found other relevant quotes in the standard that define the context in a surprising way. Please bear with me; if I have made a mistake in this answer, it would be very helpful to identify which things I have said correctly and where my logic has broken down. )

在这个回答中，我并不是试图确定一个好的实现，我只是试图帮助我们解释c++标准中的复杂性要求。我引用的是N3242，根据维基百科，这是最新的免费c++ 11标准化文档。(它的组织结构似乎与最终标准不同，因此我不会引用确切的页码。当然，这些规则可能会在最终标准中发生变化，但我不认为这已经发生了。)

deque<T>可以通过使用向量<T*>正确实现。所有元素都复制到堆上，指针存储在一个向量中。(稍后将详细介绍向量)。

为什么是T*而不是T?因为标准要求这样

在deque的任何一端插入都将使所有迭代器失效 到deque，但对引用的有效性没有影响 deque元素。”

(我的重点)。T*有助于满足这一点。它还帮助我们满足以下条件:

在deque的开头或结尾插入单个元素总是.....导致对t的构造函数的单一调用。

现在是(有争议的)部分。为什么用向量来存储T*?它给了我们随机访问的机会，这是一个好的开始。让我们暂时忘记向量的复杂性，仔细考虑一下:

该标准讨论了“对所包含对象的操作次数”。对于deque::push_front，这显然是1，因为只构造了一个T对象，并且以任何方式读取或扫描的现有T对象为零。这个数字1显然是一个常数，与当前deque中对象的数量无关。这允许我们说:

'对于deque::push_front，对包含的对象(t)的操作数量是固定的，与deque中已经存在的对象数量无关。'

当然，T*上的运算次数不会这么规范。当向量<T*>变得太大时，它将被重新分配，许多T*将被复制。所以是的，T*上的操作次数会有很大的变化，但是T上的操作次数不会受到影响。

为什么我们要关心T上的计数运算和T*上的计数运算之间的区别?因为标准上说:

此子句中的所有复杂度要求都仅根据对所包含对象的操作数量来说明。

对于deque，包含的对象是T，而不是T*，这意味着我们可以忽略任何复制(或重新分配)T*的操作。

关于vector在deque中如何表现，我还没有讲太多。也许我们可以将其解释为一个循环缓冲区(向量总是占用其最大容量()，然后当向量满时，将所有内容重新分配到一个更大的缓冲区中。细节不重要。

在前几段中，我们分析了deque::push_front以及deque中已经存在的对象数量与push_front在包含的t对象上执行的操作数量之间的关系。我们发现它们是相互独立的。由于标准要求复杂度是基于对t的操作，那么我们可以说它具有恒定的复杂度。

是的，Operations-On-T*-Complexity是平摊的(由于向量)，但我们只对Operations-On-T-Complexity感兴趣，这是常数(非平摊)。

vector::push_back或vector::push_front的复杂度在此实现中无关紧要;这些考虑涉及T*上的操作，因此无关紧要。如果该标准指的是复杂性的“传统”理论概念，那么他们就不会明确地将自己限制在“对所包含对象的操作数量”上。我是不是曲解了这句话?

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

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

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

一幅图像胜过千言万语。

Deque =双端队列

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

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

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

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

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

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

把它想象成向量的向量。只是它们不是标准的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开始或结束的向量。