c++编程(17)——deque的模拟实现（1）迭代器篇

欢迎来到博主的专栏——c++编程
博主ID：代码小豪

博主模拟STL中的容器时，参考的是SGI版本的STL，如果你对STL的源码感兴趣，请私聊博主。

deque的底层原理

deque是线性表的一种，可以像vector一样，实现随机访问，也可以向链表一样，进行头部的插入和删除（并不是vector不能进行头部的数据插入与删除，而是vector进行头部和删除的效率太低了，时间复杂度是O（N），而deque是O（1）），这是deque特殊的数据结构导致的。

deque有着像list那样高效率的头尾插入，也能像vector那样随机访问，这是由于deque的空间并不像list那样无序，又不像vector那样的顺序空间，而是一块块零散的顺序空间来存储数据。由于deque并非完全连续，而是以分段的连续空间组成，这就导致deque可以不像vector那样繁杂的复杂的重新配置空间的操作。

deque是由分段的连续空间组成的，其结构如下：

由于不像vector那样是完全连续的数据结构，因此deque虽然能随机访问，但是效率要比vector低很多（因为会出现跨区访问的操作，这需要一定的时间开销）如果deque的前端空间或者后端空间满了，就会在deque的前端或后端增加新空间，以保持deque顺序存储的假象。

如果你对数据结构具有一定理解，那么你一定会对这个数据结构进行质疑：仅凭一个begin和end指针，是怎么做到管理分段的连续数组呢？当然，如果只是两个指针当然做不到。实际上deque的数据结构是这样子的。

deque中存在一个map数组，其元素是指向各个分段空间的指针，这么一来就好理解了。如果map数组拥有所有分段空间的指针，那么管理这些分段数组确实可行的，由于这个map数组有点像中央控制器，因此我们就将map称为中控数组吧。

中控数组map指向空间称为缓冲区（buffer），每个缓冲区可容纳的元素个数都是一致的，如果我们在deque的模板上定义一个非类型模板参数，那么这一点还是很好做到的。

template<class T,size_t bufsize=25>//bufsize是deque缓冲区的元素个数
class deque	{private:
};

但是单靠两个指针还是不能做到遍历整个deque容器啊，你想想，如果我们让begin指针++，那么begin就会越界访问，除非我们能让begin进行空间上的跳跃。

