首页 > 代码库 > STL之序列容器deque
STL之序列容器deque
首先看看deque的模板声明：
template <class T, class Alloc = allocator<T>> // 原本还有个参数BufSize,现在新版本内置了，不允许用户指定了。
class deque {//…protected: // 数据成员 iterator start; // 表现第一个节点 iterator finish; // 表现最后一个节点 map_pointer map; // 指向map, map是块连续空间，其内的每个元素都是一个指//针，指向一块缓冲区（Buffer） size_type map_size; // map内可容纳多少指针 ……};
vector是单向开口的连续性空间，deque则是一种双向开口的连续性空间（逻辑上）。所谓双向开口，意思是可以在头尾两端分别做元素的插入（常数阶）与删除（常数阶）。当然vector也可以，但其头部操作效率太差（线性阶），无法被接受。
为什么说它只是逻辑上为连续性空间呢？原因在于deque其实是将一段段的连续空间串联起来，而给人造成连续空间的假象，为了这一现象其迭代器真是费了不少功夫呢。
deque接受2个（之前版本为3个）模板参数，其中后者（之前版本为后2个）属于默认参数，一般的话只需写入元素类型即可，如：
deque<int> deq;那么那个BufSize参数（之前版本，我们还是了解下）是用来做什么的呢？我们先来看看deque的构造方式。
如图所示，deque采用一块所谓的map作为主控。map是一小块连续空间，其中每个元素都是指针，指向另外一段较大的连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。
deque <int, allocator<int>> deq;
（图片来自侯捷老师课程《STL与泛型编程》， 侵删）
deque内设2个迭代器，如上图所示分别为start和finish，每个迭代器拥有4个指针，分别为cur, first, last, node.像start的cur指向容器首元素，first指向该元素位于的缓冲区的头，last指向该元素位于的缓冲区的尾。通过指针node控制map的前进后退。当map使用率满载时，再找一个更大的空间来作为map，map又来控制缓冲区，如此而已。当然构造出连续空间的假象，迭代器的实现就比较麻烦了，这里就不介绍了，我们只做了解。
简单对deque的结构了解后，我们来写一段测试代码：
#include <deque>#include <iostream>#include <algorithm>using namespace std;int main(){ deque<int, allocator<int>> ideq(20,9); cout << "size = " << ideq.size() << endl; // size = 20(20个元素，都为9） // 为每一个元素设置新值 for (int i = 0; i < ideq.size(); i++) { ideq[i] = i; } for (int i = 0; i < ideq.size(); i++) { // 0 1 2 3 ...19 cout << ideq[i] << " "; } cout << endl; for (int i = 0; i < 3; i++) { ideq.push_back(i); } for (int i = 0; i < ideq.size(); i++) { // 0 1 2 3 ...19 0 1 2 cout << ideq[i] << " "; } cout << "size = " << ideq.size() << endl; // size = 23 ideq.push_front(99); for (int i = 0; i < ideq.size(); i++) { // 99 0 1 2 3 ...19 0 1 2 cout << ideq[i] << " "; } cout << "size = " << ideq.size() << endl; // size = 24 deque<int, allocator<int>>::iterator iter; iter = find(ideq.begin(), ideq.end(),99); cout << *iter << endl; // 99 return 0; }
当然随着编译器的版本的更新，内部细节会发生一些变化，比如新版本取消了让用户自定义buffersize，转为内部自行实现。但基本原理及其存储方式是不会变化的。况且deque容器之复杂，也不是可以用这么短的文字和代码说明的，这里只是介绍deque的基本存储结构和运用，如果有兴趣加深加深了解的话推荐《STL源码剖析》，同时也推荐直接打开系统头文件自行阅读。
STL之序列容器deque