1. STL序列容器中的deque容器
STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。现在虽说它主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。
STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>
STL提供了很多种容器，每种容器都提供一组操作行为即算法接口。序列容器包括向量（vector）、双端队列（deque）、双向链表（list）。
目录
1. STL序列容器中的deque容器
1.1 deque的基本概念
1.2 deque的特点
1.3 deque的迭代器
1.4 deque的数据结构
1.5 deque的常用API
1.1 deque的基本概念
双端队列（deque）是一种随机访问的数组类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候修改其自身大小，主要完成标准C++数据结构中队列的功能。
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间。
所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
创建一个deque对象，可以通过一些方式：
1) std::deque<type> name;
2) std::deque<type> name(size);
3)std::deque<type> name(size,value);
4) std::deque<type> name(first,last);
1.2 deque的特点
a. deque是由一段一段的定量的连续空间构成，deque是分段连续内存空间。
b. deque的两端都可以进行插入和删除元素操作。
c. deque有自己的迭代器，可以用来遍历容器内的元素。
d. deque也可以动态调整内存空间大小。
注：deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。
1.3 deque的迭代器
deque 容器迭代器的类型为随机访问迭代器，deque 模板类提供了表 1 所示这些成员函数，通过调用这些函数，可以获得表示不同含义的随机访问迭代器。
deque 容器迭代器常用来遍历容器中存储的各个元素。
deque<int> intdeque;
intdeque.push_back(2);
intdeque.push_back(4);
intdeque.push_back(8);
intdeque.push_back(10);
intdeque.push_back(12);
cout << "deque:old" << endl;
deque<int>::iterator deqit;
for (deqit = intdeque.begin(); deqit != intdeque.end(); deqit++)
{
cout << "iterator:" << *deqit << endl;
}
1.4 deque的数据结构
Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。
Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
1.5 deque的常用API
| 函数 | 说明 | | assign(first,last) | 用迭代器first和last所辖范围内的元素替换双端队列元素 | | assign(num,val) | 用val的num个副本替换双端队列元素 | | at（n） | 返回双端队列中第n个元素的值 | | back() | 返回对一个双端队列最后一个元素的引用 | | begin() | 返回指向双端队列中第一个元素的迭代器 | | insert(i,n,x) | 把x的n个副本插入到双端队列中由迭代器i所指明的位置 | | clear() | 删除双端队列中所有元素 | | empty() | 如果双端队列为空，则返回为true值 | | end | 返回指向双端队列中最后一个元素的迭代器 | | erase(i) | 删除迭代器i所指向的双端队列元素 | | front() | 返回对双端队列第一个元素的引用 | | insert(i,start,end) | 把迭代器start和end所管辖范围内的元素插入到双端队列中由迭代器i所指明的位置 | | insert(i,x) | 把值x插入双端队列中由迭代器i所指明的位置 | | max_size | 返回双端队列的最大容量 | | pop_back() | 删除双端队列最后一个元素 | | pop_front() | 删除双端队列第一个元素 | | push_back(x) | 把值x放在双端队列末尾 | | push_front(x) | 把x放到双端队列的开始 | | rbegin | 返回一个反向迭代器，指向双端队列末尾元素之后 | | rend | 返回一个反向迭代器，指向双端队列起始元素 | | size() | 返回双端队列的大小（元素的个数） | | swap(vector) | 交换两个双端队列的内容 | | resize(n,x) | 重新设置双端队列大小n,新元素的值初始化为x |
| 
转播
