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

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

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

Deque可以实现为一个固定大小数组的循环缓冲区:

使用循环缓冲区，这样我们就可以通过添加/删除复杂度为O(1)的固定大小的数组在两端增加/缩小 使用固定大小的数组，这样很容易计算索引，因此通过索引访问两个指针解引用-也是O(1)

从总体上看，可以将deque看作双端队列

deque中的数据由固定大小的向量块存储

由一个map(它也是一个向量块，但它的大小可能会改变)指向

deque迭代器的主要部分代码如下:

/*
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

1. 迭代器(__deque_iterator)

迭代器的主要问题是，当++，——iterator时，它可能会跳到其他块(如果它指向块的边缘)。例如，有三个数据块:数据块1、数据块2、数据块3。

pointer1指向数据块2的开始，当operator——pointer它将指向数据块1的结束，从而指向pointer2。

下面我将给出__deque_iterator的主要函数:

首先，跳过任何部分:

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

注意，计算块大小的chunk_size()函数，你可以认为它在这里为简化返回8。

操作符*获取块中的数据

reference operator*()const{
    return *cur;
}

操作符+ +,—

//增量的前缀形式

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;
}

迭代器跳过n步/随机访问

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);
}

2. 如何构造一个deque

deque的通用函数

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，它将调用allocate new chunk:

push_back(3)

如果我们push_front，它将在prev开始之前分配新块

注意当push_back元素进入deque时，如果所有的map和chunk都被填满，会导致分配新的map，并调整chunk。但是上面的代码可能足以让您理解deque。

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

(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*上的操作，因此无关紧要。如果该标准指的是复杂性的“传统”理论概念，那么他们就不会明确地将自己限制在“对所包含对象的操作数量”上。我是不是曲解了这句话?

Deque =双端队列

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

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