blocks|key|2960246|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2960247|+deque+=双端队列|blockquote|2960248|2960249|2960250|一个可以在任意方向生长的容器。|2960251|Deque通常实现为vectors的vector+(向量列表不能提供恒定的时间随机访问)。虽然辅助向量的大小取决于实现，但常见的算法是使用以字节为单位的恒定大小。|offset|length|style|CODE|2960252|entityMap^0|0|0|0|0|0|A|7|I|6|0^^$0|@$1|2|3|-4|4|5|6|P|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|Q|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|R|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|S|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|T|7|@]|8|@]|9|$]]|$1|H|3|I|4|5|6|U|7|@$J|V|K|W|L|M]|$J|X|K|Y|L|M]]|8|@]|9|$]]|$1|N|3|-4|4|5|6|Z|7|@]|8|@]|9|$]]]|O|$]]

<blockquote>
 deque = double ended queue
</blockquote>

A container which can grow in either direction. 

Deque is typically implemented as a <code>vector</code> of <code>vectors</code> (a list of vectors can't give constant time random access). While the size of the secondary vectors is implementation dependent, a common algorithm is to use a constant size in bytes.

blocks|key|3174065|text|deque在某种程度上是递归定义的:在内部，它维护一个固定大小的块的双端队列。每个组块都是一个向量，组块的队列(下图中的“map”)本身也是一个向量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3174066|​|3174067|📷|atomic|offset|length|3174068|3174069|在CodeProject上有很好的性能特征分析，以及它与vector的比较。|style|CODE|3174070|GCC标准库实现在内部使用T**来表示地图。每个数据块都是一个T*，它被分配了一些固定大小的__deque_buf_size+(取决于sizeof(T))。|3174071|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/826a44b2e1ea69e00933800dfcd3763a.png|imageAlt|1|LINK|MUTABLE|url|https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container^0|0|0|0|1|0|0|0|S|6|1|B|1|0|D|3|V|2|1A|G|1V|9|0^^$0|@$1|2|3|4|5|6|7|13|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|14|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|15|8|@]|9|@$G|16|H|17|1|18]]|A|$]]|$1|I|3|C|5|6|7|19|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1A|8|@$G|1B|H|1C|L|M]]|9|@$G|1D|H|1E|1|1F]]|A|$]]|$1|N|3|O|5|6|7|1G|8|@$G|1H|H|1I|L|M]|$G|1J|H|1K|L|M]|$G|1L|H|1M|L|M]|$G|1N|H|1O|L|M]]|9|@]|A|$]]|$1|P|3|-4|5|6|7|1P|8|@]|9|@]|A|$]]]|Q|$R|$5|S|T|U|A|$V|W|X|-4]]|Y|$5|Z|T|10|A|$11|12]]]]

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.
<a href="https://i.stack.imgur.com/SthOW.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SthOW.png" alt="schematic of the memory layout of a deque" /></a>
There’s a great analysis of the performance characteristics and how it compares to the <code>vector</code> over at <a href="https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container" rel="noreferrer">CodeProject</a>.
The GCC standard library implementation internally uses a <code>T**</code> to represent the map. Each data block is a <code>T*</code> which is allocated with some fixed size <code>__deque_buf_size</code> (which depends on <code>sizeof(T)</code>).

blocks|key|2960277|text|虽然该标准没有强制要求任何特定的实现(只有固定时间的随机访问)，但双端队列通常是作为连续内存“页”的集合来实现的。新的页面会根据需要进行分配，但您仍然可以随机访问。与std::vector不同的是，您不能保证数据是连续存储的，但是像向量一样，在中间插入需要进行大量的重新定位。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2960278|entityMap^0|2B|B|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|K|8|@]|D|@]|E|$]]]|G|$]]

While the standard doesn't mandate any particular implementation (only constant-time random access), a deque is usually implemented as a collection of contiguous memory "pages". New pages are allocated as needed, but you still have random access. Unlike <code>std::vector</code>, you're not promised that data is stored contiguously, but like vector, insertions in the middle require lots of relocating.