但是指针++只会让指针访问下一个元素，它是绝对不会进行跳跃的。那么我们就要设计deque的专属迭代器了。我们先不管deque的迭代器是什么样的，我们假设它的名字叫做deque_iterator。那么deque的定义如下：

	template<class T,class ptr,class ref,size_t bufsize>struct deque_iterator {//deque的迭代器};template<class T,size_t bufsize=25>//bufsize是deque缓冲区的元素个数class deque{typedef T* pointer;typedef pointer* map_poniter;//中控数组的类型private:deque_iterator first;//指向数组第一个元素的迭代器deque_iterator last;//指向数组最后一个元素后一位的迭代器map_poniter map;//中控数组size_t mapsize;//数组的个数};

deque的迭代器

deque实现随机访问的操作，其代价就是迭代器设计被设计的非常复杂。我们先来看看deque的迭代器需要完成哪些操作。

假设现在迭代器first指向第一个元素，如过访问first的下一个元素，first就会指向当前顺序空间的下一个元素，而如果要访问first的下两个元素，即first+2，那么就要让first实现空间上的跳跃。因此deque的迭代器应该具有以下的结构：

1. 首先迭代器需要知道当前所在的缓冲区在哪里
2. 迭代器需要知道当前是否处于当前缓冲区的边缘，这样才能判断访问的元素是否超过了当前的缓冲区
3. 如果超过了当前的缓冲区，就要跳跃到下一个缓冲区，因此迭代器需要访问到中控中心map来获得下一个缓冲区的位置

而SGI版本的STL是这么设计deque的迭代器的
deque的迭代器拥有四个成员，分别是first，last，node，以及cur，其各个成员的作用如下：

first指向当前的缓冲区的起始地址
last指向当前缓冲区的末尾地址
node指向map中的当前缓冲区，便于跳跃到下一个缓冲区。
cur指向缓冲区的当前元素（即访问的当前元素）

template<class T,class ptr,class ref,size_t bufsize>
struct deque_iterator {//deque的迭代器
typedef T* pointer;
typedef pointer* map_pointer;
typedef deque_iterator self;//这个self是迭代器的别名//data member
T* first;
T* last;
T* cur;
map_pointer node;
};

根据c++规定，每个容器的迭代器都要放在类中，并且起一个同一的别名，因此我们还要在deque当中typedef这个迭代器

template<class T,size_t bufsize=25>//bufsize是deque缓冲区的元素个数
class deque
{
//省略
public:typedef deque_iterator<T,T*,T&,bufsize> iterator;//为迭代器起一个别名typedef deque_iterator<T,const T*,const T&,bufsize> const_iterator;//为迭代器起一个别名
//省略
};

deque迭代器的操作

deque的迭代器有一个很重要的操作就是让迭代器获得跳跃缓冲区的能力，实际上也就是从map数组中的一个位置来到另一个位置，比如

如果我们要访问下一个缓冲区，就让node指向map数组中的下一个元素即可

当然了，迭代器的first和last必须保持指向node缓冲区的起始地址和结束地址。因此完成这个操作的函数我们用setnode()表示，该函数的定义如下：

void setnode(map_poniter newnode)
{node = newnode;first = *node;last = first + bufsize;
}

deque的迭代器支持两个迭代器进行相减得到之间的元素个数，这也是deque可以实现随机访问的重要原因（list就不支持）。

int operator-(const self& x)
{return int(node - x.node - 1) + cur - first + x.last - x.cur;
}

迭代器2减去迭代器1，其蓝色部分就是两个迭代器相减的元素个数。两个迭代器之间的元素个数等于，两个迭代器之间的缓冲区（不包括本身的缓冲区）的所有元素，加上迭代器2到起始为止的元素，再加上迭代器1到末尾的元素个数。

self& operator++(){++cur;//访问下一个元素if(cur==last){//如果下一个元素来到了缓冲区的结尾setnode(node + 1);//就来到下一个缓冲区cur = first;//cur指向新缓冲区的第一个元素}return *this;
}self operator++(int) {//后置++self tmp = *this;(*this)++;return tmp;
}

当迭代器访问下一个元素时，可能会出现以下两种情况

1. 如果访问的下一个元素还在缓冲区内（cur!=last-1），就让cur访问顺序结构的下一个元素
2. 如果访问的下一个元素不在缓冲区内，就让迭代器跳到下一个缓冲区，且cur指向缓冲区的起始地址

self& operator--(){if (cur == first){//判断cur是否来到了当前缓冲区的起始位置setnode(node - 1);//让node跳跃到上一个缓冲区cur = last - 1;//让cur指向末尾位置}else {cur--;}return *this;
}self operator--(int){//后置--self tmp = *this;(*this)--;return tmp;
}

让迭代器访问上一个元素的原理和operator++类似

1. 如果迭代器指向的元素所处的缓冲区前面还有元素，就让迭代器访问顺序结构的上一个元素
2. 如果迭代器指向的元素来到了缓冲区的起始地址，就要跳往上一个缓冲区，并且让迭代器的cur指向缓冲区的末尾元素(cur=last-1)
   
   

迭代器的其他操作

bool operator==(const self& x)const
{cur == x.cur;
}bool operator!=(const self& x)const
{cur != x.cur;
}bool operator<(const self& x)const
{return node == x.node ? cur < x.cur : node < x.node;
}

迭代器的随机访问操作

self& operator+=(int n)
{int offset = n + (cur - first);if (offset >= 0 && offset < bufsize)//判断是否在缓冲区内{cur += n;}else//目标不在缓冲区内{int offset_node =offset > 0 ? offset / int(bufsize) : ((offset + 1) /(int) bufsize) - 1;setnode(node + offset_node);//切换到正确的缓冲区cur = first + offset - offset_node * bufsize;//切换到正确的位置}
}

这段代码中最难以理解的就是变量offset了，这个offset简单理解为"偏移量"，指的是随机访问的元素与first之间数据。比如，我们假设cur指向第一个元素，让cur+=8；

首先我们先获得偏移量，offset=4+8=12；由于偏移量大于bufsize(6)，因此我们确定cur+=8的结果不在本缓冲区内。然后让offset/bufsize=12/6=2，于是确定cur+=的结果在后两个缓冲区当中，于是setnode让迭代器来到后两个迭代器。最后计算offset-offset_node*bufsize=0。说明要查找的元素在当前缓冲区的后两个缓冲区中相对于first的第0个元素。因此cur+=8的结果为。


为什么相对于first的第0个元素在这里呢？这是因为C的数组下标总是从0开始计算的。

其他的操作只需要复用operator+=即可。因为我们已经允许+=对负数n进行处理。

self operator+(int n)
{self tmp = *this;return tmp += n;
}self& operator-=(int n)
{return *this += (-n);
}self operator-(int n)
{self tmp = *this;return tmp -= (-n);
}ref operator[](int n)
{return *(*this + n);
}

到此为止，我们的迭代器已经设计好了，由于篇幅原因，博主将deque容器的实现放在下一篇博客当中叙述（因为两篇加起来大约2w字，实在是有点难啃）。

链接如下：
deque_iterator的实现代码