一、关于deque

std::deque （ double-ended queue ，双端队列）是有下标顺序容器，它允许在其首尾两端快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。

与 std::vector 相反， deque 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次。

deque 的存储按需自动扩展及收缩。扩张 deque 比扩张 std::vector 更优，因为它不涉及到复制既存元素到新内存位置。另一方面， deque 典型地拥有较大的最小内存开销；只保有一个元素的 deque 必须分配其整个内部数组（例如 64 位 libstdc++ 上为对象大小 8 倍； 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者）。

deque 上常见操作的复杂度（效率）如下：

  • 随机访问——常数 O(1)
  • 在结尾或起始插入或移除元素——常数 O(1)
  • 插入或移除元素——线性 O(n)

二、底层结构

（1）deque迭代器

1
2
3
4
5
6
7
8
9
10
template<class _Tp>
struct _Deque_iterator
{
	typedef _Tp** _Map_pointer;
	
	_Tp* _M_cur;	//当前区块元素地址
	_Tp* _M_first;	//当前区块首元素地址
	_Tp* _M_last;	//当前区块尾元素地址
	_Map_pointer _M_node; //当前区块首地址（二级指针）
};

（2）deque结构

1
2
3
4
5
6
7
8
9
10
template<class _Tp>
class _Deque_base
{
	typedef _Deque_iterator<_Tp> iterator;
protected:
	_Tp** _M_map;			//_Tp* _M_map[];首地址
	size_t _M_map_size;		//_M_map的缓冲区大小
	iterator _M_start;		//标识_M_map的首个内存区块的迭代器
	iterator _M_finish;		//标识_M_map的最后一个内存区块的迭代器
};

（3）内存结构图

在这里插入图片描述

deque内存的增长方式：

  • push_front()，头插元素，若当前区块满，则向上开辟新的区块，改变_M_start迭代器的内容重新标识即可。
  • push_back()，尾插元素，若当前区块满，则向下开辟新的区块，改变_M_finish迭代器的内容重新标识即可。