blocks|key|268862|text|(这是我在another+thread中给出的答案。从本质上讲，我认为即使是相当天真的实现，使用单个vector，也符合“常量非摊销push_{前面，后面}”的要求。你可能会感到惊讶，并认为这是不可能的，但我在标准中找到了以令人惊讶的方式定义上下文的其他相关引用。请容忍我；如果我在这个答案中犯了错误，它将非常有助于识别我所说的哪些事情是正确的，以及我的逻辑在哪里崩溃。)|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|268863|在这个答案中，我并不是试图确定一个好的实现，我只是试图帮助我们解释C%2B%2B标准中的复杂性要求。我引用了N3242，根据Wikipedia的说法，这是最新的可免费获得的C%2B%2B11标准化文档。(它的组织似乎与最终标准不同，因此我不会引用确切的页码。当然，这些规则可能在最终标准中发生了变化，但我认为这并没有发生。)|268864|通过使用vector<T*>，可以正确地实现deque<T>。所有元素都被复制到堆中，指针存储在一个向量中。(稍后将详细介绍向量)。|268865|为什么是T*而不是T？因为标准要求|268866|268867|“在双端插入会使双端的所有迭代器失效，但不会影响对双端元素的引用的有效性。”|blockquote|268868|268869|268870|(我的重点)。T*有助于满足这一要求。它还帮助我们满足这一点：|268871|268872|“在双端队列的开头或结尾插入单个元素总是.....导致对T的构造函数的单个调用。”|268873|268874|268875|现在是(有争议的)一点了。为什么要使用vector来存储T*？它为我们提供了随机访问，这是一个很好的开始。让我们暂时忘掉向量的复杂性，并仔细地构建它：|268876|该标准讨论了“所包含对象上的操作数”。对于deque::push_front，这显然是1，因为只构造了一个T对象，并且以任何方式读取或扫描了零个现有的T对象。这个数字1显然是一个常量，并且独立于当前在双队列中的对象的数量。这使我们可以这样说：|268877|‘对于我们的deque::push_front，包含的对象(+Ts)上的操作数是固定的，并且独立于deque.’中已经存在的对象数。‘|268878|当然，T*上的操作数量将不会表现得那么好。当vector<T*>变得太大时，它将被重新分配，许多T*将被复制。因此，是的，T*上的操作数量会有很大的不同，但T上的操作数量不会受到影响。|268879|为什么我们关心T上的计数操作和T*上的计数操作之间的区别？因为标准是这样说的：|268880|268881|本条款中的所有复杂性要求仅根据对所包含对象的操作次数来说明。|268882|268883|268884|对于deque，包含的对象是T，而不是T*，这意味着我们可以忽略任何复制(或重新分配)+T*的操作。|268885|我没有说太多关于向量在双队列中的行为。也许我们会将其解释为循环缓冲区(向量总是占用其最大capacity()，然后当向量满时将所有内容重新分配到更大的缓冲区中。细节并不重要。|268886|在最后几个段落中，我们已经分析了deque::push_front以及双队列中已经存在的对象数量与push_front在contained+T-objects上执行的操作数量之间的关系。我们发现它们是相互独立的。因为标准要求复杂度是以operations-on-**T**，表示的，所以我们可以说这是一个恒定的复杂度。|BOLD|268887|是的，Operations-On-T*-Complexity是摊销的(由于Operations-On-T-Complexity+)，但我们只对vector感兴趣，而且这是常量(非摊销)。|268888|在这个实现中，vector::push_back或vector::push_front的复杂性是无关紧要的；这些考虑因素涉及T*上的操作，因此是无关紧要的。如果标准是指“传统的”复杂性理论概念，那么他们就不会明确地将自己限制在“对所包含对象的操作数量”上。我是不是过度解读了这句话？|268889|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/8632350/146041|1|http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf|2|http://en.wikipedia.org/wiki/C%252B%252B1x^0|1E|6|5|E|0|0|1E|5|1|1M|9|2|0|4|A|M|8|0|4|2|9|1|0|0|0|0|0|7|2|0|0|0|0|0|J|6|S|2|0|L|H|1H|1|23|1|0|6|H|0|3|2|M|A|1C|2|1P|2|26|1|0|7|1|F|2|0|0|0|0|0|2|5|E|1|J|2|18|2|0|18|A|0|G|H|1Y|1|3P|1|3R|O|0|3|R|11|Q|1Z|6|0|1Q|2|0^^$0|@$1|2|3|4|5|6|7|20|8|@$9|21|A|22|B|C]]|D|@$9|23|A|24|1|25]]|E|$]]|$1|F|3|G|5|6|7|26|8|@]|D|@$9|27|A|28|1|29]|$9|2A|A|2B|1|2C]]|E|$]]|$1|H|3|I|5|6|7|2D|8|@$9|2E|A|2F|B|C]|$9|2G|A|2H|B|C]]|D|@]|E|$]]|$1|J|3|K|5|6|7|2I|8|@$9|2J|A|2K|B|C]|$9|2L|A|2M|B|C]]|D|@]|E|$]]|$1|L|3|-4|5|6|7|2N|8|@]|D|@]|E|$]]|$1|M|3|N|5|O|7|2O|8|@]|D|@]|E|$]]|$1|P|3|-4|5|6|7|2P|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|2Q|8|@]|D|@]|E|$]]|$1|R|3|S|5|6|7|2R|8|@$9|2S|A|2T|B|C]]|D|@]|E|$]]|$1|T|3|-4|5|6|7|2U|8|@]|D|@]|E|$]]|$1|U|3|V|5|O|7|2V|8|@]|D|@]|E|$]]|$1|W|3|-4|5|6|7|2W|8|@]|D|@]|E|$]]|$1|X|3|-4|5|6|7|2X|8|@]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|2Y|8|@$9|2Z|A|30|B|C]|$9|31|A|32|B|C]]|D|@]|E|$]]|$1|10|3|11|5|6|7|33|8|@$9|34|A|35|B|C]|$9|36|A|37|B|C]|$9|38|A|39|B|C]]|D|@]|E|$]]|$1|12|3|13|5|6|7|3A|8|@$9|3B|A|3C|B|C]]|D|@]|E|$]]|$1|14|3|15|5|6|7|3D|8|@$9|3E|A|3F|B|C]|$9|3G|A|3H|B|C]|$9|3I|A|3J|B|C]|$9|3K|A|3L|B|C]|$9|3M|A|3N|B|C]]|D|@]|E|$]]|$1|16|3|17|5|6|7|3O|8|@$9|3P|A|3Q|B|C]|$9|3R|A|3S|B|C]]|D|@]|E|$]]|$1|18|3|-4|5|6|7|3T|8|@]|D|@]|E|$]]|$1|19|3|1A|5|O|7|3U|8|@]|D|@]|E|$]]|$1|1B|3|-4|5|6|7|3V|8|@]|D|@]|E|$]]|$1|1C|3|-4|5|6|7|3W|8|@]|D|@]|E|$]]|$1|1D|3|1E|5|6|7|3X|8|@$9|3Y|A|3Z|B|C]|$9|40|A|41|B|C]|$9|42|A|43|B|C]|$9|44|A|45|B|C]]|D|@]|E|$]]|$1|1F|3|1G|5|6|7|46|8|@$9|47|A|48|B|C]]|D|@]|E|$]]|$1|1H|3|1I|5|6|7|49|8|@$9|4A|A|4B|B|C]|$9|4C|A|4D|B|C]|$9|4E|A|4F|B|C]|$9|4G|A|4H|B|1J]]|D|@]|E|$]]|$1|1K|3|1L|5|6|7|4I|8|@$9|4J|A|4K|B|1J]|$9|4L|A|4M|B|1J]|$9|4N|A|4O|B|C]]|D|@]|E|$]]|$1|1M|3|1N|5|6|7|4P|8|@$9|4Q|A|4R|B|C]]|D|@]|E|$]]|$1|1O|3|-4|5|6|7|4S|8|@]|D|@]|E|$]]]|1P|$1Q|$5|1R|1S|1T|E|$1U|1V]]|1W|$5|1R|1S|1T|E|$1U|1X]]|1Y|$5|1R|1S|1T|E|$1U|1Z]]]]

(This is an answer I've given in <a href="https://stackoverflow.com/a/8632350/146041">another thread</a>. Essentially I'm arguing that even fairly naive implementations, using a single <code>vector</code>, 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. )

In this answer, I am not trying to identify a good implementation, I'm merely trying to help us to interpret the complexity requirements in the C++ standard. I'm quoting from <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf" rel="noreferrer">N3242</a>, which is, according to <a href="http://en.wikipedia.org/wiki/C%2B%2B1x" rel="noreferrer">Wikipedia</a>, the latest freely available C++11 standardization document. (It appears to be organized differently from the final standard, and hence I won't quote the exact page numbers. Of course, these rules might have changed in the final standard, but I don't think that has happened.)

A <code>deque&lt;T&gt;</code> could be implemented correctly by using a <code>vector&lt;T*&gt;</code>. All the elements are copied onto the heap and the pointers stored in a vector. (More on the vector later).

Why <code>T*</code> instead of <code>T</code>? Because the standard requires that

<blockquote>
 "An insertion at either end of the deque invalidates all the iterators
 to the deque, but has no effect on the validity of references to
 elements of the deque."
</blockquote>

(my emphasis). The <code>T*</code> helps to satisfy that. It also helps us to satisfy this:

<blockquote>
 "Inserting a single element either at the beginning or end of a deque always ..... causes a single call to a constructor of T."
</blockquote>

Now for the (controversial) bit. Why use a <code>vector</code> to store the <code>T*</code>? It gives us random access, which is a good start. Let's forget about the complexity of vector for a moment and build up to this carefully:

The standard talks about "the number of operations on the contained objects.". For <code>deque::push_front</code> this is clearly 1 because exactly one <code>T</code> object is constructed and zero of the existing <code>T</code> objects are read or scanned in any way. This number, 1, is clearly a constant and is independent of the number of objects currently in the deque. This allows us to say that:

'For our <code>deque::push_front</code>, the number of operations on the contained objects (the Ts) is fixed and is independent of the number of objects already in the deque.'

Of course, the number of operations on the <code>T*</code> will not be so well-behaved. When the <code>vector&lt;T*&gt;</code> grows too big, it'll be realloced and many <code>T*</code>s will be copied around. So yes, the number of operations on the <code>T*</code> will vary wildly, but the number of operations on <code>T</code> will not be affected.

Why do we care about this distinction between counting operations on <code>T</code> and counting operations on <code>T*</code>? It's because the standard says:

<blockquote>
 All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects.
</blockquote>

For the <code>deque</code>, the contained objects are the <code>T</code>, not the <code>T*</code>, meaning we can ignore any operation which copies (or reallocs) a <code>T*</code>.

I haven't said much about how a vector would behave in a deque. Perhaps we would interpret it as a circular buffer (with the vector always taking up its maximum <code>capacity()</code>, and then realloc everything into a bigger buffer when the vector is full. The details don't matter.

In the last few paragraphs, we have analyzed <code>deque::push_front</code> and the relationship between the number of objects in the deque already and the number of operations performed by push_front on contained <code>T</code>-objects. And we found they were independent of each other. As the standard mandates that complexity is in terms of operations-on-<code>T</code>, then we can say this has constant complexity.

Yes, the Operations-On-T*-Complexity is amortized (due to the <code>vector</code>), but we're only interested in the Operations-On-T-Complexity and this is constant (non-amortized).

The complexity of vector::push_back or vector::push_front is irrelevant in this implementation; those considerations involve operations on <code>T*</code> and hence are irrelevant. If the standard was referring to the 'conventional' theoretical notion of complexity, then they wouldn't have explicitly restricted themselves to the "number of operations on the contained objects". Am I overinterpreting that sentence?

blocks|key|2960383|text|把它想象成一个向量的向量。只是它们不是标准的std::vector。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2960384|外部向量包含指向内部向量的指针。当它的容量通过重新分配而改变时，而不是像std::vector那样将所有的空空间分配到结尾处，它在向量的开始和结尾处将空空间拆分成相等的部分。这允许这个向量上的push_front和push_back都在O(1)时间内发生。|2960385|内部向量的行为需要根据它是在deque的前面还是后面而改变。在后面，它可以表现为一个标准的std::vector，它在结束时增长，而push_back发生在O(1)时间内。在前端，它需要做相反的事情，在开始时随着每个push_front而增长。在实践中，这很容易实现，通过添加一个指针到前面的元素和增长方向以及大小。通过这个简单的修改，push_front也可以是O(1)时间。|2960386|对任何元素的访问都需要偏移和除以O(1)中出现的适当的外部向量索引，并索引到也是O(1)的内部向量。这假设内部向量都是固定大小的，除了位于deque开头或结尾的向量。|2960387|entityMap^0|M|B|0|10|B|2O|A|2Z|9|0|E|5|19|B|1U|9|30|A|4O|A|0|1X|5|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@$9|R|A|S|B|C]|$9|T|A|U|B|C]|$9|V|A|W|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|X|8|@$9|Y|A|Z|B|C]|$9|10|A|11|B|C]|$9|12|A|13|B|C]|$9|14|A|15|B|C]|$9|16|A|17|B|C]]|D|@]|E|$]]|$1|J|3|K|5|6|7|18|8|@$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|L|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]]|M|$]]

