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

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

Deque =双端队列

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

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

从总体上看，可以将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。

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

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

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

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