主流的STL容器的数据结构都比较常规，类似List就是实现了链表的数据结构，数据以一个node接连串接一个node的形式存储；vector则是一个连续空间存储的变长数组，当空间用完后则申请一倍的空间并老数据拷贝到新分配空间中；map和set则是红黑树，一种特殊的二叉平衡搜索树，保证根到叶节点最大的层数差距在两倍以内，以此保证搜索的速度和维护树结构的性能平衡；unordered_map和unordered_set则使用哈希表，有不同的哈希函数，也有不同的桶实现方法，在此不予细究；唯独deque的实现略“非主流”，这里详细结合STL中的实现解析一下。

基本原理概述

侯捷的《STL源码剖析》中有详细的理论解析，只是示例代码有点老，在此截图一用： 上图可以明显的看出，deque对于数据的中的存储并不是严格连续的，而是分成了很多个缓冲区，用一个map（并非STL中map，而只是一个简单的连续数组）存储所有缓冲区的地址指针，每个缓冲区都可以存储多个数据，当一个缓冲区填满以后，会开辟新的缓冲区存储数据，并将其地址指针存入map，若map也已经存满以后，会创建新的更大的map，并将旧的map数据拷贝进去并释放旧的空间。

代码分析

下面结合代码来详细看看细节（代码来自gcc5.4自带的STL，stl_deque.h）：

template<typename _Tp, typename _Alloc = std::allocator<_Tp> > class deque : protected _Deque_base<_Tp, _Alloc>

deque继承自_Deque_base类，空间分配器默认为std标准分配器allocator（该版本底层实现为new和delete的封装，而并非一级二级配置器的模式），_Deque_base类主要完成了deque的内存管理相关的任务，拿一些主要的部分来看：

template<typename _Tp, typename _Alloc> class _Deque_base { protected: typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type; //确定_Tp空间分配器类型 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; //alloc_traits会实际调_Tp_alloc_type来分配内存和完成构造和析构操作，这里不详细分析 typedef typename _Alloc_traits::pointer _Ptr; typedef typename _Alloc_traits::const_pointer _Ptr_const; typedef typename _Alloc_traits::template rebind<_Ptr>::other _Map_alloc_type; //确定_Map空间分配器类型 typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits; //同上 ...

以上代码主要用来确定空间分配器类型，之后的接口中会利用以上确定的空间分配器分配空间以及构造对象，再看看主要成员和接口：

struct _Deque_impl : public _Tp_alloc_type { _Map_pointer _M_map; //上文提到的map地址 size_t _M_map_size; //map大小 iterator _M_start; //首元素所在map节点迭代器 iterator _M_finish; //尾后元素所在map节点迭代器 ... } _Deque_impl _M_impl;

实现了一个内置类型，继承自_Tp空间分配器类，定义一个其对象并作为空间分配器，之后所有空间分配任务和构造析构任务都由这个对象完成，同时包含一些重要成员。

_Ptr _M_allocate_node() { typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits; return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp))); } void _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT { typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits; _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp))); }

_Deque_base仅仅只包涵了分配空间和回收的接口，这里只拿了node（上图中的缓冲器）相关的接口，还有map的接口，都大同小异，都是直接调用空间分配起来分配空间。最后提一下_Deque_base的构造中会用到的_M_initialize_map(size_t __num_elements)函数：

template<typename _Tp, typename _Alloc> void _Deque_base<_Tp, _Alloc>:: _M_initialize_map(size_t __num_elements) { const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp)) + 1); //根据初始化元素的个数确定需要的map大小 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size, size_t(__num_nodes + 2)); //根据上面确定map的大小决定（最小为_S_initial_map_size=8） this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size); //分配map的空间 // For "small" maps (needing less than _M_map_size nodes), allocation // starts in the middle elements and grows outwards. So nstart may be // the beginning of _M_map, but for small maps it may be as far in as // _M_map+3. _Map_pointer __nstart = (this->_M_impl._M_map + (this->_M_impl._M_map_size - __num_nodes) / 2); //因为是双端队列map都是从中间开始分配空间，首元素向左生长，尾元素向右，这点比较重要 _Map_pointer __nfinish = __nstart + __num_nodes; //以下给缓冲器分配空间 __try { _M_create_nodes(__nstart, __nfinish); } __catch(...) { _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); this->_M_impl._M_map = _Map_pointer(); this->_M_impl._M_map_size = 0; __throw_exception_again; } //以下就是空间分配完成后初始化_M_impl中各个关键元素，上文已经提过相应意义 this->_M_impl._M_start._M_set_node(__nstart); this->_M_impl._M_finish._M_set_node(__nfinish - 1); this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first; this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first + __num_elements % __deque_buf_size(sizeof(_Tp))); }

到这里_Deque_base的任务基本就完成了，它所有的任务就是提供创建、回收map和node的接口，方便后面的使用。 然后来看看deque的主要实现，主要就是完成元素的插入删除，以插入为例子：

void push_back(const value_type& __x) { if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) { _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish._M_cur, __x); ++this->_M_impl._M_finish._M_cur; } else _M_push_back_aux(__x); }

逻辑还是比较简单的，if判断该缓冲区还有没有空间，有就直接创建对象返回，没有就调用_M_push_back_aux(__x)，看看它的实现：

void deque<_Tp, _Alloc>:: _M_push_back_aux(_Args&&... __args) { _M_reserve_map_at_back(); // 1 *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); // 2 __try { _Alloc_traits::construct(this->_M_impl, // 3 this->_M_impl._M_finish._M_cur, std::forward<_Args>(__args)...); this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1); this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; } __catch(...) { _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); __throw_exception_again; } }

_M_push_back_aux(__x)也并不复杂，因为目前尾元素所在缓冲区空间不够了，因此需要申请新的空间，1、_M_reserve_map_at_back()实现的主要功能就是检查map空间是否足够，不够就申请新的空间，并将数据移动过去，并更新_M_impl中存储关键元素的信息；2、然后根据尾元素所在节点申请新的缓冲区空间；3、最后构造元素。 push_front()基本完全一致，只不过其生长方向与back完全相反，可以简单理解为front和back从初始的中间位置分别向两端生长，一旦所在缓冲区空间不够就申请新的空间，并在新的空间继续生长，最后看下pop_back函数，front类似：

void pop_back() _GLIBCXX_NOEXCEPT { if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first) { --this->_M_impl._M_finish._M_cur; _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish._M_cur); } else _M_pop_back_aux(); }

可以看到，基本就是push_front反过来，if检查当前元素是否到达当前缓冲区最前端，不在则直接pop，否则调用_M_pop_back_aux()，_M_pop_back_aux()与_M_push_back_aux()也是几乎完全相反，需要注意的是它会回收缓冲区内存，其他的这里就不再赘述了。

总结

总体来看，deque由于结构的原因，它整体的实现比vector要复杂很多，缓冲区有点类似于一个每个“节点”都是一个大block的List，只不过它的操作主要在头尾两端，头尾节点一旦空间不够了就新建“节点”，pop空了就删除“节点”，因此如果不想要频繁在头部操作时，选择vector要远远优于deque；但如果有大量头部操作时（例如FIFO）还是老老实实用deque吧。