Imagine it as a vector of vectors. Only they aren't standard <code>std::vector</code>s.

The outer vector contains pointers to the inner vectors. When its capacity is changed via reallocation, rather than allocating all of the empty space to the end as <code>std::vector</code> does, it splits the empty space to equal parts at the beginning and the end of the vector. This allows <code>push_front</code> and <code>push_back</code> on this vector to both occur in amortized O(1) time.

The inner vector behavior needs to change depending on whether it's at the front or the back of the <code>deque</code>. At the back it can behave as a standard <code>std::vector</code> where it grows at the end, and <code>push_back</code> occurs in O(1) time. At the front it needs to do the opposite, growing at the beginning with each <code>push_front</code>. In practice this is easily achieved by adding a pointer to the front element and the direction of growth along with the size. With this simple modification <code>push_front</code> can also be O(1) time.

Access to any element requires offsetting and dividing to the proper outer vector index which occurs in O(1), and indexing into the inner vector which is also O(1). This assumes that the inner vectors are all fixed size, except for the ones at the beginning or the end of the <code>deque</code>.

blocks|key|3174196|text|我读过Adam+Drozdek的“C%2B%2B中的数据结构和算法”，发现这本书很有用。HTH。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3174197|3174198|+deque的一个非常有趣的方面是它的实现。STL双端队列不是作为链表实现的，而是作为指向数据块或数组的指针数组实现的。块的数量根据存储需求动态变化，指针数组的大小也相应地变化。|blockquote|3174199|3174200|3174201|您可以注意到，中间是指向数据的指针数组(右侧的块)，您还可以注意到，中间的数组是动态变化的。|3174202|一张图片胜过千言万语。|3174203|​|3174204|📷|atomic|offset|length|3174205|3174206|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/a5eac787f7a53d92465e53e32d59c4db.png|imageAlt^0|0|0|0|0|0|0|0|0|0|1|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|13|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|14|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|15|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|16|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|17|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|18|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|19|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|1A|8|@]|9|@$Q|1B|R|1C|1|1D]]|A|$]]|$1|S|3|M|5|6|7|1E|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]]|U|$V|$5|W|X|Y|A|$Z|10|11|-4]]]]

