简介

deque是双端队列，支持快速随机访问。在前后位置插入/删除元素较快，它是vector和array的组合体，等下从结构中就可以看到，其实还应该加上list。string在侯捷老师后面的视频没有具体说明，但是在primer中说它和vector相似，因此结构不会很难。

deque结构

deque

deque的结构设计很巧妙。deque中是以buffer为存储单位，当存储空间不够时，它会增加一个buffer的空间，buffer的大小在旧版中可以指定，后面则默认设置了。上图中的buffer就是可以存储8个int的空间。中间的map其实是一个vector，注意这个vector是用来模拟deque的，意思就是vector的元素不是从头往后放置的，而是从中间到两边放置存储，因此当vector需要扩充时，元素是被copy到中间位置。vector中放置的是指针，该指针指向相应的buffer，这里就有点像list了。

iterator包含了四个指针，其代码如下：

template<class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T** map_pointer;
    typedef __deque_iterator self;
    T* cur;
    T* first;
    T* last;
    map_pointer node;
}

其中cur指向当前元素值，first指向buffer的首元素，finish则指向buffer的尾元素。node类型为指针的指针，指向map即vector容器中的指向buffer的指针。

了解完deque的基本结构，下面看deque中定义的函数。下面是insert函数，在position处插入一个元素其值为x。（注意position是一个位置迭代器）

iterator insert(iterator position, const value_type &x)
{
    if (position.cur == start.cur){ //如果安插点在最前端
        push_front(x);
        return start;
    }
    else if (position.cur == finish.cur){
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp;
    }
    else {
        return insert_aux(position, x);
    }
}

当元素插入位置在最前端或者后端时都可以借助push_front()和push_back()函数来完成。当插入位置在中间时需要借助辅助函数，其操作和vector的insert_aux类似。另外一个比较重要的操作是设置指针值，见下面代码：

//指向指针的指针
void set_node(map_pointer new_node) {
    node = new_node;
    first = *new_node;
    last = first + difference_type(buffer_size());
}

new_node解引用得到一个指针即map中所存的值，该值又指向buffer。last指针只需要在first上移动buffer_size()即可。

最后说一下stack 和 queue的底层容器都可选择list 或 dequeue，但是两者都不允许遍历，也不提供iterator。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。