什么是deque ?
deque是C++标准模板库（STL）中的一个容器，代表“双端队列”（double-ended queue）。deque支持在其前端（front）和后端（back）进行快速插入和删除操作，并且它在序列的中间插入和删除元素时通常比vector或list更高效。
deque的特点
- 双端插入和删除：你可以在
deque的头部和尾部快速地添加或移除元素，时间复杂度为O(1)。 - 随机访问：与
vector类似，你可以通过索引（即下标）直接访问deque中的任何元素，时间复杂度也为O(1)。 - 动态数组：
deque是一个动态数组，它可以根据需要增长或缩小。 - 内部实现：虽然
deque在外部接口上看起来像一个连续的内存块，但它的内部实现可能不同。它通常是由多个固定大小的内存块组成，这些内存块以某种方式链接在一起，以便在需要时能够动态地分配和释放内存。 - 迭代器稳定性：在
deque的头部或尾部插入或删除元素时，指向容器其它部分的迭代器仍然有效。但是，如果你在中间插入或删除元素，指向这些元素的迭代器可能会失效。
下面我们依旧从stl的六个方面来学习
容器和迭代器
template<class T>
class deque //双端队列
{
protected:
iterator start;
iterator finish;
map_pointer map; //二级指针，指向内存块地址数组的指针
size_t map_size; //内存块的个数吧
};
template<class T,class ref,class pointer,size_t buf_size> buf_size 是内存块的大小
{
T* cur; //尾部迭代器指向元素的pointer
T* first; //当前内存块的起始地址
T* last; //尾部
map_pointer node; //当前迭代器所在的内存块
}
从上面代码我们可以看到在deque中有 begin迭代器，end迭代器，一个二级指针map表示一个指向每块内存块起始地址数组的指针，map_pointer表示内存块的个数
需要注意的是deque是许多非连续连续内存块来实现连续，有点拗口，也就是说它是由多块内存块构成的，内存块内部连续，但内存块之间就不一定连续了 ，如下图所示
内存块和迭代器初始化
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);//这里表示的是需要的内存块,你需要1000个int,每个内存块128则需要9块
this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
size_t(__num_nodes + 2));//默认为8个,+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)));
}这里对头迭代器的初始化很简单
尾迭代器__num_elements % __deque_buf_size(sizeof(_Tp)))是因为1000个元素能装满7个128剩下一个并未装满所以取模
添加数据
deque支持双端插入即，向尾部插入push_back，向头部插入元素push_front
下面以push_back为例子
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);
}这里我们如果如果尾部的当前_M_cur还没到尾内存块的尾部就可以直接插入,否则内存不够_M_push_back_aux(__x)
template<class _Tp,class _Alloc>
void deque<_Tp,Alloc>::M_push_back_aux()
{
_M_reserve_map_at_back(); //向尾部添加一个内存块
*(_M_finish._M_node+1)=_M_allocate_node();
__STL_TRY{ //更新尾部迭代器的当前指向元素，和尾部内存块
construct(_M_finish._M_cur);
_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)));
}然后push_front也类似
如果一直从尾部插入元素会使得前面的内存块导致失衡未被使用、所以在每次插入数据时还有个检测以方便重新分配map，这里我就不再说了大家感兴趣的可以去看看
删除数据
pop_front和pop_back
void pop_back() _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
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();
} void pop_back() _GLIBCXX_NOEXCEPT
这声明了一个不抛出异常的pop_back函数（通过_GLIBCXX_NOEXCEPT宏，它可能是GCC标准库实现中的一个宏，用于指示该函数不会抛出异常）。
if语句判断的是容器是否为空
迭代器的运算
一般我们计算整个deque的大小时都是通过计算头尾迭代器的差值
我们知道迭代器中包含当前的指针，以及当前内存块的头和尾，以及当前内存块
也就是 （尾迭代器内存块-头迭代器内存块）*buf_size+头内存块尾-头迭代器当前元素+尾迭代器当前元素-尾内存块的头 结合上面的图大家可以弄懂
其中源码对迭代器的+，-，-=，++，--，等重载都是基于+=重载实现的，比如++就调用+=1，-=10相当于+=-10
_self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{
const difference_type __offset = __n + (_M_cur - _M_first);
/*计算加完__n之后的偏移量,因为要判断是否越过当前内存块*/
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))//偏移量大于等于0,未越界
_M_cur += __n; //单个内存块内部时连续的可以直接运算
else //偏移量越界
{
const difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
/*计算向先或者向后移动多少个内存块*/
_M_set_node(_M_node + __node_offset); //设置迭代器中内存块的地址
_M_cur = _M_first + (__offset - __node_offset //更新当前指向元素的指针
* difference_type(_S_buffer_size()));
}
return *this;
}大家可以自己仔细琢磨下可以自己画图
分配器
分配和管理相应的内存等其他资源
算法
比如sort，find等算法很简单这里不再展示代码
仿函数
比较仿函数：
std::less<T>：对元素进行小于比较。
std::greater<T>：对元素进行大于比较。
std::equal_to<T>：检查两个元素是否相等。
std::not_equal_to<T>：检查两个元素是否不相等。
适配器
stack,queue的默认适配器都是deque