I was reading "Data structures and algorithms in C++" by Adam Drozdek, and found this useful. 
HTH.

<blockquote>
 A very interesting aspect of STL deque is its implementation. An STL deque is not implemented as a linked list but as an array of pointers to blocks or arrays of data. The number of blocks changes dynamically depending on storage needs, and the size of the array of pointers changes accordingly. 
</blockquote>

You can notice in the middle is the array of pointers to the data (chunks on the right), and also you can notice that the array in the middle is dynamically changing. 

An image is worth a thousand words.

<a href="https://i.stack.imgur.com/3mtM6.png" rel="noreferrer"><img src="https://i.stack.imgur.com/3mtM6.png" alt="enter image description here"></a>

blocks|key|2960566|text|从概述中，您可以将deque看作一个double-ended+queue|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2960567|​|2960568|📷|atomic|2960569|2960570|deque中的数据由固定大小的向量块存储，这些向量块是|2960571|由map(也是向量块，但其大小可能会改变)指向|2960572|2960573|2960574|2960575|deque+iterator的主要部分代码如下：|2960576|/*
buff_size+is+the+length+of+the+chunk
*/
template+<class+T,+size_t+buff_size>
struct+__deque_iterator{
++++typedef+__deque_iterator<T,+buff_size>++++++++++++++iterator;
++++typedef+T**+++++++++++++++++++++++++++++++++++++++++map_pointer;

++++//+pointer+to+the+chunk
++++T*+cur;+++++++
++++T*+first;+++++//+the+begin+of+the+chunk
++++T*+last;++++++//+the+end+of+the+chunk

++++//because+the+pointer+may+skip+to+other+chunk
++++//so+this+pointer+to+the+map
++++map_pointer+node;++++//+pointer+to+the+map
}|code-block|syntax|javascript|2960577|deque的主要部分代码如下：|2960578|/*
buff_size+is+the+length+of+the+chunk
*/
template<typename+T,+size_t+buff_size+=+0>
class+deque{
++++public:
++++++++typedef+T++++++++++++++value_type;
++++++++typedef+T&++++++++++++reference;
++++++++typedef+T*++++++++++++pointer;
++++++++typedef+__deque_iterator<T,+buff_size>+iterator;

++++++++typedef+size_t++++++++size_type;
++++++++typedef+ptrdiff_t+++++difference_type;

++++protected:
++++++++typedef+pointer*++++++map_pointer;

++++++++//+allocate+memory+for+the+chunk+
++++++++typedef+allocator<value_type>+dataAllocator;

++++++++//+allocate+memory+for+map+
++++++++typedef+allocator<pointer>++++mapAllocator;

++++private:
++++++++//data+members

++++++++iterator+start;
++++++++iterator+finish;

++++++++map_pointer+map;
++++++++size_type+++map_size;
}|2960579|下面我将给出deque的核心代码，主要分为三个部分：|2960580|用于构建deque的|2960581|iterator|ordered-list-item|2960582|How|2960583|2960584|1.迭代程序(__deque_iterator)|2960585|迭代器的主要问题是，当%2B%2B，--+iterator时，它可能会跳到其他块(如果它指向块的边缘)。例如，有三个数据块：chunk+1、chunk+2和chunk+3。|2960586|pointer1指向chunk+2的开头，当运算符--pointer时，它将指针指向chunk+1的末尾，从而指向pointer2。|2960587|2960588|2960589|2960590|下面我将给出__deque_iterator的主要功能|2960591|首先，跳到任意块：|2960592|void+set_node(map_pointer+new_node){
++++node+=+new_node;
++++first+=+*new_node;
++++last+=+first+%2B+chunk_size();
}|2960593|注意，计算块大小的chunk_size()函数，您可以认为它在这里返回8表示简化。|2960594|operator*获取区块中的数据|2960595|reference+operator*()const{
++++return+*cur;
}|2960596|operator%2B%2B,+--|2960597|//前缀形式的增量|2960598|self&+operator%2B%2B(){
++++%2B%2Bcur;
++++if+(cur+==+last){++++++//if+it+reach+the+end+of+the+chunk
++++++++set_node(node+%2B+1);//skip+to+the+next+chunk
++++++++cur+=+first;
++++}
++++return+*this;
}

