STL容器：deque实现

概述

vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间，可以在头尾两端分别做元素的插入和删除操作。vector虽然从技术上也可以实现对头尾两端进行操作，但由于vector的底层实现特点的原因，其头部操作效率奇差，故STL没有为vector实现这一功能。

deque和vector的最大差异，一在于deque允许于常数时间内对头部进行插入和删除操作，二在于deque是动态地以分段连续空间组合而成，随时可以增加一段新的空间并与已有空间链接起来，因此像vector那样“因旧空间不足而重新配置一块更大的空间，复制元素过去再释放旧空间”这样的事情在deque是不会发生的。
虽然deque也提供Ramdon Access Iterator，但它的迭代器并不是普通指针，其复杂度远比vector的迭代器要高得多。迭代器的实现差异影响到各种算法的效率，因此除非必要，应尽可能使用vector而非deque。某些操作（例如排序）可以将deque中的元素先完整复制到一个vector中，在vector中操作后再复制回deque。

deque的数据结构

为了实现逻辑上的连续线性空间（实际上是分段的连续线性空间），deque必须定义相应的数据结构来存储和管理这些分段的线性空间。如下图所示：

首先应该用另一个连续空间来存储这些分段连续空间的位置，也即这个空间用来存储每一段存放元素的空间的起始位置（指针），STL将这个数据结构命名为map，它实际上相当于一个指针数组，它的每个元素都指向另一段连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体，我们用deque来存储的数据都放在这一段段缓冲区中。SGI STL允许我们制定缓冲区的大小，默认值0表示将使用512bytes缓冲区。

template <typename T, typename Alloc = alloc, size_t Bufsiz = 0>
class deque {
public:
	typedef T value_type;
	typedef value_type* pointer;//解引用得到元素值
	...
protected:
	typedef pointer* map_pointer;//指针的指针，指向缓冲区，解引用得到缓冲区的地址


	map_pointer map;//指向map, map是一块连续空间，其中的每个元素都是一个指针（称为节点），指向一块缓冲区
	size_type map_size;
...
}

其次，deque的迭代器也必须做特殊实现。由上图可推断出，deque的迭代器必须知道分段连续空间（即缓冲区）在哪里。然后，为了实现迭代器移动，它必须能判断自己是否已经处于其所在缓冲区的边缘，如果是，移动时就需要跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握中控器（map）。迭代器由4个数据组成，node指向中控器map，first指向*node指向的缓冲区的首元素，last指向尾元素，cur则指向缓冲区中的现行（当前访问位置）元素。

迭代器

deque的迭代器设计如下：

template <typename T, typename Ref, typename Ptr, size_t BufSiz>
struct __deque_iterator { //由于deque迭代器的特殊需要，不能继承std::iterator
	typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
	typedef __deque_iterator<T, const T&, T*, BufSiz> const_iterator;
	static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T));}

	//未继承std::iterator，必须自行定义5个必要的迭代器相应类型
	typedef random_access_iterator_tag iterator_category;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef size_t size_type;
	typedef ptrdiff_t defference_type;
	typedef T** map_pointer;

	typedef __deque_iterator self;

	//保持与容器的联结
	T* cur;
	T* first;
	T* last;
	map_pointer node;
...
}

用来决定缓冲区大小的函数buff_size()调用__deque_buf_size()，后者是全局函数，定义如下：

inline size_t __deque_buf_size(size_t n, size_t sz) {
	//默认值为0，代表默认buffer大小为512bytes，若不为0，则buffer size由用户自定义
	return n != 0 ? n : (sz < 512 ? size_t(512/sz) : size_t(1));
}

deque迭代器实现

前文已经提到deque的迭代器比较特殊，它需要判断边界以进行“跳跃”缓冲区的操作，因此它的各种加减运算都需要对指针运算符进行重载。跳跃缓冲区的操作由set_node()函数来实现：
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first+difference_type(buffer_size());
}
以迭代器跳跃n个距离的源码为例：
self& operator+=(defference_type n) {
defference_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;//两处减1都是为了考虑0的边界情况
set_node(node + node_offset);
//切换至正确的元素
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
上述代码中对负数的处理是很有用的，因为当我们定义相反的运算符时，只需要将n值取反即可；
self& operator-=(difference_type n) {
//调用operator+=来完成
return *this += -n;
}

维护map的迭代器

deque除了维护一个指向map的指针外，也维护start，finish两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素的下一个迭代器（尾后迭代器）。这是为了动态增长map的大小而设计的，其增长的底层实现方式与vector一样都是构造一块更大的空间，将旧空间的元素复制过去，再销毁旧空间。但由于维持deque的特点以及map的复杂性，其代码实现上要考虑的因素更多。
deque的定义如下：
template <typename T, typename Alloc = alloc, size_t BufSiz = 0>
class deque {
public:
typedef T value_type;
typedef value_type* pointer;
typedef size_t size_type;


typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
protected:
//元素的指针的指针
typedef pointer* map_pointer;


iterator start;
iterator finish;
map_pointer map;
size_type map_size;
...
}

源码实现中，当deque的map不够时，会构造一个至少大小是8，至多是“所需缓冲区加2”（前后各预留一个，方便扩充），将元素复制过去。不同的是，由于deque是可以双向增长的，因此旧空间中的元素都放置在新空间的中间位置。复制后将start和finish两个迭代器内的指针都更新好，再构造缓冲区，这样就完成了一个map的增长过程。

本文摘自《STL源码剖析》，有改动