一、deque概述
vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，如下所示。vector也可以在头尾两端进行操作，但是其头部操作效率奇差，无法被接受。
deque和vector的最大差异，一在于deque允许常量时间内对头端进行元素的插入和移除，二在于deque没有所谓容量(capacity)观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。
虽然deque也提供了Ramdon Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可相比，这也影响了各个运算层面。因此，除非必要我们应尽可能选择使用vector而不是deque。对deque进行的排序操作，为了最高效率可以将deque先完整复制到一个vector身上，将vector排序后再复制回deque
二、deque的中控器
deque由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务便是在这些分段的定量连续空间上维护其整体连续的假象，并提供随机存取的接口。避开了"重新配置、复制、释放"的轮回，代价则是复杂的迭代器架构。
deque采用一块所谓的**map**(注意：不是STL的map容器)作为主控。这里所谓map是一小块连续空间，其中每个元素(此处称为一个节点，node)都是指针，指向另一段(较大的)连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。STL允许我们制定缓冲区大小，默认值0表示将使用512bytes缓冲区。
template<class T, class Alloc=alloc, size_t BufSize = 0>
class deque {
public: //基础类型
typedef T value_type;
typedef value_type *pointer;
typedef size_t size_type;
typedef value_type &reference;
typedef ptrdiff_t difference_type;
protected: //内建别名
//元素的指针的指针
typedef pointer *map_pointer;
......
protected: //数据成员
map_pointer map; //指向map，map是块连续空间，其元素都是个指针，指向一个节点缓冲区
size_type map_size; //map内可容纳多少个指针
......
map其实是一个T**，它是一个指针，所指之物又是一个指针，指向型别为T的一块空间。如下所示
三、deque的迭代器
deque是分段连续空间。维持其"整体连续"假象的任务，落在了迭代器的operate++和operator--两个运算子身上。
deque迭代器必须能够指出分段连续空间在哪里，其次它必须能够判断自己是否已经处于其所在缓冲区的边缘。如果是一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心(map)
template<class T, class Ref, class Ptr, size_t BufSize>
struct __deque_iterator { //未继承std::iterator
typedef __deque_iterator<T, T &, T *, BufSize> iterator;
typedef __deque_iterator<T, const T &, const T *, BufSize> const_iterator;
static size_t buffer_size() { return __deque_buf_size(BufSize, sizeof(T)); }
//未继承std::iterator，所以必须自行撰写五个必要的迭代器相应型别
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T **map_pointer;
typedef __deque_iterator self;
//保持与容器的联结
T *cur; //此迭代其所指之缓冲区的现行元素
T *first; //此迭代器所指之缓冲区的头
T *last; //此迭代器所指缓冲区的尾
map_pointer node; //指向管控之心
...
}
其中用来决定缓存区大小的函数buffer_size()调用__deque_buf_size()，后者是一个全局函数
//如果n不为0，传回n，表示buffer size由用户定义
//如果n为0，表示buffer size使用默认值，那么如果sz小于512，传回512/sz
//如果sz不小于512，传回1
inline size_t __deque_buf_size(size_t n, size_t sz) {
return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}
如下所示是deque的中控器、缓冲区、迭代器的相互关系
假设我们现在产生了一个元素型别为int，缓冲区大小为8的deque。经过某些操作之后，deque拥有20个元素，那么其begin()和end()所传回的两个迭代器应该如下图所示。这两个迭代器事实上一直保持在deque内，名为**start和finish**
20个元素需要20/8=3个缓冲区，所以map之内运用了三个节点。迭代器start内的cur指针指向缓冲区第一个元素，迭代器finish内的cur指针指向缓冲区的最后元素(的下一位置)。
下面是deque迭代器的几个关键行为。由于迭代器内对各种指针运算都进行了重载操作，所以各种指针运算如加、减、前进、后退都不能直观视之。其中最关键的就是：一旦行进时遇到缓冲区边缘，要特别小心，视前进或后退而定，可能需要调用set_node()跳一个缓冲区
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self &x) const {
return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
}
self &operator++() {
++cur; //切换至下一个元素
if (cur == last) { //如果已达所在缓冲区的尾端
set_node(node + 1); //就切换至下一个节点的第一个元素
cur = first;
}
return *this;
}
self operator++(int) {
self temp = *this;
++*this;
return temp;
}
self &operator--() {
if (cur == first) { //如果已达所在缓冲区的头端
set_node(node - 1); //就切换至前一个节点的最后一个元素
cur = last;
}
--cur; //切换至下一个元素
return *this;
}
self operator--(int) {
self temp = *this;
--*this;
return temp;
}
//实现随机存取，迭代器可以直接跳跃n个距离
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;
}
self operator+(difference_type n) const {
self temp = *this;
return temp += n;
}
self &operator-=(difference_type n) {
return *this += -n;
}
self operator-(difference_type n) const {
self temp = *this;
return temp -= n;
}
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self &x) const { return cur == x.node; }
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);
}
四、deque的数据结构
deque除了维护一个指向map的指针外，也维护start、finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一位置)。此外，它还必须记住当前map的大小。一旦map所提供的节点不足，就必须重新配置更大一块map
template<class T, class Alloc=alloc, size_t BufSize = 0>
class deque {
public: //基础类型
typedef T value_type;
typedef value_type *pointer;
typedef size_t size_type;
typedef value_type &reference;
typedef ptrdiff_t difference_type;
public:
typedef __deque_iterator<T, T &, T *, BufSize> iterator;
protected:
//元素的指针的指针
typedef pointer *map_pointer;
protected: //数据成员
iterator start; //表现第一个节点
iterator finish; //表现最后一个节点
map_pointer map; //指向map，map是块连续空间，其元素都是个指针，指向一个节点缓冲区
size_type map_size; //map内有多少个指针
public:
deque(int n, const value_type &value) : start(), finish(), map(0), map_size(0) {
fill_initialize(n, value);
}
iterator begin() { return start; }
iterator end() { return finish; }
reference operator[](size_type n) {
return start[difference_type(n)];
}
reference front() {
return *start;
}
reference back() {
iterator temp = finish;
--temp;
return *temp;
}
size_type size() const { return finish - start; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
}
五、deque的构造与内存管理
deque自行定义了两个专属的空间配置器
//专属空间配置器，每次配置一个元素大小
typedef simple_alloc<value_type, Alloc> data_allocator;
//专属空间配置器，每次配置一个指针大小
typedef simple_alloc<pointer, Alloc> map_allocator;
并提供了一个构造函数:
deque(int n, const value_type &value) : start(), finish(), map(0), map_size(0) {
fill_initialize(n, value);
}
其内所调用的fill_initialize()负责产生并安排好deque的结构，并将元素的初值设定妥当:
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_t n, const value_type &value) {
create_map_and_nodes(n);
map_pointer cur;
try {
//为每个节点的缓冲区设定初值
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
//最后一个节点的设定稍有不同(因为尾端可能有备用空间，不必设初值)
uninitialized_fill(finish.first, finish.cur, value);
}
catch (...) {
}
}
其中create_map_and_nodes()负责产生并安排好deque的结构:
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(deque::size_type num_elements) {
//需要节点数=(元素个数/每个缓冲区可容纳的元素个数)+1
//如果刚好整除，会多配一个节点
size_type num_node = num_elements / buffer_size() + 1;
//一个map要管理几个节点。最少八个，最多是"所需节点数加2"
//前后各预留一个，扩充时可用
map_size = std::max(initial_map_size(), num_node + 2);
map = map_allocator::allocate(map_size);
//以上配置出一个"具有map_size个节点"的map
//以下令nstart和nfinish指向map所拥有之全部节点的最中央区段
//保持在最中央，可使头尾两端的扩充能量一样大，每个节点可对应一个缓冲区
map_pointer nstart = map(map_size - num_node) / 2;
map_pointer nfinish = nstart + num_node - 1;
map_pointer cur;
try {
//为map内的每个现行节点配置缓冲区，所有缓冲区加起来就是deque的可用空间
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();
}
catch (...) {
}
//deque内的两个迭代器start和end设定正确内容
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_elements % buffer_size();
}
以下是push_back()函数内容：
void push_back(const value_type &t) {
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
++finish.cur;
}
else {
push_back_aux(t);
}
}
再增加一个新元素于尾端，由于尾端只剩一个元素备用空间，于是push_back()调用push_back_aux()，先配置一整块新的缓冲区，在设置新元素内容，然后更改迭代器finish的状态:
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type &t) {
value_type t_copy = t;
reserve_map_at_back(); //若符合某种条件则必须重换一个map
*(finish.node + 1) = allocate_node(); //配置一个新节点
try {
construct(finish.cur, t_copy); //针对标的元素设值
finish.set_node(finish.node + 1); //改变finish，令其指向新节点
finish.cur = finish.first; //设定finish的状态
}
catch (...) {
deallocate_node(*(finish.node + 1));
}
}
现在，deque的状态如下图所示:
push_front()函数操作如下：
void push_front(const value_type &t) {
if (start.cur != start.first) { //第一缓冲区尚有备用空间
construct(start.cur - 1, t); //直接在备用空间上构造元素
--start.cur; //调整第一缓冲区的使用状态
}
else {
push_front_aux(t); //第一缓冲区已无备用空间
}
}
由于目前状态下，第一缓冲区并无备用空间所以调用push_front_aux()：
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type &t) {
value_type t_copy = t;
reserve_map_at_front(); //若符合某种条件则必须重换一个map
*(start.node - 1) = allocate_node(); //配置一个新节点
try {
start.set_node(start.node - 1); //改变start，令其指向新节点
start.cur = start.last - 1; //设定start的状态
construct(start.cur, t_copy); //针对标的元素设值
}
catch (...) {
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*start.node - 1);
throw;
}
}
该函数一开始即调用reserve_map_at_front()，后者用来判断是否需要扩充map，如有需要就付诸行动。
什么时候map需要重新整治？这个问题的判断由reserve_map_at_back()和reserve_map_at_front()进行，实际操作则由reallocate_map()执行：
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reserve_map_at_back(deque::size_type node_to_add) {
if (node_to_add + 1 > map_size - (finish.node - map))
//如果map尾端的节点备用空间不足，符合上述条件则必须重换一个map
reallocate_map(node_to_add, false);
}
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reserve_map_at_front(deque::size_type node_to_add) {
if (node_to_add > start.node - map)
//如果map前端的节点备用空间不足，符合上述条件则必须重换一个map
reallocate_map(node_to_add, true);
}
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::reallocate_map(deque::size_type node_to_add, bool add_at_front) {
size_type old_num_nodes = finish.node - start.node + 1;
size_type new_num_nodes = old_num_nodes + node_to_add;
map_pointer new_nstart;
if (map_size > 2 * new_num_nodes) {
new_nstart = map + (map_size - new_num_nodes) / 2 + (add_at_front ? node_to_add : 0);
if (new_nstart < start.node)
std::copy(start.node, finish.node + 1, new_nstart);
else
std::copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
} else {
size_type new_map_size = map_size + std::max(map_size, node_to_add) + 2;
//配置一块空间，准备给新map使用
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2 + (add_at_front ? node_to_add : 0);
//把原map内容拷贝过来
std::copy(start.node, finish.node + 1, new_nstart);
//释放原map
map_allocator::deallocate(map, map_size);
//设定新的map的起始地址与大小
map = new_map;
map_size = new_map_size;
}
//重新设定迭代器start和finish
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
六、deque的元素操作
void pop_back() {
if (finish.cur != finish.first) {
//最后缓冲区有一个(或更多)元素
--finish.cur; //调整指针
destory(finish.cur); //将最后元素析构
}
else {
pop_back_aux(); //最后缓冲区没有任何元素
}
}
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_back_aux() {
deallocate_node(finish.first); //释放最后一个缓冲区
finish.set_node(finish.node - 1); //调整finish的状态，使指向上一个缓冲区的最后一个元素
finish.cur = finish.last - 1;
destory(finish.cur); //将该元素析构
}
void pop_front() {
if (start.cur != start.last - 1) {
destory(start.cur);
++start.cur;
}
else {
pop_front_aux();
}
}
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::pop_front_aux() {
destory(start.cur);
deallocate_node(start.first);
start.set_node(start.node + 1);
start.cur = start.first;
}
接下来是clear()函数，用来消除整个deque
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::clear() {
for (map_pointer node = start.node + 1; node < finish.node; ++node) {
destory(*node, *node + __deque_iterator<T, T &, T *, BufSize>::buffer_size());
data_allocator::deallocate(*node, __deque_iterator<T, T &, T *, BufSize>::buffer_size());
}
if (start.node != finish.node) {
destory(start.cur, start.last);
destory(finish.first, finish.cur);
data_allocator::deallocate(finish.first, __deque_iterator<T, T &, T *, BufSize>::buffer_size());
} else {
destory(start.cur, finish.cur);
}
finish = start;
}
下面是erase()函数，用来清除某个元素：
iterator erase(deque::iterator pos) {
iterator next = pos;
++next;
difference_type index = pos - start;
if (index < (size() >> 1)) {
std::copy_backward(start, pos, next);
pop_front();
} else {
std::copy(next, finish, pos);
pop_back();
}
return start + index;
}
接下来这个erase()函数用来清除[first,last]区间内的所有元素：
template<class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator deque<T, Alloc, BufSize>::erase(deque::iterator first, deque::iterator last) {
if (first == start && last == finish) {
clear();
return finish;
} else {
difference_type n = last - first;
difference_type elems_befor = first - start;
if (elems_befor < (size() - n) / 2) {
std::copy_backward(start, first, last);
iterator new_start = start + n;
destory(start, new_start);
for (map_pointer cur = start.node; cur < new_start.node; ++cur)
data_allocator::deallocate(*cur, __deque_iterator<T, T &, T *, BufSize>::buffer_size());
start = new_start;
} else {
std::copy(last, finish, first);
iterator new_finish = finish + n;
destory(new_finish, finish);
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
data_allocator::deallocate(*cur, __deque_iterator<T, T &, T *, BufSize>::buffer_size());
finish = new_finish;
}
return start + elems_befor;
}
}
接下来是insert()函数：
template<class T, class Alloc, size_t BufSize>
typename deque<T, Alloc, BufSize>::iterator deque<T, Alloc, BufSize>::insert(deque::iterator position, const value_type &x) {
if (position.cur == start.cur) {
push_front(x);
return start;
} else if (position.cur == finish.cur) {
push_back(x);
iterator temp = finish;
--temp;
return temp;
} else {
return insert_aux(position, x);
}
}
template<class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::insert_aux(deque::iterator pos, const value_type &x) {
difference_type index = pos - start;
value_type x_copy = x;
if (index < size() / 2) {
push_front(front());
iterator front1 = start;
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
std::copy(front2, pos1, front1);
} else {
push_back(back());
iterator back1 = finish;
--back1;
iterator back2 = back1;
--back2;
pos = start + index;
std::copy_backward(pos, back2, back1);
}
*pos = x_copy;
return pos;
}