STL里面有一个什么东西？
我正在查看STL容器，并试图确定它们究竟是什么（即使用的数据结构），并且deque阻止了我：我首先想到它是一个双链表，它允许从两端插入和删除时间不变，但是我对运营商做出的承诺感到不安， 在链表中，任意访问应该是O（n），对不对？
如果它是一个dynamic数组，它如何在常量时间内添加元素 ？ 应该指出，重新分配可能会发生，而O（1）是摊销成本， 就像一个向量 。
所以我想知道这个结构是什么，它允许在任何时间任意访问，同时也不需要移动到一个新的更大的地方。
一个deque是有些recursion定义的：它在内部维护一个固定大小的块的双端队列（下图中的“块”）。 每个块都是一个向量，块本身的队列（下图中的“地图”）也是一个向量。
有一个很好的性能特点的分析，以及它如何比较CodeProject上的vector 。
GCC标准库实现在内部使用T**来表示地图。 每个数据块是一个T* ，分配一些固定的大小__deque_buf_size （这取决于sizeof(T) ）。
deque =双端队列
一个容器可以在任何方向上生长。
Deque 通常被实现为vector vectors （ vectors列表不能给出恒定的时间随机访问）。 虽然辅助vector的大小是与实现有关的，但常用的algorithm是以字节为单位使用常量大小。
把它想象成vector的vector。 只有他们不是标准的std::vector s。
外部向量包含指向内部向量的指针。 当通过重新分配来改变其容量时，不是像std::vector那样将所有的空白空间分配到结尾，而是将空白空间分割成std::vector的开头和结尾的相等部分。 这允许这个向量上的push_front和push_back同时发生在分摊的O（1）时间。
内部向量行为需要根据是在前端还是后端来改变。 在后面它可以作为一个标准的std::vector在最后增长， push_back在O（1）时间发生。 在前面，它需要做相反的事情，每个push_front开始的时候都在增长。 在实践中，这很容易通过添加指向前端元素的指针和随着大小的增长方向来实现。 有了这个简单的修改， push_front也可以是O（1）次。
访问任何元素需要偏移并划分为O（1）中出现的适当的外部向量索引，并索引到也是O（1）的内部向量中。 这假设内部向量都是固定的大小，除了在deque开头或结尾的那些。
（这是我在另一个线程中给出的答案，本质上我认为，即使是相当天真的实现，使用单个vector ，也符合“常量non-amortized push_ {front，back}”的要求。感到惊讶，认为这是不可能的，但是我在标准中find了另外一个相关的引用，它们以一种令人惊讶的方式定义了上下文，请耐心等待，如果我在这个答案中弄错了，那么识别哪个我已经说得对的事情，以及我的逻辑在哪里崩溃了。）
在这个答案中，我没有试图find一个好的实现，我只是试图帮助我们解释C ++标准中的复杂性要求。 我从N3242引用，这是根据维基百科 ，最新免费提供的C ++ 11标准化文件。 （它看起来与最终的标准有所不同，因此我不会引用确切的页码，当然，这些规则可能已经在最终的标准中有所改变，但我不认为已经发生了。）
一个deque<T>可以通过使用一个vector<T*>正确实现。 所有元素都被复制到堆中，而指针则存储在一个向量中。 （更多关于向量）。
为什么T*而不是T ？ 因为标准要求
“在deque的任一端插入将使所有迭代器无效，但对引用deque元素的有效性没有影响。
（我的重点）。 T*有助于满足这一点。 这也有助于我们满足这一点：
“在一个deque的开始或结尾总是插入一个单独的元素…..只会导致对T的构造函数的一次调用 。
现在争议（争议）位。 为什么使用vector来存储T* ？ 它给了我们随机访问，这是一个好的开始。 让我们暂时忘记vector的复杂性，并仔细地build立起来：
标准谈到“包含对象的操作次数”。 对于deque::push_front这显然是1，因为正好构造了一个T对象，并以任何方式读取或扫描了现有T对象的零。 这个数字1显然是一个常量，并且独立于当前在双端队列中的对象的数量。 这让我们可以这样说：
'对于我们的deque::push_front ，包含对象（Ts）的操作数是固定的，并且与已经在deque中的对象的数量无关。
当然， T*上的操作数量不会那么好。 当vector<T*>增长得太大时，它将被实现，许多T*将被复制。 所以是的， T*上的操作数量会有很大的变化，但T上的操作数量不会受到影响。
为什么我们关心T计数操作和T*计数操作之间的区别呢？ 这是因为标准说：
本条款中的所有复杂性要求仅以包含对象的操作数表示。
对于deque ，包含的对象是T ，而不是T* ，这意味着我们可以忽略任何复制（或重新分配） T* 。
我并没有多说如何一个载体会在一个双层行为。 也许我们会把它解释为一个循环缓冲区（vector总是占用它的最大capacity() ，然后在vector满的时候把所有的东西都重新分配到一个更大的缓冲区中，细节并不重要。
在最后几段中，我们已经分析了deque::push_front和deque已经存在的对象数量与push_front对包含的Tobobject执行的操作次数之间的关系。 我们发现他们是相互独立的。 由于标准要求复杂性是在T ，所以我们可以说这是复杂的。
是的， Operation-On-T *复杂性是摊销的（由于vector ），但是我们只对T上的操作复杂性感兴趣，而且这是不变的（非摊销）。
vector :: push_back或vector :: push_front的复杂性在这个实现中是不相关的; 这些考虑涉及对T*操作，因此是不相关的。 如果标准是指“复杂性”的“传统”理论概念，那么他们就不会明确地将自己限制在“被包含的对象上的操作次数”上。 我是否过度解释这句话？
虽然这个标准没有要求任何特定的实现（只有定时随机访问），但是一个deque通常是作为连续内存“页面”的集合来实现的。 新页面按需分配，但仍然有随机访问权限。 不像std::vector ，你并不是承诺连续存储数据，但是像vector一样，中间的插入需要大量的重定位。