//+postfix+forms+of+increment
self+operator%2B%2B(int){
++++self+tmp+=+*this;
++++%2B%2B*this;//invoke+prefix+%2B%2B
++++return+tmp;
}
self&+operator--(){
++++if(cur+==+first){++++++//+if+it+pointer+to+the+begin+of+the+chunk
++++++++set_node(node+-+1);//skip+to+the+prev+chunk
++++++++cur+=+last;
++++}
++++--cur;
++++return+*this;
}

self+operator--(int){
++++self+tmp+=+*this;
++++--*this;
++++return+tmp;
}|2960599|迭代器跳过n步/随机访问|BOLD|2960600|self&+operator%2B=(difference_type+n){+//+n+can+be+postive+or+negative
++++difference_type+offset+=+n+%2B+(cur+-+first);
++++if(offset+>=0+&&+offset+<+difference_type(buffer_size())){
++++++++//+in+the+same+chunk
++++++++cur+%2B=+n;
++++}else{//not+in+the+same+chunk
++++++++difference_type+node_offset;
++++++++if+(offset+>+0){
++++++++++++node_offset+=+offset+/+difference_type(chunk_size());
++++++++}else{
++++++++++++node_offset+=+-((-offset+-+1)+/+difference_type(chunk_size()))+-+1+;
++++++++}
++++++++//+skip+to+the+new+chunk
++++++++set_node(node+%2B+node_offset);
++++++++//+set+new+cur
++++++++cur+=+first+%2B+(offset+-+node_offset+*+chunk_size());
++++}

++++return+*this;
}

//+skip+n+steps
self+operator%2B(difference_type+n)const{
++++self+tmp+=+*this;
++++return+tmp%2B=+n;+//reuse++operator+%2B=
}

self&+operator-=(difference_type+n){
++++return+*this+%2B=+-n;+//reuse+operator+%2B=
}

self+operator-(difference_type+n)const{
++++self+tmp+=+*this;
++++return+tmp+-=+n;+//reuse+operator+%2B=
}

//+random+access+(iterator+can+skip+n+steps)
//+invoke+operator+%2B+,operator+*
reference+operator[](difference_type+n)const{
++++return+*(*this+%2B+n);
}|2960601|2.如何构建deque|2960602|deque的常用功能|2960603|iterator+begin(){return+start;}
iterator+end(){return+finish;}

reference+front(){
++++//invoke+__deque_iterator+operator*
++++//+return+start's+member+*cur
++++return+*start;
}

reference+back(){
++++//+cna't+use+*finish
++++iterator+tmp+=+finish;
++++--tmp;+
++++return+*tmp;+//return+finish's++*cur
}

reference+operator[](size_type+n){
++++//random+access,+use+__deque_iterator+operator[]
++++return+start[n];
}


template<typename+T,+size_t+buff_size>
deque<T,+buff_size>::deque(size_t+n,+const+value_type&+value){
++++fill_initialize(n,+value);
}

template<typename+T,+size_t+buff_size>
void+deque<T,+buff_size>::fill_initialize(size_t+n,+const+value_type&+value){
++++//+allocate+memory+for+map+and+chunk
++++//+initialize+pointer
++++create_map_and_nodes(n);

++++//+initialize+value+for+the+chunks
++++for+(map_pointer+cur+=+start.node;+cur+<+finish.node;+%2B%2Bcur)+{
++++++++initialized_fill_n(*cur,+chunk_size(),+value);
++++}

++++//+the+end+chunk+may+have+space+node,+which+don't+need+have+initialize+value
++++initialized_fill_n(finish.first,+finish.cur+-+finish.first,+value);
}

