前言
说起STL中deque，相比是经常使用STL比较熟悉的数据结构。这是一个相对vector或者array等数据结构来说更加复杂。其复杂程度一是其内部元素的存储位置及分配，二是双向队列两头都可以进行操作，这进一步增加deque的复杂度。
deque元素的存储位置
首先可以从deque的迭代器代码入手。参见stl_deque.h文件，发现deque的迭代器与vector迭代器不同，它自己实现了一个_Deque_iterator迭代器，该迭代器中有几个比较重要的成员变量：
typedef _Deque_iterator _Self;
_Tp* _M_cur; //当前元素
_Tp* _M_first; //缓冲区头
_Tp* _M_last; //缓冲区尾
_Map_pointer _M_node; //map节点
iterator中有四个很重要的成员变量，_M_cur指向当前的元素，_M_first指向缓冲区的头部，_M_last指向缓冲区的尾部，_M_node是一个没有见过的变量（表面上看起来像是一个节点，但是一个什么节点呢？），实际上 _M_node 是一个typedef出来的：
typedef _Tp** _Map_pointer
是iterator的默认参数的二级指针，这里就要说到deque的元素存储了。 vector是线性结构，但是deque看似为线性结构，但似乎又不是线性结构，说理就要详细说下了。deque采用的是一种分段存储方式。即在一个deque中，分多个段来存储元素，每个段实际上就是一个缓冲区，有固定的大小。
假如一个deque内有三个缓冲段，每个缓冲段的大小是8，如果deque内的元素个数小于8的时候，每一个缓冲段都可以满足着几个元素的存储，因此这几个元素就会放在一个段内，这样这几个元素看起来就像是线性存储。但是如果deque内的元素大于8，也就说一个缓冲段容不下这么多的元素，那么剩下的元素就会放在第二个、第三个缓冲段内，这样看起来又不是线性存储了。
到这里可能又会出现疑问了，既然deque是分段存取，那么deque又是如何来管理这些缓冲段的呢？这里就是上面说所的一个map变量的二级指针_M_node（注意：这里的map并非STL中的map，而是deque内部段管理的一种方式）。map中的每一个node都指向一个段，由上面可知，每个iterator中都会有一个_M_node，这样不管迭代器指向哪个元素，都可根据_M_node所指向的段找到iterator当前所要返回的元素，具体的可以看下图：
说完了deque的基本结构，再来看看deque的内存管理。deque的构造函数内部调用了_M_fill_initialize函数，构造函数内部又调用了一个全局函数uninitialized_fill生产deque的结构，并将其初始值设置好。这里虽然说已经完成构造了，但是有一个地方不能忽略。由于deque是继承自_Deque_base的，在deque实例化的过程中也会先调用父类的构造函数，父类的构造函数原型：
_Deque_base(const allocator_type& __a, size_t __num_elements)
: _Base(__a), _M_start(), _M_finish()
{
_M_initialize_map(__num_elements);
}
父类的构造函数中调用了_M_initialize_map函数，这个函数实际上就是负责产生并安排好deque的结构，而子类中的_M_fill_initialize函数只是将父类中产生的结构进行初始化而已。
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
size_t __num_nodes = __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
__STL_TRY
{
_M_create_nodes(__nstart, __nfinish);
}
__STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), _M_map = 0, _M_map_size = 0));
_M_start._M_set_node(__nstart);
_M_finish._M_set_node(__nfinish - 1);
_M_start._M_cur = _M_start._M_first;
_M_finish._M_cur = _M_finish._M_first + __num_elements % __deque_buf_size(sizeof(_Tp));
}
首先根据元素大小得到了需要的节点数，然后计算出map的size（即map最多可以管理多少个node），然后invoke _M_allocate_map function 配置具有 _M_map_size 个节点的map，得到了内存块的首地址与尾地址，然后invoke _M_create_nodes 开始分配整个空间（即为每个节点配置缓冲段，所有的缓冲段和map加起来就是完整的deque结构），完成deque结构的生产工作。
deque的运作
接下来分析一下deque中对元素的操作是如何运作的。push_back是向尾端插入一个元素，源代码如下：
void push_back(const value_type& __t)
{
if (_M_finish._M_cur != _M_finish._M_last - 1)
{
construct(_M_finish._M_cur, __t);
++_M_finish._M_cur;
}
else
_M_push_back_aux(__t);
}
如果迭代器所指的当前元素地址不等于缓冲段的最后一个地址时，说明该缓冲段下面还有空间存放要push进去的元素，那么就构造这个元素push进去（construct所做的操作）。如果相等说明该缓冲段已经满了，需要将这个元素放入下一个缓冲段中，那就是_M_push_bak_aux所做的事情：
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY
{
construct(_M_finish._M_cur, __t_copy);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
_M_reserve_map_at_back()函数先不管，往下看。_M_allocate_node()配置了一个缓冲段，然后构造要push进去的元素，接下来_M_set_node改变迭代器finish的指向，使之指向新allocate的缓冲段，然后将当前元素指针指向push进去的元素。push_back的操作就这么做完了，如果是push_front()向deque的前端push一个元素呢？
void push_front(const value_type& __t)
{
if (_M_start._M_cur != _M_start._M_first)
{
construct(_M_start._M_cur - 1, __t);
--_M_start._M_cur;
}
else
_M_push_front_aux(__t);
}
从source code可以看出其流程与push_back差不多，如果start迭代器所指元素的前面还有空间，就把这个元素push在start迭代器的前面，然后start迭代器中的当前元素指针前进一个单位，如果没有空间了就invoke了_M_push_front_aux函数中：
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
value_type __t_copy = __t;
_M_reserve_map_at_front();
*(_M_start._M_node - 1) = _M_allocate_node();
__STL_TRY
{
_M_start._M_set_node(_M_start._M_node - 1);
_M_start._M_cur = _M_start._M_last - 1;
construct(_M_start._M_cur, __t_copy);
}
__STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
}
_M_reserve_map_at_front先不管，同样_M_allocate_node开辟了一个缓冲段，然后让start迭代器指向新开辟的缓冲段的首地址，然后_M_cur 指针指向所要push进元素的位置，然后构造要push进去的位置（将元素push到_M_cur 所指向的位置），就这样push_front的工作完成，it’s ok!
这样，deque的基本运作分析完毕，但是还有一个疑问就是，deque的内部map也是一种数据结构，它也是有大小限制的。当deque中有很多的缓冲段（多到一个map不能完全表达）时候，这个时候就需要扩大map了，如果扩大map呢？这里采用了与vector类似的操作，先开辟一个大空间，然后将旧的map拷贝进去，然后将旧的map空间释放。有两个相关的函数_M_reserve_map_at_back和_M_reserve_map_at_front。
void _M_reserve_map_at_back (size_type __nodes_to_add = 1)
{
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front (size_type __nodes_to_add = 1)
{
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front)
{
size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
//__old_num_nodes map中已有的node，__nodes_to_add 需要add进去的node（即新开辟的缓冲段的个数）
size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (_M_map_size > 2 * __new_num_nodes)
{
__new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < _M_start._M_node)
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
else
copy_backward(_M_start._M_node, _M_finish._M_node + 1,
__new_nstart + __old_num_nodes);
}
else
{
size_type __new_map_size = _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
_Map_pointer __new_map = _M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
_M_deallocate_map(_M_map, _M_map_size);
_M_map = __new_map;
_M_map_size = __new_map_size;
}
_M_start._M_set_node(__new_nstart);
_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
先看_M_reserve_map_at_back，如果满足了if条件就需要更换一个更大的map，就是接下来_M_reallocate_map的工作。这里只说else下面的代码（if里面所做的操作仅仅只是copy而已），map的新size为__new_map_size ，_M_allocate_map接下来开辟了一个map空间，然后将map里的内容拷贝到新的map里面，然后释放旧map。从上面的代码可以看到，在push_back和push_front中都invoke了此函数，实际上_M_reserve_map_at_back 的作用就是在每次插入元素的时候检查当前的map状态，当map不足时就换新的，否则不做操作。
deque元素的操作
在deque里，元素操作除了上面所说的push_back,push_front,还pop_back,pop_front,erase,clear,insert
void pop_back()
{
if (_M_finish._M_cur != _M_finish._M_first)
{
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
_M_pop_back_aux();
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
_M_deallocate_node(_M_finish._M_first);
_M_finish._M_set_node(_M_finish._M_node - 1);
_M_finish._M_cur = _M_finish._M_last - 1;
destroy(_M_finish._M_cur);
}
void pop_front()
{
if (_M_start._M_cur != _M_start._M_last - 1)
{
destroy(_M_start._M_cur);
++_M_start._M_cur;
}
else
_M_pop_front_aux();
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
destroy(_M_start._M_cur);
_M_deallocate_node(_M_start._M_first);
_M_start._M_set_node(_M_start._M_node + 1);
_M_start._M_cur = _M_start._M_first;
}
pop_back，pop_front内部代码比较简单，主要还是_M_pop_back_aux和_M_pop_front_aux这两个函数，先说_M_pop_back_aux函数，当所要pop的元素在某一个缓冲段首地址时，需要检查此时deque是否还有其他的缓冲段和元素所在缓冲段中是否有其他元素，如果有则free了元素之后需要将空的缓冲段也free掉（deque默认无值情况下只留下一个缓冲段），如果只有一个缓冲段就将这个元素free掉，然后更改start和finish迭代器状态（缓冲段不free）。同样，当pop的元素在finsih部分时，也需要做和上面一样的检查操作，这样做的保证了deque在最初的状态、无任何值得情况下都会只有一个缓冲段存在，节省空间，避免产生内存碎片。
clear函数比较简单，就是清除了整个deque中的元素留下一个缓冲段。（具体代码可以参见源代码）
erase函数是清除某一个元素，由于缓冲段内的元素是线性存储，因此在erase了某一个元素之后需要将元素移动，保证缓冲段内元素位置为空的地方要么在finish部分，要么在start部分。（具体代码可以参见源代码） 下面的一段傻逼代码主要就是deque中的常用操作。
void operatorDeque()
{
std::deque<int> de(10,0);
std::cout << "de内值初始化为0："<< endl;
for (int i = 0; i < de.size(); i++)
{
std::cout << de[i] << ",";
}
std::cout << endl;
for (int i = 0; i < de.size(); i++)
{
de[i] = i;
}
std::deque<int>::iterator iter;
iter = de.begin();
de.insert(iter,11);
iter = de.end();
de.insert(iter,22);
std::cout << "输出："<< endl;
for (int i = 0; i < de.size(); i++)
{
std::cout << de[i] << ",";
}
de.pop_back();
de.push_back(33);
de.push_front(44);
iter = find(de.begin(),de.end(),5);
de.erase(iter);
std::cout << "操作之后输出：" << endl;
for (int i = 0; i < de.size(); i++)
{
std::cout << de[i] << ",";
}
de.clear();
std::cout << "清除之后size:" << de.size() << endl;
}