双端队列(deque)的定义有点递归：它内部维护了一个固定大小的双端队列块(chunk)的队列。每个块都是一个向量(vector)，而块的队列(在下面的图中称为“map”)本身也是一个向量。
关于deque的性能特征以及与向量(vector)的比较，这里有一篇很好的分析：CodeProject。
GCC标准库的实现内部使用T**来表示map。每个数据块是一个T*，其分配了一些固定大小的空间__deque_buf_size(取决于sizeof(T))。
vector 不会这样做，但这不是一个难以修改的问题。 - Mark Ransom从概述来看，您可以将deque视为双端队列
deque中的数据是通过固定大小向量块存储的，这些向量块由一个指向map的指针指向（map也是一个向量块，但其大小可能会更改）
deque iterator的主要代码如下：
/*
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
}
deque 的主要部分代码如下：
/*
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;
}
以下是deque的核心代码，主要包括三个部分：
迭代器
如何构造一个deque
__deque_iterator）迭代器的主要问题是，在++、--迭代器时，如果指针指向chunk的边缘，可能会跳到其他chunk。例如，有三个数据块：chunk 1、chunk 2、chunk 3。
pointer1指向chunk 2的开头，当使用运算符--pointer时，它将指向chunk 1的结尾，pointer2也是如此。
下面是__deque_iterator的主要函数：
首先，跳转到任何一个chunk：
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}
chunk_size() 函数计算块大小，您可以认为它在此处简化后返回 8。
operator* 获取块中的数据。reference operator*()const{
return *cur;
}
operator++, --
// 前缀形式的自增/自减运算符
self& 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& 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;
}
self& operator+=(difference_type n){ // n can be postive or negative
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// in the same chunk
cur += 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 + 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& 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);
}
dequedeque 的常见功能
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; ++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<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) + 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 <= 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();
}
假设i_deque有20个int元素0~19，块大小为8，现在将3个元素（0、1、2）推入i_deque：
i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);
它的内部结构如下：
然后再次push_back，它会调用分配新块：
push_back(3)
如果我们使用push_front函数，它会在前一个start块之前分配一个新的块。
注意，当我们使用push_back函数将元素添加到双端队列中时，如果所有的映射和块都已满，则会分配一个新的映射，并调整块。但是以上代码可能已经足够让您理解deque了。
把它想象成向量的向量，但它们不是标准的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的开头或结尾的向量。
(这是我在另一个线程中给出的答案。基本上，我认为即使是相当幼稚的实现，使用单个vector，也符合“常数时间非摊销的push_{front,back}”的要求。你可能会感到惊讶，并认为这是不可能的，但我在标准中发现了其他相关的引用，以令人惊讶的方式定义了上下文。请耐心等待；如果我在这个答案中犯了错误，识别我正确的地方和我的逻辑出了问题将非常有帮助。)
vector<T*>来正确地实现deque<T>。所有元素都被复制到堆上，并将指针存储在向量中。（稍后详细介绍向量。）T*而不是T？因为标准要求：deque :: push_front ，所包含对象（Ts）上的操作数量是固定的，并且与deque中已有对象的数量无关。" vector 增长过大时，其中将进行重新分配并复制许多 T * 。因此， T * 上的操作数量会大幅变化，但 T 上的操作数量不会受到影响。"
"为什么我们要关注计算 T 和计算 T * 之间的这种区别？因为标准规定："
" 本条款中的所有复杂性要求均仅以所包含对象上的操作次数为基础。 "
"对于 deque ，所包含的对象是 T ，而不是 T * ，这意味着我们可以忽略任何复制（或重新分配） T * 的操作。"
我还没有详细讲述一个向量在deque中的行为。也许我们可以将其解释为一个循环缓冲区（向量始终占用其最大容量capacity()，当向量满时，将所有内容重新分配到更大的缓冲区中。细节并不重要。
在过去的几段中，我们分析了deque::push_front以及队列中已有对象的数量与push_front对包含的T对象执行的操作数量之间的关系。我们发现它们彼此独立。由于标准规定复杂度是以对T的操作为单位的，因此我们可以说这具有恒定的复杂度。
是的，Operations-On-T*-Complexity是摊销的（由于vector），但我们只关心Operations-On-T-Complexity，而这是常数（非摊销）的。
在这个实现中，vector::push_back或vector::push_front的复杂度是无关紧要的；这些考虑涉及对T*的操作，因此是无关紧要的。如果标准是指传统的理论复杂度概念，那么它们不会明确限制自己只针对“包含对象上的操作次数”。我是否过于解读了这个句子？
O(n) 意味着操作数量与元素数量渐进成比例关系。也就是说，元操作也要算在内。否则将查询限制为 O(1) 是毫无意义的。因此，链表不符合条件。 - Mooing Ducklist也可以被实现为指针的vector（无论链表大小，插入到中间将导致单个复制构造函数调用，并且指针的O(N)打乱可以忽略，因为它们不是在T上的操作）。 - Mankarsedeque的，而且（2）即使标准允许，在计算算法复杂度时以这种方式“作弊”也无助于编写高效的程序。 - Kyle Strandarray或vector都不能保证平摊复杂度为O(1)的push_front操作。至少两种结构中的内部必须能够具有O(1)的push_front，而array和vector都无法保证这一点。 - Mooing Duck
deque部分，觉得非常不错。 - Rick虽然标准没有规定任何特定的实现方式（只要求常数时间随机访问），但双端队列通常作为一组连续的内存“页面”来实现。需要时会分配新页面，但仍可进行随机访问。与 std::vector 不同，你不能保证数据存储在连续的位置上，但像 vector 一样，在中间插入需要大量重新定位。
insert需要大量的重定位，那么实验4（在此处）如何展示vector::insert()和deque::insert()之间惊人的差异？ - Buladeque 可以实现为固定大小数组的循环缓冲区：