template<typename+T,+size_t+buff_size>
void+deque<T,+buff_size>::create_map_and_nodes(size_t+num_elements){
++++//+the+needed+map+node+=+(elements+nums+/+chunk+length)+%2B+1
++++size_type+num_nodes+=+num_elements+/+chunk_size()+%2B+1;

++++//+map+node+num。min+num+is++8+，max+num+is+"needed+size+%2B+2"
++++map_size+=+std::max(8,+num_nodes+%2B+2);
++++//+allocate+map+array
++++map+=+mapAllocator::allocate(map_size);

++++//+tmp_start，tmp_finish+poniters+to+the+center+range+of+map
++++map_pointer+tmp_start++=+map+%2B+(map_size+-+num_nodes)+/+2;
++++map_pointer+tmp_finish+=+tmp_start+%2B+num_nodes+-+1;

++++//+allocate+memory+for+the+chunk+pointered+by+map+node
++++for+(map_pointer+cur+=+tmp_start;+cur+<=+tmp_finish;+%2B%2Bcur)+{
++++++++*cur+=+dataAllocator::allocate(chunk_size());
++++}

++++//+set+start+and+end+iterator
++++start.set_node(tmp_start);
++++start.cur+=+start.first;

++++finish.set_node(tmp_finish);
++++finish.cur+=+finish.first+%2B+num_elements+%25+chunk_size();
}|2960604|让我们假设i_deque有20个int元素0~19，它的块大小是8，现在push_back+3个元素(0，1，2)到i_deque|2960605|i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);|2960606|它的内部结构如下：|2960607|2960608|2960609|2960610|然后再次分配新块，它将调用push_back：|2960611|push_back(3)|2960612|2960613|2960614|2960615|如果我们使用push_front，它将在前一个start之前分配新的区块|2960616|2960617|2960618|2960619|注意当push_back元素进入deque时，如果所有的地图和区块都填满了，就会导致分配新的地图，并调整chunks.But上面的代码可能足以让你理解deque。|2960620|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/9105e88704f91a3f4b5f1460e0e2a05e.png|imageAlt|1|https://ask.qcloudimg.com/http-save/yehe-900000/15936752a18bfda7cdf7b06a42dfff58.png|2|https://ask.qcloudimg.com/http-save/yehe-900000/ada4f21057885facb01f1436cf473907.png|3|https://ask.qcloudimg.com/http-save/yehe-900000/b876e7217a90f56a384f6f99239b1207.png|4|https://ask.qcloudimg.com/http-save/yehe-900000/c038b08e4de3a920f2ab9ce08056f282.png|5|https://ask.qcloudimg.com/http-save/yehe-900000/b82273239004d6b0f882f7de1c7bb1b7.png^0|9|5|I|I|0|0|0|1|0|0|0|0|5|0|1|3|0|0|0|1|1|0|0|0|E|0|0|0|5|0|0|6|5|0|4|5|0|0|0|0|7|G|0|1M|7|1U|7|22|7|0|0|8|A|7|P|9|16|7|1L|8|0|0|0|1|2|0|0|6|G|0|0|0|9|C|0|0|9|0|0|0|E|0|0|0|0|C|0|0|6|5|0|0|5|0|0|5|7|L|4|1M|7|0|0|0|0|0|1|3|0|0|0|0|0|0|1|4|0|0|6|A|N|5|0|0|0|1|5|0|0|3|9|23|5|0^^$0|@$1|2|3|4|5|6|7|3L|8|@$9|3M|A|3N|B|C]|$9|3O|A|3P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|3Q|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|3R|8|@]|D|@$9|3S|A|3T|1|3U]]|E|$]]|$1|K|3|G|5|6|7|3V|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|3W|8|@$9|3X|A|3Y|B|C]]|D|@]|E|$]]|$1|N|3|O|5|6|7|3Z|8|@$9|40|A|41|B|C]]|D|@]|E|$]]|$1|P|3|G|5|6|7|42|8|@]|D|@]|E|$]]|$1|Q|3|I|5|J|7|43|8|@]|D|@$9|44|A|45|1|46]]|E|$]]|$1|R|3|G|5|6|7|47|8|@]|D|@]|E|$]]|$1|S|3|T|5|6|7|48|8|@$9|49|A|4A|B|C]]|D|@]|E|$]]|$1|U|3|V|5|W|7|4B|8|@]|D|@]|E|$X|Y]]|$1|Z|3|10|5|6|7|4C|8|@$9|4D|A|4E|B|C]]|D|@]|E|$]]|$1|11|3|12|5|W|7|4F|8|@]|D|@]|E|$X|Y]]|$1|13|3|14|5|6|7|4G|8|@$9|4H|A|4I|B|C]]|D|@]|E|$]]|$1|15|3|16|5|6|7|4J|8|@$9|4K|A|4L|B|C]]|D|@]|E|$]]|$1|17|3|18|5|19|7|4M|8|@]|D|@]|E|$]]|$1|1A|3|1B|5|19|7|4N|8|@]|D|@]|E|$]]|$1|1C|3|-4|5|6|7|4O|8|@]|D|@]|E|$]]|$1|1D|3|1E|5|6|7|4P|8|@$9|4Q|A|4R|B|C]]|D|@]|E|$]]|$1|1F|3|1G|5|6|7|4S|8|@$9|4T|A|4U|B|C]|$9|4V|A|4W|B|C]|$9|4X|A|4Y|B|C]]|D|@]|E|$]]|$1|1H|3|1I|5|6|7|4Z|8|@$9|50|A|51|B|C]|$9|52|A|53|B|C]|$9|54|A|55|B|C]|$9|56|A|57|B|C]|$9|58|A|59|B|C]]|D|@]|E|$]]|$1|1J|3|G|5|6|7|5A|8|@]|D|@]|E|$]]|$1|1K|3|I|5|J|7|5B|8|@]|D|@$9|5C|A|5D|1|5E]]|E|$]]|$1|1L|3|G|5|6|7|5F|8|@]|D|@]|E|$]]|$1|1M|3|1N|5|6|7|5G|8|@$9|5H|A|5I|B|C]]|D|@]|E|$]]|$1|1O|3|1P|5|6|7|5J|8|@]|D|@]|E|$]]|$1|1Q|3|1R|5|W|7|5K|8|@]|D|@]|E|$X|Y]]|$1|1S|3|1T|5|6|7|5L|8|@$9|5M|A|5N|B|C]]|D|@]|E|$]]|$1|1U|3|1V|5|6|7|5O|8|@$9|5P|A|5Q|B|C]]|D|@]|E|$]]|$1|1W|3|1X|5|W|7|5R|8|@]|D|@]|E|$X|Y]]|$1|1Y|3|1Z|5|6|7|5S|8|@$9|5T|A|5U|B|C]]|D|@]|E|$]]|$1|20|3|21|5|6|7|5V|8|@]|D|@]|E|$]]|$1|22|3|23|5|W|7|5W|8|@]|D|@]|E|$X|Y]]|$1|24|3|25|5|6|7|5X|8|@$9|5Y|A|5Z|B|26]]|D|@]|E|$]]|$1|27|3|28|5|W|7|60|8|@]|D|@]|E|$X|Y]]|$1|29|3|2A|5|6|7|61|8|@$9|62|A|63|B|C]]|D|@]|E|$]]|$1|2B|3|2C|5|6|7|64|8|@$9|65|A|66|B|C]]|D|@]|E|$]]|$1|2D|3|2E|5|W|7|67|8|@]|D|@]|E|$X|Y]]|$1|2F|3|2G|5|6|7|68|8|@$9|69|A|6A|B|C]|$9|6B|A|6C|B|C]|$9|6D|A|6E|B|C]]|D|@]|E|$]]|$1|2H|3|2I|5|W|7|6F|8|@]|D|@]|E|$X|Y]]|$1|2J|3|2K|5|6|7|6G|8|@]|D|@]|E|$]]|$1|2L|3|G|5|6|7|6H|8|@]|D|@]|E|$]]|$1|2M|3|I|5|J|7|6I|8|@]|D|@$9|6J|A|6K|1|6L]]|E|$]]|$1|2N|3|G|5|6|7|6M|8|@]|D|@]|E|$]]|$1|2O|3|2P|5|6|7|6N|8|@]|D|@]|E|$]]|$1|2Q|3|2R|5|W|7|6O|8|@]|D|@]|E|$X|Y]]|$1|2S|3|G|5|6|7|6P|8|@]|D|@]|E|$]]|$1|2T|3|I|5|J|7|6Q|8|@]|D|@$9|6R|A|6S|1|6T]]|E|$]]|$1|2U|3|G|5|6|7|6U|8|@]|D|@]|E|$]]|$1|2V|3|2W|5|6|7|6V|8|@$9|6W|A|6X|B|C]|$9|6Y|A|6Z|B|C]]|D|@]|E|$]]|$1|2X|3|G|5|6|7|70|8|@]|D|@]|E|$]]|$1|2Y|3|I|5|J|7|71|8|@]|D|@$9|72|A|73|1|74]]|E|$]]|$1|2Z|3|G|5|6|7|75|8|@]|D|@]|E|$]]|$1|30|3|31|5|6|7|76|8|@$9|77|A|78|B|C]|$9|79|A|7A|B|C]]|D|@]|E|$]]|$1|32|3|-4|5|6|7|7B|8|@]|D|@]|E|$]]]|33|$34|$5|35|36|37|E|$38|39|3A|-4]]|3B|$5|35|36|37|E|$38|3C|3A|-4]]|3D|$5|35|36|37|E|$38|3E|3A|-4]]|3F|$5|35|36|37|E|$38|3G|3A|-4]]|3H|$5|35|36|37|E|$38|3I|3A|-4]]|3J|$5|35|36|37|E|$38|3K|3A|-4]]]]

