今天我们来看deque这个数据结构。
我们在C语言的数据结构之中，应该是没有deque这个数据结构的，但是我们肯定有两个数据结构，一个叫做quene（就是所谓的队列），还有一个叫做stack（也就是所谓栈），当然对于我们来说应该是自己写出来的，但是在c++当中他们两个的实现就不一样了，他们采用同一个底层数据结构叫做deque的来进行扩充。
deque这个结构体可以说是list和vector的一个混合结构，所以我们也不能说他是连续空间还是非连续空间。但是起码在应用层（也就是我们看到的这层），他是一个连续空间（因为可以随机跳转）。那么接下来我们就说一下这个deque在源码当中的实现。
一、为什么要用deque
二、Deque是什么
三、Deque的源码实现
四、Deque迭代器的实现
五、deque中包含的各种函数说明和软件架构
六、Deque的优点和缺点
一、为什么要用deque
在C语言中我们有很多的数据结构，比如队列，链表等等。这些大部分都在STL容器当中实现了，但是队列和栈我们始终没有实现。所以deque就出现了。
二、Deque是什么
Deque的用途既包含了数据结构中队列的功能，也包含了栈的功能（因为他是两端都可以插入的），当然我们说list也可以两端插入的，不过list不支持随机读取，但是Deque可以支持随机查找，但是它的插入效率要低于vector（这也好理解，因为判断的东西多了嘛）。
三、deque的源码实现
首先我们来看一下deque的内存模型：
我们来分析一下deque的内存模型。首先deque中包含一个map（注意，这个map不是STL中的map），他是一个指针数组，里面存放了指针，每个指针中指向了一段内存，而这段内存才是真正存放数据的地方。所以，deque当中必须包含两个迭代器指针，分别是start和finish这两个迭代器，每个迭代器中又包含了4个指针，分别是start,finish,current以及size这四个部分。所以，一个空的deque应该是有16个指针的。
这里说一下，对于源码来说，我们使用的时候，比如*iterator这个函数，迭代器会自动把当前数据放到cur当中，非常方便，但是这个要花点时间，因为毕竟函数重载了嘛。
好的，接下来我们说一下deque的源码实现。deque的源码部分我们可以分成三个部分：
一、初始化部分
二、insert部分（包括头部添加，尾部添加，中间添加）
三、删除部分
一、初始化部分
我们首先来看第一部分初始化部分
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);
this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
size_t(__num_nodes + 2));
this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
// 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_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;
}
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)));
}
这里我要说明的部分有两点：
首先是这句话：
this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
size_t(__num_nodes + 2));
这句话指定的是一开始map中节点的个数。我们可以看到，map所用的是初始化节点和我们指定的节点的最大值，而初始化节点大小是8，所以map中节点最少是8，或者是我们指定节点的数字加2，为什么要加2呢？因为头部和尾部各加一个，这样比较方便。
然后这里是第二句话：
_Map_pointer __nstart = (this->_M_impl._M_map
+ (this->_M_impl._M_map_size - __num_nodes) / 2);
这句话指定的是头节点nstart所使用的节点数。我们注意，deque的start不是在开头，而是在中间，为什么要这么设计呢？诚如之间所说，deque本身是两头扩充的，这样做比较方便。
接下来我们来看一下inert的部分
我们以push_back为例：
push_back(bool __x)
{
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
*this->_M_impl._M_finish++ = __x;
else
_M_insert_aux(end(), __x);
}
这个代码比较好理解，就是如果说没到节点的尾端，那么直接插入，否则的话执行_M_insert_aux这个函数
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
value_type __x_copy = __x; // XXX copy
#endif
difference_type __index = __pos - this->_M_impl._M_start;
if (static_cast<size_type>(__index) < size() / 2)
{
push_front(_GLIBCXX_MOVE(front()));
iterator __front1 = this->_M_impl._M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = this->_M_impl._M_start + __index;
iterator __pos1 = __pos;
++__pos1;
_GLIBCXX_MOVE3(__front2, __pos1, __front1);
}
else
{
push_back(_GLIBCXX_MOVE(back()));
iterator __back1 = this->_M_impl._M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = this->_M_impl._M_start + __index;
_GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
}
*__pos = _GLIBCXX_MOVE(__x_copy);
return __pos;
它的这个插入是很有趣的，它可以这样看，首先是对其进行赋值（拷贝一下），然后我们判断是否当前的插入位置在前半段还是后半段，这是为什么呢？我们接着往后看，如果是前半段，那么我们push_front这个函数，然后将他移动到中间。这就明白了吧，这样可以减少移动次数。
四、Deque迭代器的使用
我们这里以operator++举例
_Self&
operator++() _GLIBCXX_NOEXCEPT
{
++_M_cur;
if (_M_cur == _M_last)
{
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
我们看到，如果当前节点不到last的时候M_cur正常++，反之则要跳到下一个节点。我们继续看
void
_M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
{
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
再这里，我们跳入了下一个节点，并且重新将M_first,last重新定义，并且再返回时候将first赋值给了current。
以上就是deque的源码，今天就分享到这了。