一个双向开口的逻辑上连续线性空间。
Vector 和 Deque 一般是可以放一起讨论的，但是实际上 Deque 的实现复杂比 Vector 难了…额不以万里计…
Deque 在头部和尾部都可以做到常数时间的插入和删除操作。
当然 Vector 也可以在头部进行插入和删除操作，但是这个速度嘛…自己体会。
Deque 相对于 Vector 来说，是没有容量(capacity)的概念的，因为它是由个数动态增长的分段空间组合而成的（这些空间在逻辑上是连续的），所以不会像Vector一样需要进行配置复制释放来完成增长。
Deque也提供了 Random Access Iterator(随机存取迭代器)，但是它的迭代器并不是普通指针，其复杂度相比Vector来说，简直上天~恩…上天。
因此，除非必要的操作，我们应尽可能选用 Vector 而不是 Deque。
如果我们要对 Deque 进行排序操作，就先将 Deque 复制到一个 Vector 中，对 Vector 进行排序后，再复制回 Deque.
Deque的中控器：
Deque 在逻辑上来看是一段连续线性空间，实际上(物理上)则是由一段段的定量连续空间构成。
如果有必要在Deque的首部或者尾部增加一段新的空间的话，那就配置一段定量连续空间，然后串接在 Deque 的首部或者尾部即可。
Deque 采用了一小块所谓的map(这里指的并不是STL的容器，而是一个二级指针)作为主控，这里的map是一小块线性连续空间，每一个元素也都是一个指针，指向另一段连续线性空间的头部，我们称这段空间为缓冲区。这些缓冲区就是Deque的存储空间主体。
STL一般是允许指定缓冲区的大小的，默认0则表示用512byte大小的缓冲区。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template <class T, class Alloc = alloc , size_t BufSiz = 0> class deque { public: typedef T value_type; typedef T* pointer; //... protected: typedef pointer* map_pointer; //一个指向元素的指针的指针 protected: map_pointer map; //指向实际map，其内每个元素都是一个指针，指向一块缓冲区，所以map是二级指针 size_type map_size; //map内可容纳指针数量 //... } |
样子嘛，还是上图把，这样比较明显：
Deque的大致情况我们了解了，接来下我们来我们来看看迭代器的设计。
Deque的迭代器：
我们知道，Deque是一个分段的逻辑连续空间，那么如何让这个空间看起来是连续的呢，就得靠与外界的接口迭代器来实现了。
所以其真正的任务是 operator++ 与 operator– 的设计。
那么Deque的迭代器应该具备什么能力呢，首先它要指出分段连续空间的位置(即缓冲区的位置)，然后要能判断自己是否位于缓冲区的边缘，然后又要能够正确跳到下一个或者上一个缓冲区，于是必须掌控map。
采用了下面的实现方法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
template <class T, class Ref, class Ptr, size_t BufSiz> struct __deque_iteraotr { typedef __deque_iterator<T, T&, T*, BufSiz> iterator; typedef __deque_iteraotr<T, const T&, const T*, BufSiz> const_iteraotr; static size_t buffer_size() { return __deque_buf_size(BufSiz, sizeof(T)); } 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; //管控中心 //... }; inline size_t __deque_buf_size(size_t n, siez_t sz) { return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); } |
下图可以很好地表示deque的中控器，迭代器，缓冲区之间的关系：
下面是 Deque 迭代器的几个关键行为。由于迭代器内对各种指针的运算都进行了重载操作，所以各种指针运算如加、减、前进、后退都不能直观视之。
其中重点是：当行进到迭代器边缘时，要调用 set_node函数 跳一个缓冲区。
|
1 2 3 4 5 6 |
void set_node(map_pointer new_node) { node = new_node; first = *new_node; last = first + difference_type(buffer_size()); } |
以下各个运算子的重载，则是Deque Iterator 成功运作的关键：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
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; //1.跳至下一个元素 if(cur == last) //2.如果到了尾端 { set_node(node + 1); //3.切换下一缓冲区 cur = first; //4.切换为第一个元素 } return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { if(cur == first) //1.如果在缓冲区头部 { set_node(node -1); //2.切换上一缓冲区 cur = last; //3.切换到缓冲区尾端 } --cur; //4.跳至上一元素，即最后一个元素 return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; } //实现随机存取。迭代器可以直接跳跃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 tmp = *this; return tmp += n; } self& operator -=(difference_type n) { //精妙！ return *this += -n; } self operator- (difference_type n) const { self tmp = *this; return tmp -= n; } //实现随机存取，迭代器可以直接跳跃n个距离 reference operator[](difference_type n) const { return *(*this + n); } 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; } |
Deque的数据结构：
除了要维护map之外，也维护 start，finish两个迭代器，分别指向缓冲区第一个元素和最后一个元素的下一位置。
除此之外，还要知道map的大小。（一旦map大小不足则需要重新配置）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
template <class T, class Alloc = alloc, size_t BufSiz = 0> class deque { public: typedef T value_type; typedef value_type* pointer; typedef size_t size_type; //... public: typedef __deque_iterator<T, T&, T*, BufSiz> iterator; protected: typedef pointer* map_pointer; //二级指针 protected: iterator start; //第一个节点 iterator finish; //最后一个结点 map_pointer map; //指向实际map，其内每个元素都是一个指针，指向一块缓冲区 size_type map_size; //map内可容纳指针数量 //... } |
这样，有了上述结构，以下机能便能轻易完成：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public: iterator begin() { return start; } iterator end() { return finish; } reference operator[](size_type n) {//调用 __deque_iterator<>::operator[] return start[difference_type(n)]; } reference front() { return *start; } reference back() { iterator tmp = finish; -- tmp; return *tmp; } size_type size() const { return finish - start; } size_type max_size() const { return size_type(-1); } bool empty() const { return finish == start; } |
deque的构造与内存管理：
来来来，看代码…反正每次侯捷大神都这样…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <deque> #include <iostream> #include <algorithm> using namespace std; int main() { deque<int> ideq(20,9); //Size = 20 cout << "Size = " << ideq.size() << endl; for(int i=0;i<ideq.size();i++) ideq[i] = i; //0 1 2 3 4 5 ... 19 for(int i=0;i<ideq.size();i++) cout << ideq[i] << " "; cout << endl; for(int i=0;i<3;i++) ideq.push_back(i); //0 1 2 3 ... 19 0 1 2 for(int i=0;i<ideq.size();i++) cout << ideq[i] << " "; cout << endl; //Size = 23 cout << "Size = " << ideq.size() << endl; ideq.push_back(3); //0 1 2 3 ... 19 0 1 2 3 for(int i=0;i<ideq.size();i++) cout << ideq[i] << " "; cout << endl; //Size = 24 cout << "Size = " << ideq.size() << endl; ideq.push_front(99); //99 0 1 2 3 ... 19 0 1 2 3 for(int i=0;i<ideq.size();i++) cout << ideq[i] << " "; cout << endl; //Size = 25 cout << "Size = " << ideq.size() << endl; ideq.push_front(98); ideq.push_front(97); //97 98 99 0 1 2 3 ... 19 0 1 2 3 for(int i=0;i<ideq.size();i++) cout << ideq[i] << " "; cout << endl; //Size = 27 cout << "Size = " << ideq.size() << endl; deque<int>::iterator ite; ite = find(ideq.begin(),ideq.end(),99); if(ite!=ideq.end()) { //99 cout << *ite << endl; //cout << *(ite.cur) << endl; //99 cout << *(ite._M_cur) << endl; } } |
哔~…太复杂了…恩不爆粗…2016.7.19 记于此…留待后观。
【STL】Deque