From overview, you can think <code>deque</code> as a <code>double-ended queue</code>

<a href="https://i.stack.imgur.com/czGx1.png" rel="noreferrer"><img src="https://i.stack.imgur.com/czGx1.png" alt="deque overview"></a>

The datas in <code>deque</code> are stored by chuncks of fixed size vector, which are 

pointered by a <code>map</code>(which is also a chunk of vector, but its size may change)

<a href="https://i.stack.imgur.com/2m7Yk.png" rel="noreferrer"><img src="https://i.stack.imgur.com/2m7Yk.png" alt="deque internal structure"></a>

The main part code of the <code>deque iterator</code> is as below:

<pre><code>/*
buff_size is the length of the chunk
*/
template &lt;class T, size_t buff_size&gt;
struct __deque_iterator{
 typedef __deque_iterator&lt;T, buff_size&gt; iterator;
 typedef T** map_pointer;

 // pointer to the chunk
 T* cur; 
 T* first; // the begin of the chunk
 T* last; // the end of the chunk

 //because the pointer may skip to other chunk
 //so this pointer to the map
 map_pointer node; // pointer to the map
}
</code></pre>

The main part code of the <code>deque</code> is as below:

<pre><code>/*
buff_size is the length of the chunk
*/
template&lt;typename T, size_t buff_size = 0&gt;
class deque{
 public:
 typedef T value_type;
 typedef T&amp; reference;
 typedef T* pointer;
 typedef __deque_iterator&lt;T, buff_size&gt; iterator;

 typedef size_t size_type;
 typedef ptrdiff_t difference_type;

 protected:
 typedef pointer* map_pointer;

 // allocate memory for the chunk 
 typedef allocator&lt;value_type&gt; dataAllocator;

 // allocate memory for map 
 typedef allocator&lt;pointer&gt; mapAllocator;

 private:
 //data members

 iterator start;
 iterator finish;

 map_pointer map;
 size_type map_size;
}
</code></pre>

Below i will give you the core code of <code>deque</code>, mainly about three parts:

<ol>
<li>iterator</li>
<li>How to construct a <code>deque</code></li>
</ol>

<h3>1. iterator(<code>__deque_iterator</code>)</h3>

The main problem of iterator is, when ++, -- iterator, it may skip to other chunk(if it pointer to edge of chunk). For example, there are three data chunks: <code>chunk 1</code>,<code>chunk 2</code>,<code>chunk 3</code>.

The <code>pointer1</code> pointers to the begin of <code>chunk 2</code>, when operator <code>--pointer</code> it will pointer to the end of <code>chunk 1</code>, so as to the <code>pointer2</code>.

<a href="https://i.stack.imgur.com/IgAwE.png" rel="noreferrer"><img src="https://i.stack.imgur.com/IgAwE.png" alt="enter image description here"></a>

Below I will give the main function of <code>__deque_iterator</code>:

Firstly, skip to any chunk:

<pre><code>void set_node(map_pointer new_node){
 node = new_node;
 first = *new_node;
 last = first + chunk_size();
}
</code></pre>

Note that, the <code>chunk_size()</code> function which compute the chunk size, you can think of it returns 8 for simplify here.

<code>operator*</code> get the data in the chunk

<pre><code>reference operator*()const{
 return *cur;
}
</code></pre>

<code>operator++, --</code>

// prefix forms of increment

<pre><code>self&amp; operator++(){
 ++cur;
 if (cur == last){ //if it reach the end of the chunk
 set_node(node + 1);//skip to the next chunk
 cur = first;
 }
 return *this;
}

// postfix forms of increment
self operator++(int){
 self tmp = *this;
 ++*this;//invoke prefix ++
 return tmp;
}
self&amp; operator--(){
 if(cur == first){ // if it pointer to the begin of the chunk
 set_node(node - 1);//skip to the prev chunk
 cur = last;
 }
 --cur;
 return *this;
}

self operator--(int){
 self tmp = *this;
 --*this;
 return tmp;
}
</code></pre>

iterator skip n steps / random access

<pre><code>self&amp; operator+=(difference_type n){ // n can be postive or negative
 difference_type offset = n + (cur - first);
 if(offset &gt;=0 &amp;&amp; offset &lt; difference_type(buffer_size())){
 // in the same chunk
 cur += n;
 }else{//not in the same chunk
 difference_type node_offset;
 if (offset &gt; 0){
 node_offset = offset / difference_type(chunk_size());
 }else{
 node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
 }
 // skip to the new chunk
 set_node(node + node_offset);
 // set new cur
 cur = first + (offset - node_offset * chunk_size());
 }

 return *this;
}

// skip n steps
self operator+(difference_type n)const{
 self tmp = *this;
 return tmp+= n; //reuse operator +=
}

