原理"/>
【STL】deque的实现原理
一、概述
vector是单向开口的连续空间，而deque是双向开口，即在头尾都可以进行插入和删除操作。如图所示：
两者最大的差异：
- deque是常数时间向头端进行插入或者移除。
- deque没有容量（capacity）的观念，因为它是动态分段连续空间组合成的。并不会提供空间保留的功能。
本章所采用list版本为 SGI STL 2.91版本。
二、deque的中控器
deque是连续空间，但是不同于array和vector的连续地址。它是通过一段一段定量的连续空间构成的，deque的任务便是维护其连续的假象，并提供随机存取的接口。
deque选取一块map（并非STL的map容器）作为主控。map中的每个元素都是一个指针，指向另一段较大的连续空间，简称缓冲区。缓冲区才是deque的存储空间主体。SGI中允许我们指定缓冲区的大小，但是在新版中，将该接口封闭了，所以后续并不介绍该部分内容。
template <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的迭代器
它的迭代器必须能够指出（缓冲区）在哪，是否到达缓冲区的边缘，如果到达边缘，怎么前往下一个缓冲区？怎么支持随机存储？
下面先看一下 iterator 一些定义以及变量声明：
template <class T,class Ref,class Ptr,size_t BufSiz>
struct __deque_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是分段连续空间，所以要维持这种分段连续的假象，首先要考虑的就是到达边界时，视前进或后退情况，调用 set_node() 跳进下一个缓冲区。
void set_node(map_pointer new_node) {//设定节点信息node = new_node;first = *new_node;last = first + difference_type(buffer_size());}
为了前后遍历考虑，需要对operator++ 和operator-- 两个运算符进行重载。同时，也需要指针加、减等几个关键行为支持。
reference operator*() const { return *cur; } //为了支持*itepointer operator->() const { return &(operator*()); } //为了支持ite->curdifference_type operator-(const self& x) const { //为了支持ite1 - ite2，返回元素个数return difference_type(buffer_size()) * (node - x.node - 1) +(cur - first) + (x.last - x.cur);}self& operator++() {//++ite++cur;if (cur == last) { //如果到达尾端，切换下一个缓冲区set_node(node + 1);cur = first;}return *this; }self operator++(int) {//ite++self tmp = *this;++*this;return tmp;}self& operator--() {//--iteif (cur == first) { //如果到达头端，切换下一个缓冲区set_node(node - 1);cur = last;}--cur;return *this;}self operator--(int) {//ite--self tmp = *this;--*this;return tmp;}
为了实现随机存取，迭代器可以直接跳跃n个距离，还需要对+=、-=等操作符进行重载
self& operator+=(difference_type n) {//支持ite+=ndifference_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 {//重载const重载+号。self tmp = *this;return tmp += n; //调用+=}self& operator-=(difference_type n) { return *this += -n; }//ite -=n通过+ -n实现。self operator-(difference_type n) const {//重载-self tmp = *this;return tmp -= n;}
同时，需要对一些 [] 、== 等操作符重载
//实现随机存储，迭代器调用operator* 和 operator+reference operator[](difference_type n) const { return *(*this + n); }//重载ite[]操作// [] 通过调用 operator* 和 operator+ 来实现。bool operator==(const self& x) const { return cur == x.cur; }//重载ite1 == ite2bool operator!=(const self& x) const { return !(*this == x); }//重载ite1 != ite2bool operator<(const self& x) const {return (node == x.node) ? (cur < x.cur) : (node < x.node);}//重载ite1 < ite2
当迭代器++ 、 – 、+= 等操作符的时候，一旦遇到缓冲区边缘，需要更换缓冲区的时候，那么用set_node更新迭代器三个成员变量的值，进入下（上）一个缓冲区。同时，为了更加深入理解源码，希望大家仔细分析，每个运算符重载时，调用的是 重载后的运算符 还是未重载的运算符。
四、deque的数据结构
deque除了维护指向map的指针外，还需要维护 start、finish 两个迭代器，分别指向第一个缓冲区的第一个元素和最后一个缓冲期的最后一个元素（下一个位置）。同时，也需要记住目前map的大小，一旦map的结点不足，需要配置更大的map。
整体结构如下图所示：
下面是关于 deque的基本定义：
template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque {
public: // Basic typestypedef T value_type;typedef value_type* pointer;typedef size_t size_type;
public: typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
protected: // Internal typedefstypedef pointer* map_pointer; protected: // Data membersiterator start; //开始迭代器，其中cur指向头部元素iterator finish; //结束迭代器，其中cur指向尾部元素后面的一个元素map_pointer map; //指向指针数组size_type map_size; //指针数组元素个数
}
通过上述结构，以下一些机能便可以轻易完成：
public: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 tmp = finish;--tmp; //调用迭代器中 operator--return *tmp; //调用迭代器中 operator**}size_type size() const{ return finish - start;; } //deque迭代器重载了 - 运算符size_type max_size() const { return size_type(-1); } bool empty() const{return finish == start;}
五、deque的构造和内存管理
deque缓冲区扩充比较复杂，下面逐步分解，程序开始声明一个deque：
deque<int,alloc,8> ideq(20,9);
现在，deque情况如上图所示，调用构造函数如下面代码所示。
deque(size_type 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_type n, const value_type& value) {create_map_and_nodes(n); //把deque结构都产生并安排好map_pointer cur;__STL_TRY {//为每个结点的缓冲区设置初值for (cur = start.node; cur < finish.node; ++cur)uninitialized_fill(*cur, *cur + buffer_size(), value);uninitialized_fill(finish.first, finish.cur, value);//尾部可能有多余空间，处理方式有所不同}
}
其中，create_map_and_nodes() 负责产生并安排好deque的结构：
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {size_type num_nodes = num_elements / buffer_size() + 1;/*相当于20/8 + 1 = 3。刚好整除，则多分配一个节点*/map_size = max(initial_map_size(), num_nodes + 2);//map至少管理8个节点，最多是所需节点+2，前后各预留一个位置，扩充时候使用。map = map_allocator::allocate(map_size);//分配指针数组//先使用map指针数组中间的位置，方便前后扩充map_pointer nstart = map + (map_size - num_nodes) / 2;map_pointer nfinish = nstart + num_nodes - 1;map_pointer cur;__STL_TRY {for (cur = nstart; cur <= nfinish; ++cur)*cur = allocate_node();//初始化指针数组成员}start.set_node(nstart);//存储开始nodefinish.set_node(nfinish);//存储结束nodestart.cur = start.first;//指向第一个元素finish.cur = finish.first + num_elements % buffer_size();//指向最后元素的后面一个元素形成[start , finish)左闭右开空间。
}
下面通过 ideq [] 对容器重新设值
for(int i=0;i<ideq.size();i++){ideq[i]=i;
}
并在尾端插入三个元素
for(int i=0;i<3;i++){ideq.push_back(i);
}
由于，最后一块缓冲区还有四个空间，所以不会进行缓冲区再分配，结果如图所示：
下面简单介绍push_back()，
//尾部添加元素void push_back(const value_type& t) {if (finish.cur != finish.last - 1) {//尾部还有多余空间，一个以上的空间construct(finish.cur, t);//直接构造++finish.cur;//调整缓冲区状态finish的cur+1}elsepush_back_aux(t);//没有或者只剩下一个，添加node，然后构造}
如果此时再进行一次push_back()，
ideq.push_back(3);
当尾端元素不足时，调用push_back_aux()，在配置一块新缓冲区，设置新内容，最后更改迭代器finish状态。
// Called only if finish.cur == finish.last - 1.
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();//分配节点，node__STL_TRY {construct(finish.cur, t_copy);//构造元素finish.set_node(finish.node + 1);finish.cur = finish.first;//设定finish}__STL_UNWIND(deallocate_node(*(finish.node + 1)));//释放返回
}
状态如图所示：
当调用push_front(99)时
ideq.push_front(99);
前面没位置了，然后前面需要动态在添加一个位置，不像vector一样，需要移动再添加。这个就是deque的方便之处。这里调用了push_front_aux增加了一个节点。
void push_front(const value_type& t) {if (start.cur != start.first) {construct(start.cur - 1, t);--start.cur;}elsepush_front_aux(t);}// Called only if start.cur == start.first.
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();//分配node__STL_TRY {start.set_node(start.node - 1);start.cur = start.last - 1;construct(start.cur, t_copy);}
}
如下图所示：
如果想要继续添加，由于前面还有位置，就不会造成缓冲区的重新分配。
ideq.push_front(98);
ideq.push_front(97);
前面已经讲述，deque最基本的空间分配策略，那么如果map满了，怎么办？
有以下两个函数进行判断：
void reserve_map_at_back (size_type nodes_to_add = 1) {if (nodes_to_add + 1 > map_size - (finish.node - map))reallocate_map(nodes_to_add, false); //第二参数，判断是向前还是向后判断}void reserve_map_at_front (size_type nodes_to_add = 1) {if (nodes_to_add > start.node - map)reallocate_map(nodes_to_add, true);}
reallocate_map() 先考虑原本空间是否够用，如果大于所需的2倍，通过copy进行重新分配。如果不够，那么就需要动态分配map，设计map内存分配，数据拷贝，然后释放原来。
六、总结
deque要比vector和list复杂很多，有很多细节的地方很难理解，大抵是我太愚，在hjj的谆谆教导下依旧不能很好理解。但整个最重要的地方就是在于，对于各种操作符的重载，要正确理解里面的操作符什么时间用到重载版本，什么时间是普通版本。
参考资料：
《STL源码剖析》- 侯捷
更多推荐
【STL】deque的实现原理
发布评论