容器deque(发音为”deck”)和vector非常相似。它也采用动态数组来管理元素，提供随机存取，并有着和vector几乎一模一样的接口。不同的是deque的动态数组头尾都开放，能在头尾两端进行快速安插和删除。
使用deque之前，必须包含头文件<deuqe>
#include <deque>
其中，deque类型是定义于命名空间std内的一个class template：
namespace std {
template <class T, class Allocator = allocator<T>>
class deque;
}
和vector相同，第一个template参数用来表明元素类型——只要是assignable和copyable都可以胜任。第二个template参数可有可无，用来指定内存模型，缺省为allocator。
1.deque的能力
与vector相比，deque功能上的不同处在于：
（1）两端都能快速安插元素和移除元素。这些操作可以在分期摊还的常数时间内完成。
（2）存取元素时，deque的内部结构会多一个间接过程，所以元素的存取和迭代器的动作会稍慢一些。
（3）迭代器需要在不同区块间跳转，所以必须是特殊的智能型指针，非一般指针。
（4）在对内存区块有所限制的系统中，deque可以内含更多元素，因为它使用不止一块内存。因此deque的max_size()可能更大。
（5）deque不支持对容量和内存重分配时机的控制。除了头尾两端，在任何地方安插或删除元素，都将导致指向deque元素的任何pointers,references, iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素，
（6）deque的内存区块不再被使用时，会被释放。
deque的下述特性跟vector差不多：
（1）在中段部分插入、删除元素的速度相对较慢，因为所有元素都需要移动以腾出或填补空间。
（2）迭代器属于random access iterator
如果是以下情形，最好采用deque：
（1）需要在两端插入和移除元素
（2）无需引用容器内的元素
（3）要求容器释放不再使用的元素
2.deque的操作函数
（1）deque的构造函数和析构函数
|
1 2 3 4 5 6 |
deque<Elem> c1 产生一个空的deque deque<Elem> c1(c2) 针对某个deque产生一个同型副本 deque<Elem> c(n) 产生一个deque，含有n个元素，这些元素均以default构造函数产生出来 deque<Elem> c(n,elem) 产生一个deque，含有n个元素，这些元素均是elem的副本 deque<Elem> c(beg,end) 产生一个deque，以区间[beg,end)内的元素为初值 c.~deque<Elem>() 销毁所有元素，释放内存 |
（2）deque的非变动性操作(nonmodifying operations)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
c.size() 返回当前元素数量 c.empty() 判断大小是否为零 c.max_size()返回可容纳的元素最大数量 c1 == c2 如前所诉 c1 != c2 ... c1 < c2 ... c1 > c2 ... c1 <= c2 ... c1 >= c2 ... c.at(idx) 返回索引idx所标示的元素。如果idx越界，抛出out_of_range c[idx] 返回s索引idx所标示的元素，不进行范围检查 c.front() 返回第一个元素。不检查第一个元素是否存在 c.back() 返回最后一个元素。不检查最后一个元素是否存在 c.begin() 返回一个随机存取迭代器，指向第一个元素 c.end() 返回一个随机存取迭代器，指向最后元素的下一个位置 c.rbegin() 返回一个逆向迭代器，指向逆向遍历时的第一个元素 c.rend() 返回一个逆向迭代器，指向逆向迭代的最后一个元素的下一个位置 |
（3）deque的变动性操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
c1 = c2 将c2的所有元素赋值给c1 c.assign(n,elem) 赋值n个elem，赋值给c c.assign(beg,end) 将区间[beg,end)内的元素赋值给c c1.swap(c2) 将c1和c2元素互换 swap(c1,c2) 同上，是个全局函数 c.insert(pos,elem) 在pos位置上插入一个elem副本，并返回新元素位置 c.insert(pos,n,elem) 在pos位置上插入n个elem副本。 c.insert(pos,beg,end) 在pos位置上插入区间[beg,end)内的所有元素的副本。 c.push_back(elem) 在尾部添加一个elem副本 c.pop_back() 移除最后一个元素 c.push_front(elem) 在头部插入elem的一个副本 c.pop_front() 移除最后一个元素 c.erase(pos) 移除pos位置上的元素，返回下一个元素位置 c.erase(beg,end) 移除[beg,end)区间内所有元素，返回下一个元素位置 c.rsize(num) 将元素的数量改为num(如果size()变大了，多出来的新元素都需以default构造函数构造完成) c.rsize(num,elem) 将元素数量改为num(如果size()变大了，多出来的新元素都是elem副本) c.clear() 移除所有元素，将容器清空 |
（4）deque的各项操作只有以下数点和vector不同
1）deque不提供容量操作(capacity()和reserve())。
2）deque直接提供函数，用以完成头部元素的安插和删除(push_front()和pop_front() )。
（5）还有一些值得注意的事情
1）除了at()，没有任何成员函数会检查索引或迭代器是否有效。
2）元素的插入或删除可能导致内存重新分配所以任何插入或删除动作都会使所有指向deque元素的pointers, references和iterators失效。唯一例外是在头部或尾部插入元素，动作之后，pointers和references仍然有效(但iterators就没这么幸运了)。
3.异常处理(Exception Handling)
原则上deque提供的异常处理和vector提供的一样。新增的操作函数push_front()和pop_front()分别对应于push_back()和pop_back()。因此，C++标准程序库保证下列行为：
（1）如果以push_back()或push_front()安插元素时发生异常，则该操作不带来任何效应。
（2）pop_back()和pop_front()不会抛出任何异常。
4.Deque运用实例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <deque> #include <string> #include <algorithm> #include <iterator> using namespace std; int main() { deque<string> coll; coll.assign(3,string("string")); coll.push_back("last string"); coll.push_front("first string"); copy(coll.begin(), coll.end(), ostream_iterator<string>(cout, "\n")); cout << endl; coll.pop_front(); coll.pop_back(); for (int i=1; i<coll.size(); ++i){ coll[i] = "another " + coll[i]; } coll.resize(4,"resized string"); copy (coll.begin(), coll.end(), ostream_iterator<string>(cout, "\n")); } |
输出：
|
1 2 3 4 5 6 7 8 9 10 11 |
[root@VM_198_209_centos cppstl]# ./deque first string string string string last string string another string another string resized string |