目录：
1.deque概述
2.deque中控器
3.deque迭代器
4.deque数据结构
deque概述
vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间，即可以在头尾两端进行元素的插入和删除操作。vector当然也可以在头尾进行操作，但是头部操作效率特别差，无法被接受
deque和vector的最大差异，一在于deque允许常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓容量（capacity）的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大的空间，然后复制元素到新的空间，释放旧空间”这样的事情在deque是不会发生的。也因此，deque没有必要提供所谓的空间保留功能。
deque的迭代器并不是普通指针，复杂度非常大，因此，除非必要，尽可能的选择vecto而非deque，如果对deque排序，最好先将deque的元素复制到vector，然后vector执行sort，再复制回到deque
deque中控器
deque是连续空间，类似的有array和vector，array无法增长；vector只能从尾端增长，且是“伪增长”，代价高昂。
deque是由一段一段连续的空间构成，一旦有必要在deque的前端或尾端增加新的空间，便配置一段定量的连续空间，串接在整个deque的头端或尾端，维护其整体连续的假象，避开了“重新配置，复制，释放”的轮回，代价则是复杂的迭代器架构
deque才用一块所谓的map（不是STL 的map）作为主控，这里的map是一块连续空间，其中每个元素（此处为节点）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。1
2
3
4
5
6
7
8
9
10
11
12
13
14template <class T,class Alloc = alloc , size_t BufSiz = 0>
class deque{
public :
typedef T value_type;
typedef value_type* pointer;
...
protected:
typedef pointer* map_pointer; //元素的指针的指针
protected:
map_pointer map; //指向map，map是块连续的空间，
//其内的每个元素都是一个指针（称为节点）,指向一块缓冲区
size_type map_size; //map内有多少个指针
...
}
可以发现，map是一个 T**，也就是说他是一个指针，所指之物又是一个指针，指向型别为T的一块空间
deque的迭代器
首先该迭代器要具备两个功能：
1.可以指出分段连续空间（缓冲区）在哪里
2.可以判断自己是否处于缓冲区的边缘，如果是，一旦前进或后退，就必须跳跃至下一个或上一个缓冲区。1
2
3
4
5
6
7
8
9
10template <class T,chass Ref, class Ptr, size_t BufSiz>
struct _deque_iterator{
...
typedef T **map_pointer;
T *cur; //此迭代器所指的缓冲区中的当前元素
T *first; //此迭代器所指缓冲区的头
T *last; //此迭代器所指缓冲区的尾（含备用空间）
map_pointer node; //指向管控中心
...
}
假设产生一个deque
deque的数据结构
deque除了维护一个先前说过的指向map的指针外，也维护start，finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素（的下一位置）。此外，它也必须记住当前 map的大小。因为一旦map提供的节点不足，就必须重新配置更大的一块map1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque{
public:
typedef T value_type;
typedef value_type *pointer;
typedef size_t size_type;
public:
typedef _deque_iterator<T, T&, T*, BufSiz> iterator;
protected:
typedef pointer *map_pointer;
protected:
iterator start; //表现第一个节点
iterator finish; //表现最后一个节点
map_pointer map; //指向map，map是块连续空间，其每个元素都是一个指针，
//指向一个节点（缓冲区）
size_type map_size; //map内有多少指针
...
}