目录：

1. deque逻辑模型
2. deque底层实现原理
3. deque头文件
4. deque简介
5. deque头文件
6. deque构造函数
7. deque迭代器
8. deque容量等属性
9. deque元素访问、操作

写在前面：

之前已经学过 vector 和 list 这两种序列式容器
deque (double ended queue） 双端队列 也是序列式容器的一种，在其底层结构上还适配出 stack和 queue 这两种适配器，deque 发音为deck /di:k/ 逻辑模型为两端都可以插入删除的数组：

deque逻辑模型（双端队列 两端都可以插入删除）

vector逻辑模型（动态增长的数组 一端进行插入删除）

显而易见的是，双端队列可以在两端进行插入和删除的，这是vector 无法完成的操作，或者是因为其在头插入和删除的复杂度比较高，因此没有设计这样的接口，而双端队列是如何完成这样的 两端进行动态的增长的呢？ 这要从它的底层结构来说：

---

底层原理

因为deque没有所谓的容量capacity这一概念，表面的连续空间也是一个假象。为了维持这个假象由deque的迭代器来将分段连续的空间链接起来，因此要在头或者尾，删除或者插入时，增加一段新的空间并链接起来，这样有点像是链表那样。但又和链表不同，deque的底层由以下几个原理实现：

deque的中控器 ：map(并不是关联式容器map)

deque在表面上看是连续空间，实际上是由一段一段定量的连续空间构成，当在队列的头和尾增加元素需要新的空间的时候，就会分配一段新的定量的空间，串在deque的头和尾上，因此deque的最大的任务就是在这些分段定量的连续空间上，维持整体连续假象的状态。 并且提供了随机访问、存取的操作，为了避免像vector 那样 开辟新空间 拷贝数据复制数据 释放旧空间的繁琐重复操作，底层由复杂的迭代器负责。

既然是分段连续空间，因此肯定需要一个控制器来将这些分段连续的空间组织起来，才能维持空间连续的假象
map 只是一小段的连续空间 ，空间中存储节点指向更大的连续空间称为缓冲区，而dequq的主存储体才是缓冲区：

deque的迭代器

这样就保证了整体的空间连续，但是按照deque可以随机访问，deque的迭代器应该还要具备

1.指出当前缓冲区的位置
2.知道自己是否在当前缓冲区的边缘，当迭代器进行++或者–时发生缓冲区跳跃，到上一个或者下一个缓冲区
3.知道当前元素的位置，访问和操作该元素

因此在deque中的源码设计了以下的一些用于完成这些操作的迭代器

图示：

那么这样就将中控器，迭代器，缓冲区联系起来，即实现了空间连续的假象，也为deque的相关操作提供了可实行的方法。

例如：当我们设置一个缓冲区的大小时32个byte,需要存储20个int型的元素时，一个缓冲区可以存储8个元素，因此需要3个缓冲区来存储，也需要三个节点来将这三个空间链家起来，其中的迭代器如下图所示：

这里可能大家会有疑问，当需要到上一个/下一个缓冲区的话，这里应该如何实现呢？STL源码剖析里也给出了实现的方案：
函数 ： set_node

迭代器：

---

了解了以上的deque的基本原理，接下来介绍以下deque的使用方法：
注意：

deque在序列式容器中比较鸡肋，因为如果只是简单的存储元素，使用vector即可，如果对元素任意位置进 行插入或者删除操作比较多，使用vector即可，所以一般很少去使用deque。deque最大的应用，就是用其 作为标准库中stack和queue的底层结构

一、头文件 <deque>

二、deque简介

说明：

1.deque(发音类似“deck”)，是双端队列不规则的首字母缩写，双端队列是动态大小的序列式容器，其可以像两端进行伸缩
2.特定的库可以以不同的方式实现deque，但通常都是一种动态数组。不论在何种情况下，它都允许通过 随机访问迭代器直接访问单个元素，可以根据需要动态的伸缩。
3.因此，deque提供了一些与vector相似的功能，但deque在头部和尾部进行数据插入和删除操作更加高效。与vector不同的是，deque 不能保证所有的元素存储在连续的空间 中，在deque中通过指针加偏移 量方式访问元素可能会导致非法的操作。
4.vector与list提供了相似的接口，因此其具有类似的用途，但是内部的实现原理不同：vector使用使用了 动态数组，该数组通常需要动态增长；deque中的元素可能分散在不同的存储块中，在deque中保存了 一些必要的信息，通常用来在常数范围内直接访问deque中的任何一个元素，所以deque的内部实现比 vector复杂，但是这些额外信息使得deque在某些情况下增长更加的高效，特别是在序列比较大，重新分 配成本比较高的情况下。
5.除了在频繁在头部或尾部进行插入和删除操作外，deque比list和forward_list的性能更差。

三、构造函数

函数声明	接口说明
deque<T> dq();	构造空的双端队列
deque<T> dq(size_type n, const value_type& val = value_type());	用n个值为val的元素构造双端队列
deque<T>dq(InputIterator first, InputIterator last) ;	用[first, last)的区间构造双端队列
deque<T>dq(const deque& x);	双端队列的拷贝构造函数

例如：

	deque<int> dq;//构造空的deque对象
	deque<int> dq2(5, 10);//用n个value来构造deque对象 当不给值时采用类型的默认值来构造
	deque<int>dq4(dq2.begin(), dq2.end());//采用一段范围内的元素来构造一个deque对象 通常是迭代器范围
	deque<int> dq3(dq2);//拷贝构造函数

四、迭代器

函数声明	接口说明
iterator begin()	返回deque起始位置迭代器
iterator end()	返回deque最后一个元素下一个位置的迭代器
reverse_iterator rbegin()	返回deque起始位置的反向迭代器(即end())
reverse_iterator rend()	返回deque最后一个元素下一个位置的反向迭代器(begin())
const_iterator cbegin()	const
const_iterator cend() const	返回deque最后一个元素下一个位置的const迭代器
const_reverse_iterator crbegin() const	返回deque起始位置的const反向迭代器(即crend())
const_reverse_iterator crend() const	返回deque最后一个元素下一个位置的const反向迭代器 (crbegin())

例如：

	deque<int> deq;
	deq.push_back(1);
	deq.push_back(3);
	deq.push_back(2);
	deq.push_back(6);
	deq.push_back(3);
	deq.push_back(4);
	deque<int>::iterator ite = deq.begin();
	while (ite != deq.end())//普通正向迭代器操作元素
	{
		*ite += 2;//可读可写
		cout << *ite << " ";
		++ite;
	}
	cout << endl;
	deque<int>::reverse_iterator rite = deq.rbegin();//普通反向迭代器操作元素
	while (rite != deq.rend())
	{
		*rite += 3;
		cout << *rite << " ";
		++rite;
	}
	cout << endl;
	deque<int>::const_iterator cite = deq.cbegin();//const正向迭代器
	while (cite != deq.cend())
	{
		//*cite+=1;不允许修改
		cout << *cite << " ";
		++cite;
	}
	cout << endl;
	deque<int>::const_reverse_iterator crite = deq.crbegin();//const反向迭代器
	while (crite != deq.crend())
	{
		cout << *crite << " ";
		++crite;
	}
	cout << endl;

五、容量操作

函数声明	接口说明
size_type size() const	返回deque中有效元素个数
bool empty ( ) const	检测deque是否为空，是返回true，否则返回false
void resize ( size_type sz, T c = T());	将deque中的元素改变到sz，多出的空间用c填

六、deque元素访问操作

函数声明	接口说明
reference operator[] (size_type n)	返回deque中n位置上元素的引用
const_reference operator[] (size_type n) const	返回deque中n位置上元素的const 引用
reference front()	返回deque中首元素的引用
const_reference front() const	返回deque中首元素的const引用
reference back()	返回deque中最后一个元素的引用
const_reference back() const	返回deque中最后一个元素的const引用

七、deque元素的修改操作

函数声明	接口说明
void push_back(const value_type& val)	deque尾部插入元素val
void pop_back()	删除deque尾部元素
void push_front (const value_type& val)	deque头部插入元素val
void pop_front()	删除deque头部元素
iterator insert (iterator position, const value_type& val)	在deque的position位置插入值为val的元素
void insert (iterator position, size_type n, const value_type& val)	在deque的position位置插入n个值为val的元素
void insert (iterator position, InputIterator first, InputIterator last)	在deque的position位置插入[first, last)区间 中的元素
iterator erase (iterator position)	删除deque中position位置的元素，并返回该 位置的下一个位置
iterator erase (iterator first, iterator last)	删除deque中[first, last)区间中的元素，并返 回last位置
void swap (deque& x)	交换两个deque中的内容
void clear()	将deque中的元素清空
iterator emplace (const_iterator position, Args&&… args)	在deque的position位置构造元素，将元素所 需内容通过参数类表传入
void emplace_front (Args&&… args)	在deque的头部构造元素，元素的参数通过参数列表传入
void emplace_back (Args&&… args)	在deque的尾部构造元素，元素的参数通过参 数列表传入

示例：

	deque<int> deq(5, 10);
	deque<int> deq2(3, 2);
	deq.assign(6, 2);//也可以将dequ对象修改成n个  val   和构造时是异曲同工之妙
	deq.assign(deq2.begin(), deq2.end());//使用迭代器位置进行修改deque对象的元素内容
	Print(deq);
	Print(deq2);
	deque<int> deq;
	deq.push_front(1);//头插元素
	deq.push_front(2);
	deque<int>::iterator ite = deq.begin();
	deq.insert(ite+2, 3);//迭代器位置插入元素  支持迭代器位置的++操作
	deq.push_front(3);
	deq.push_front(4);
	deq.pop_front();
	deq.push_back(5);//尾插元素
	deq.push_back(6);
	deq.pop_back();//尾删元素
	cout << deq.back() << " " << deq.front() << endl;
	Print(deq);
	deq.erase(deq.begin());//删除迭代器位置的元素
	deq.erase(deq.begin(), deq.begin() + 1);//删除迭代器位置区间的元素

注意：如果需要对deque中的元素进行排序时最好的方法是，先将deque中的元素复制到vector中进行排序，然后再复制到deque中，因为对deque中的元素进行遍历时是比较麻烦的且代价高，因为其底层空间不连续，导致访问访问起来比较麻烦，因此建议先拷贝出去，排完序再拷贝回去。