C++ STL deque容器详解

deque容器是STL中的序列式容器，其具备以下特点：

• 提供一个双向随机访问迭代器，可从列表的两端开始遍历容器
• 可以从队列两端扩充
• 逻辑空间整体连续，物理空间部分连续

 deque容器的逻辑结构是一个可以双向扩充的连续数组结构：

而其物理结构是由多个离散的连续空间组成：

 每一个连续空间称为一个buffer，各个buffer的位置信息（首地址）记录在被称为map的结构中，当deque需要扩充的时候，会新创建一个buffer并将其首地址放入map中，而当map满后，会进行类似vector容器的n倍扩充。

deque提供一个双向随机访问迭代器，该迭代器是一个智能指针。其有四个成员cur、first、last、node。cur指向当前访问的节点，first和last分别指向当前buffer的头和尾。node指向map中表示当前访问buffer的节点：

上图可以看到，使用迭代器模板需要传递四个参数，其中T表示deque中存储的数据类型，BufSiz表示一个buffer容纳的元素个数。deque容器迭代器维护四个成员，皆为指针，大小均为4byte，因此deque容器迭代器的大小为16byte。

deque为了保证访问的连续性，每次访问都会判断是否到了头或尾，如果到了头或尾，则访问下一个时需要借助node。（具体操作由重载的operator++和operator--完成）。

deque的迭代器提供begin()/end()、rbegin()/rend()、cbegin()/cend()、crbegin()/crend()四对函数供开发者使用，具体用法：C++ STL deque容器迭代器用法详解

几乎所有的容器都提供了两个函数，来维护两个迭代器。也就是start（）和finish（），分别是指向头和尾的迭代器。deque也不例外，它的start（）和finish（）指向头尾buffer，其中cur不可更改，分别指向第一个有数据的节点，和最后一个有数据的节点的后一个节点：

上图可以看到，BufSiz默认长度为0，当传入参数为0时，根据值类型所占大小来自动生成buffer大小。deque容器本身维护四个成员，start、finish为迭代器，大小均为16byte，map为指向指针的指针，大小为4byte，map_size为map的实际大小（有多少个buffer)，本质为int类型，大小为4byte，因此deque成员本身大小为40byte。

#include 
#include 
using namespace std;
int main()
{
    dequed{ 1,2,3,4 };
    cout << d[1] << endl;
    //修改指定下标位置处的元素
    d[1] = 5;
    cout << d[1] << endl;
    return 0;
}

运行结果：

2
5

通过下标访问可能发生越界风险，则此时可以使用at()函数来访问，该函数会对越界异常进行捕获。

#include 
#include 
using namespace std;
int main()
{
    dequed{ 1,2,3,4 };
    cout << d.at(1) << endl;
    d.at(1) = 5;
    cout << d.at(1) << endl;
    //下面这条语句会抛出 out_of_range 异常
    //cout << d.at(10) << endl;
    return 0;
}

运行结果：

2
5

deque没有重载operator[]让其访问时检查越界的原因是，如果这样做了，每次访问都要检查是否越界，会产生额外开销，所以提供at()函数让开发者自己选择是否检查。

front()和back()分别返回deque容器中第一个和最后一个元素的引用。

#include 
#include 
using namespace std;
int main()
{
    deque d{ 1,2,3,4,5 };
    cout << "deque 首元素为：" << d.front() << endl;
    cout << "deque 尾元素为：" << d.back() << endl;
    //修改首元素
    d.front() = 10;
    cout << "deque 新的首元素为：" << d.front() << endl;
    //修改尾元素
    d.back() = 20;
    cout << "deque 新的尾元素为：" << d.back() << endl;
    return 0;
}

运行结果：

deque 首元素为：1
deque 尾元素为：5
deque 新的首元素为：10
deque 新的尾元素为：20

deque作为一个有序列表，在插入数据的时候是可能发生数据移动的，而由于deque双向的特性，既可以移动插入点之前的元素，也可以移动插入点之后的元素，到底怎样移动成本会小一些，deque::insert()来完成这项工作：

参考：侯捷 - STL和泛型编程，C++ STL deque容器（详解版）