deque是一种那个双向开口的连续线性空间，其头尾端做元素的插入和删除效率比vector效率高很多。Deque和vector的最大差异，一在于deque允许常数时间内对头尾端进行元素插入或移除操作，二在于deque没有所谓容量概念，因为它是动态地分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
deque提供的迭代器也是RandomAccess Iterator，但它的迭代器并不是普通指针。对deque进行排序操作，为了最高效率，可将deque先完整的复制到一个vector身上，将vector排序后(利用STL的sort算法)，在复制回deque。
deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。
deque采用一块所谓map（不是STL中的map）作为主控。这里所谓的map是一小块连续空间，其中每个元素(此处成为一个节点，node)都是指针，指向另一段（较大）连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区。
typedef value_type* pointer;
//元素指针的指针
typedef pointer* map_pointer;
map_pointer map; //指向map,map是连续空间，其内的每个元素都是一个指针，指向
//一块缓冲区
size_typemap_size; //map内可容纳多少指针
deque是分段连续空间。维持其”整体连续”假象的任务，落在了operator++和operator--上。
Deque迭代器维护四个指针，一个指向缓冲区现行元素，一个指向缓冲区的头，一个指向缓冲区的尾，还有一个指向对于管控中心中的节点。
下面是迭代器的部分源代码：
template <class T, class Ref, class Ptr>
struct __deque_iterator { // 未继承 std::iterator
typedef __deque_iterator<T, T&, T*> iterator;
typedef __deque_iterator<T, const T&, const T*> const_iterator;
static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); }
#endif
//未继承std::iterator，所以必须自行撰写五个必要的迭代器相应型别
typedef random_access_iterator_tag iterator_category; // (1)
typedef T value_type; // (2)
typedef Ptr pointer; // (3)
typedef Ref reference; // (4)
typedef size_t size_type;
typedef ptrdiff_t difference_type; // (5)
typedef T** map_pointer;
typedef __deque_iterator self;
// 保持与容器的联结
T* cur; // 此迭代器所指的缓冲区中的现行元素
T* first; // 此迭代器所指的缓冲区的头
T* last; // 此迭代器所指缓冲区的位（含备用空间）
map_pointer node; //执行管控中心
__deque_iterator(T* x, map_pointer y)
: cur(x), first(*y), last(*y + buffer_size()), node(y) {}
__deque_iterator() : cur(0), first(0), last(0), node(0) {}
__deque_iterator(const iterator& x)
: cur(x.cur), first(x.first), last(x.last), node(x.node) {}
// 以下各个重载运算子是__deque_iterator<>成功运作的关键
reference operator*() const { return *cur; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
}
// postfix forms of increment and decrement operators.
self& operator++() {
++cur; // 切换至下一元素
if (cur == last) { //如果已达所在缓冲区的尾端
set_node(node + 1); // 就切换至下一节点（亦即缓冲区）
cur = first; // 的第一个元素
}
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) { // 如果已达所在缓冲区的尾端
set_node(node - 1); // 就切换至前一节点
cur = last; // 的最后一个元素
}
--cur; // 切换至前一元素
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
if (offset >= 0 && offset < difference_type(buffer_size()))
// 目标位置在同一缓冲区内
cur += n;
else {
// 目标位置不在同一缓冲去内
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
// 切换至正确的节点（亦即缓冲区）
set_node(node + node_offset);
// 切换至正确的元素
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
// stand-alone op.
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n; // 调用operator+=
}
self& operator-=(difference_type n) { return *this += -n; }
// 以上利用operator+= 来完成 operator-=
// stand-alone op.
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n; // 调用operator-=
}
reference operator[](difference_type n) const { return *(*this + n); }
// 以上调用operator*, operator+
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
};
deque的构造、内存管理，以及元素操作：
dequeue自行定义了两个专属的空间配置器。一个用于配置元素空间，另一个用于配置map空间大小。首先会配置map空间，使map空间最中央区段得到利用，最中央区段的每个节点都对于一个即将分配的缓冲区。然后配置缓冲区，所以缓冲区加起来就是deque的可用空间（最后一个缓冲区可能有一些余裕）。然后为deque内的两个迭代器start和end设定正确内容。
push_back()实现：当尾端有两个以上的元素备用空间，直接在备用空间上构造元素，然后更改迭代器finish的状态。当缓冲区只剩下一个元素备用空间，会先配置一整块新的缓冲区，再设妥新元素内容，然后更改迭代器finish的状态。
push_front()实现：当第一缓冲区尚有备用空间，直接在备用空间上构造元素，调整第一缓冲区的使用状态。当第一缓冲区已无备用空间，配置一个新缓冲区，调整start状态，设妥新元素内容。
当执行push_back()时，map尾端的节点备用空间不足或执行push_front()时，map前端的节点备用空间不足就重新配置一块更大的空间（new_map_size = map_size + max(map_size,nodes_to_add)+2 ）给新map使用，然后把元map内容拷贝过来，释放原来map，设定新map的起始地址和大小。
pop_back()实现：当缓冲区有一个以上元素，调整finish状态，析构最后一个元素。当最后缓冲区没有任何元素时，则将最后一个缓冲区释放，调整finish状态，使指向上一个缓冲区的最后一个元素，将该元素析构。
pop_front()实现：第一个缓冲区有两个以上元素，将第一个元素析构，调整指针。当第一个缓冲区只有一个元素，将第一个缓冲区的元素析构，释放第一个缓冲区，调整start状态，使指向下一个缓冲区的第一个元素。
clare()实现：用来清除整个deque,注意deque的最初状态保有一个缓冲区，因此clear()完成之后恢复初始状态，也需要保留一个缓冲区。首先将除了头尾以外的每一个缓冲区中的元素析构，然后释放内存。再将头尾缓冲区元素析构，释放尾部缓冲区内存，头缓冲区保留调整finish和start状态。
erase()实现：用来清除一个前闭后开区间内的所有元素。如果是清除整个区间，直接掉头clear()。为提高效率，如果清除区间前方元素比较少，那就向后移动前方元素（覆盖清除区间），将冗余的元素析构。如果后方元素比较少，那就向前移动后方元素（覆盖清除区间），将冗余的元素析构。
Insert()实现：允许在某个点之前插入一个元素。如果插入点是最前端，交给push_front去做，如果插入点是最尾端，交给push_back去做。否则如果插入点之前的元素个数比较少，在最前端加入与第一个元素同值的元素，然后使旧的第一个点到插入点之前的元素向前移动，最后在插入点上设定新值。否则，在最尾端加入与最后元素同值的元素，然后进行元素移动，最后在插入点出设定新值。
原文：http://blog.csdn.net/walkerkalr/article/details/22819799