STL容器deque使用
deque简介
deque与vector非常相似。它也采用动态数组来管理元素，提供随机存取，并有着和vector几乎一模一样的接口。不同的是deque的动态数组头尾都开放，因此能在头尾两端进行快速安插和删除。
与vector相比，deque功能上的不同在于：
两端都能快速安插元素和移除元素（vector只在尾端插入）。这些操作可以在分期摊还的常数时间内完成。
存取元素时，deque的内部结构会多一个间接过程，所以元素的存取和迭代器的动作会稍稍慢一些。
迭代器需要在不同区块间跳转，所以必须是特殊的智能型指针，非一般指针。
在对内存区块有所限制的系统中，deque可以内含更多的元素，因为它使用不止一块内存。故deque的max_size()可能更大。
deque不支持对容量和内存重分配时机的控制。特别注意的是，除了头尾两端，在任何地方安插或删除元素，都将导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vectors，因为其内部结构显示，deuqe不必在内存重分配时复制所有元素。
deque的内存区块不再被使用时，会被释放。deque的内存大小是可能缩减的。
deque与vector相似特性如下：
在中段部分安插、移除元素的速度相对较慢，因为所有元素都需移动以腾出或填补空间。
迭代器属于随机存取迭代器。
在以下情形，最好采用deque：
需要在两端安插和移除元素。
无需引用（refer to）容器内的元素。
要求容器释放不再使用的元素。
deque基本操作
- 构造、析构操作
deque c：产生一个空的deque
deque c1(c2)：针对某个deque产生同型副本（所有元素都被拷贝）
deque c(n)：产生一个deque，含有n个元素，这些元素均匀default构造函数产生出来
deque c(n, elem)：产生一个deque，含有n个元素，这些元素均是elem的副本
deque c(beg, end)：产生一个deque，以区间[beg; end]内的元素为初值
c.~deque()：销毁所有元素，释放内存
- 非变动性操作
c.size()：返回容器的实际元素个数
c.empty()：判断容器大小是否为零。等同于size()==0，但可能更快
c.max_size()：返回可容纳的最大元素数量
c1 == c2：判断是否c1等于c2
c1 != c2：判断是否c1不等于c2。等同于!(c1 == c2)
c1 < c2：判断是否c1小于c2
c1 > c2：判断是否c1大于c2。等同于c2 < c1
c1 <= c2：判断是否c1小于等于c2。等同于!(c2 < c1)
c1 >= c2：判断是否c1大于等于c2。等同于!(c1 < c2)
c.at(idx)：判断索引idx所标示的元素。如果idx越界，抛出out_of_range
c[idx]：返回索引idx所标示的元素。不进行范围检查
c.front()：返回第一个元素。不检查元素是否存在
c.back()：返回最后一个元素。不检查元素是否存在
c.begin()：返回第一个元素。不检查元素是否存在
c.end()：返回一个随机迭代器，指向第一个元素
c.rbegin()：返回一个逆向迭代器，指向逆向迭代时的第一个元素
c.rend()：返回一个逆向迭代器，指向逆向迭代时的最后元素的下一位置
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)：将c1和c2的元素互换
c.insert(pos, elem)：在pos位置插入一个elem副本，并返回新元素的位置
c.insert(pos, n, elem)：在pos位置插入elem的n个副本，并无返回值
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.resize(num)：将大小（元素个数）改为num。如果size()增长了，新增元素都以default构造函数产生出来
c.resize(num, elem)：将大小（元素个数）给位num。如果size()增长了，新增元素都是elem的副本
c.clear()：移除所有元素，将容器清空
deque的各项操作只有以下数点和vectors不同：
deque不提供容量操作capacity()和reserve()
deque直接提供函数，用以完成头部元素的安插和删除（push_front()和pop_front()。
需要考虑如下：
除了at()，没有任何成员函数会检查索引或迭代器是否有效
元素的插入或删除可能导致内存重新分配，所以任何插入或删除动作都会使所有指向deque元素的pointers、references和iterators失效。唯一例外的是在头部或尾部插入元素，动作之后，pointers和references仍然有效（但iterators没这么幸运）。
- 异常处理
如果已push_back()或push_front()安插元素时发生异常，则该操作不带来任何效应
pop_back()和pop_front()不会抛出任何异常。
参考文献：C++标准库、STL源码分析