self&amp; operator-=(difference_type n){
 return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
 self tmp = *this;
 return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
 return *(*this + n);
}
</code></pre>

<h3>2. How to construct a <code>deque</code></h3>

common function of <code>deque</code>

<pre><code>iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
 //invoke __deque_iterator operator*
 // return start's member *cur
 return *start;
}

reference back(){
 // cna't use *finish
 iterator tmp = finish;
 --tmp; 
 return *tmp; //return finish's *cur
}

reference operator[](size_type n){
 //random access, use __deque_iterator operator[]
 return start[n];
}


template&lt;typename T, size_t buff_size&gt;
deque&lt;T, buff_size&gt;::deque(size_t n, const value_type&amp; value){
 fill_initialize(n, value);
}

template&lt;typename T, size_t buff_size&gt;
void deque&lt;T, buff_size&gt;::fill_initialize(size_t n, const value_type&amp; value){
 // allocate memory for map and chunk
 // initialize pointer
 create_map_and_nodes(n);

 // initialize value for the chunks
 for (map_pointer cur = start.node; cur &lt; finish.node; ++cur) {
 initialized_fill_n(*cur, chunk_size(), value);
 }

 // the end chunk may have space node, which don't need have initialize value
 initialized_fill_n(finish.first, finish.cur - finish.first, value);
}

template&lt;typename T, size_t buff_size&gt;
void deque&lt;T, buff_size&gt;::create_map_and_nodes(size_t num_elements){
 // the needed map node = (elements nums / chunk length) + 1
 size_type num_nodes = num_elements / chunk_size() + 1;

 // map node num。min num is 8 ，max num is "needed size + 2"
 map_size = std::max(8, num_nodes + 2);
 // allocate map array
 map = mapAllocator::allocate(map_size);

 // tmp_start，tmp_finish poniters to the center range of map
 map_pointer tmp_start = map + (map_size - num_nodes) / 2;
 map_pointer tmp_finish = tmp_start + num_nodes - 1;

 // allocate memory for the chunk pointered by map node
 for (map_pointer cur = tmp_start; cur &lt;= tmp_finish; ++cur) {
 *cur = dataAllocator::allocate(chunk_size());
 }

 // set start and end iterator
 start.set_node(tmp_start);
 start.cur = start.first;

 finish.set_node(tmp_finish);
 finish.cur = finish.first + num_elements % chunk_size();
}
</code></pre>

Let's assume <code>i_deque</code> has 20 int elements <code>0~19</code> whose chunk size is 8, and now push_back 3 elements (0, 1, 2) to <code>i_deque</code>:

<pre><code>i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);
</code></pre>

It's internal structure like below:

<a href="https://i.stack.imgur.com/2HVId.png" rel="noreferrer"><img src="https://i.stack.imgur.com/2HVId.png" alt="enter image description here"></a>

Then push_back again, it will invoke allocate new chunk:

<pre><code>push_back(3)
</code></pre>

<a href="https://i.stack.imgur.com/TP3dj.png" rel="noreferrer"><img src="https://i.stack.imgur.com/TP3dj.png" alt="enter image description here"></a>

If we <code>push_front</code>, it will allocate new chunk before the prev <code>start</code>

<a href="https://i.stack.imgur.com/77Ui4.png" rel="noreferrer"><img src="https://i.stack.imgur.com/77Ui4.png" alt="enter image description here"></a>

Note when <code>push_back</code> element into deque, if all the maps and chunks are filled, it will cause allocate new map, and adjust chunks.But the above code may be enough for you to understand <code>deque</code>.

blocks|key|3174357|text|deque可以实现为固定大小数组的循环缓冲区：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|3174358|3174359|使用循环缓冲区，因此我们可以通过添加/删除复杂度为O(1)的固定大小的数组在两端进行扩展/缩小|unordered-list-item|3174360|使用固定大小的数组，因此很容易计算索引，因此通过索引访问具有两个指针解引用-也就是O(1)|3174361|3174362|entityMap^0|0|5|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|R|8|@]|D|@]|E|$]]|$1|G|3|H|5|I|7|S|8|@]|D|@]|E|$]]|$1|J|3|K|5|I|7|T|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|U|8|@]|D|@]|E|$]]|$1|M|3|-4|5|6|7|V|8|@]|D|@]|E|$]]]|N|$]]

<code>deque</code> could be implemented as a circular buffer of fixed size array:
<ul>
<li>Use circular buffer so we could grow/shrink at both end by adding/removing a fixed sized array with O(1) complexity</li>
<li>Use fixed sized array so it is easy to calculate the index, hence access via index with two pointer dereferences - also O(1)</li>
</ul>

I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the deque stopped me: I thought at first that it was a double linked list, which would allow insertion and deletion from both ends in constant time, but I am troubled by <a href="http://en.cppreference.com/w/cpp/container/deque/operator_at" rel="noreferrer">the promise made</a> by the operator [] to be done in constant time. In a linked list, arbitrary access should be O(n), right?

And if it's a dynamic array, how can it <a href="http://en.cppreference.com/w/cpp/container/deque/push_back" rel="noreferrer">add elements</a> in constant time? It should be mentioned that reallocation may happen, and that O(1) is an amortized cost, <a href="http://en.cppreference.com/w/cpp/container/vector/push_back" rel="noreferrer">like for a vector</a>.

So I wonder what is this structure that allows arbitrary access in constant time, and at the same time never needs to be moved to a new bigger place.

What really is a deque in STL?

数据结构

容器

我看着STL容器，试图弄清楚它们到底是什么(即使用的数据结构)，这让我停住了脚步:我一开始以为它是一个双向链表，它允许在固定时间内从两端插入和删除，但我被操作符[]的在固定时间内完成而困扰。在链表中，任意访问应该是O(n)，对吗？如果它是一个动态数组，它怎么能在固定时间内呢？值得一提的是，可能会发生重新分配，O(1)是...

问什么是STL中的deque？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问什么是STL中的deque？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问什么是STL中的deque？
EN