首页 > 代码库 > vector,list,deque容器的迭代器简单介绍
vector,list,deque容器的迭代器简单介绍
我们知道标准库中的容器有vector,list和deque。另外还有slist，只不过它不是标准容器。而谈到容器，我们不得不知道进行容器一切操作的利器---迭代器。而在了解迭代器之前，我们得先知道每个容器的结构，包括它的逻辑结构和物理结构。让我们先说说vector:
一、vector
我们先来看看vector容器内元素在内存中的布局：
其中的#0，#1...就是容器内的元素。从上图可以看出vector维护的是一个连续的线性空间，和数组是一样的。所以不论其元素为何种型别，普通指针就可以作为vector的迭代器！因为vector迭代器所需要的操作如operator*,operator->,operator++,operator+,operator-,operator+=,operator-=,普通指针天生就具备。查看vector的源码，我们可以看到vector的迭代器并没有另外定义为一个模版类，而是直接 typedef value_type* iterator。 更可以看出 vector 的迭代器就是一个普通指针。对于普通指针，我就不在多说。相信大家也早已理解。
二、list
还是先来看看list的结构：从list的名字我们就可以看出 list 的结构应该是一个链表，事实上他的结构确实是一个链表---一个环状双向链表。他的结构图如下：；
画的可能有点乱，但是如果你知道双链表的结构，你可以自行画出。上图的每个结点就是 list 容器中用来保存元素值的结构了。其中的#0,#1...就是容器的实际保存的元素值。而 list 的迭代器本身是一个模板类，我们看看 list 的迭代器设计：
template<class T, class Ref, class Ptr> struct __list_iterator { //定义了一些类型的别名 typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; //构造函数 __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} //重载操作符 bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } reference operator*() const { return (*node).data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; } };
这个迭代器的模板类其实并没有多少东西。只包括：
1.定义一些类型别名
2.定义一个 node 成员变量
3.必要的构造函数和重载了的操作符
其中真正起作用的是 node 成员变量，它是指向 list 链表结构的结点的普通指针， list 链表结点的结构定义代码如下：
template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data; };
就是一般的结构体啦，不过这里是模板形式的。其中的 prev 和 next是双向链表必须的两个指针分别指向前一个结点和后一个结点。data 用来保存实际的值。可以看出，list 的迭代器只是封装了 list node 的指针 ，并重载了迭代器应有的操作符而已。想想我们在用普通操作链表的时候，要想指向下一个结点，也就是实现指针的自增是怎么做的？是不是用 p = p->next啊，只不过这里把他用++操作符代替了我们的操作，更加方便了而已！所以 list 的迭代器也挺简单。list 迭代器重载了 ==, !=, *, ->, 前置++,后置++,前置--,后置--。没有重载 +,-,+=,-n，所以 list 的迭代器只是一个 Bidirectional Iterator。而 vector 的迭代器是普通指针，它是 Random Access Iterator。
三、deque
我们知道 vector 是个单向开口的连续线性空间，而 deque 则是一种双向开口的连续线性空间。所以 vector 从尾端插入元素效率较高，而如果从头部插入，则效率奇差。deque 可以从两端插入，效率也很高。在介绍 deque 迭代器之前，我们先来了解一下 deque 的逻辑结构。deque 到底是什么样的一个结构、在内存中如何布局，才可以从两端插入且是连续线性空间呢？我还是先来张图，根据图我们再娓娓道来：
看到这个图，大家也许蒙了，第一反映是怎么这么复杂？跟 vector 内存布局比起来，确实很复杂。因为它并不是真正的连续线性空间，而是模拟的。看到图中标志的缓冲区(node-buffer)没，它才是用来存储 deque 容器元素的真正承担者。他们是一段段定量连续空间。其大小可以自己指定，默认是 512bytes。接下来我们看看 map 这个结构：它也是一个连续的线性空间，不过它保存的是指向每个缓冲区(node-buffer)首地址的指针。map 起着中央控制器的作用，所以我们称其为中控器。既然 deque 在内存中如此布局，那如何伪装成一个连续的线性空间呢？造成这个假象的任务全落到了迭代器的身上。我们来看看 deque 迭代器、中控器、缓冲区之间的相互关系：
为了更好的说明问题，我给出一个实际的例子。现在假设有一个 deque 有 20 个元素，每个缓冲区是 8 个元素大小。其结构如下图：
我们看到实例中有三个缓冲区(node-buffer),可以保存24个元素，而现在deque只有20个，所以还剩4个剩余空间(图中灰色部分)。map是中控器，我们可以看到其并没有满，而且起始位置也不是在 map 首地址，这都是为了能够实现在头尾两端进行插入。再看看 start 和 finish，他们分别是 deque 的 begin()和 end() 返回的迭代器。看完迭代器、中控器、缓冲区之间的关系，我们来看看 deque 迭代器的代码：
1 //确定缓冲区大小的函数 2 inline size_t __deque_buf_size(size_t n, size_t sz) 3 { 4 return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); 5 } 6 7 template <class T, class Ref, class Ptr> 8 struct __deque_iterator { 9 //定义一些类型别名 10 typedef __deque_iterator<T, T&, T*> iterator; 11 typedef __deque_iterator<T, const T&, const T*> const_iterator; 12 static size_t buffer_size() {return __deque_buf_size(0, sizeof(T)); } 13 14 typedef random_access_iterator_tag iterator_category; 15 typedef T value_type; 16 typedef Ptr pointer; 17 typedef Ref reference; 18 typedef size_t size_type; 19 typedef ptrdiff_t difference_type; 20 typedef T** map_pointer; 21 22 typedef __deque_iterator self; 23 24 //图片中的几个指针 25 T* cur; 26 T* first; 27 T* last; 28 //中控器结点 29 map_pointer node; 30 31 //构造函数 32 __deque_iterator(T* x, map_pointer y) 33 : cur(x), first(*y), last(*y + buffer_size()), node(y) {} 34 __deque_iterator() : cur(0), first(0), last(0), node(0) {} 35 __deque_iterator(const iterator& x) 36 : cur(x.cur), first(x.first), last(x.last), node(x.node) {} 37 38 //以下全是重载 39 reference operator*() const { return *cur; } 40 pointer operator->() const { return &(operator*()); } 41 //注意这个操作符 42 difference_type operator-(const self& x) const { 43 return difference_type(buffer_size()) * (node - x.node - 1) + 44 (cur - first) + (x.last - x.cur); 45 } 46 //注意这个操作符 47 self& operator++() { 48 ++cur; 49 if (cur == last) { 50 set_node(node + 1); 51 cur = first; 52 } 53 return *this; 54 } 55 self operator++(int) { 56 self tmp = *this; 57 ++*this; 58 return tmp; 59 } 60 61 self& operator--() { 62 if (cur == first) { 63 set_node(node - 1); 64 cur = last; 65 } 66 --cur; 67 return *this; 68 } 69 self operator--(int) { 70 self tmp = *this; 71 --*this; 72 return tmp; 73 } 74 //注意这个操作符 75 self& operator+=(difference_type n) { 76 difference_type offset = n + (cur - first); 77 if (offset >= 0 && offset < difference_type(buffer_size())) 78 cur += n; 79 else { 80 difference_type node_offset = 81 offset > 0 ? offset / difference_type(buffer_size()) 82 : -difference_type((-offset - 1) / buffer_size()) - 1; 83 set_node(node + node_offset); 84 cur = first + (offset - node_offset * difference_type(buffer_size())); 85 } 86 return *this; 87 } 88 89 self operator+(difference_type n) const { 90 self tmp = *this; 91 return tmp += n; 92 } 93 94 self& operator-=(difference_type n) { return *this += -n; } 95 96 self operator-(difference_type n) const { 97 self tmp = *this; 98 return tmp -= n; 99 } 100 101 reference operator[](difference_type n) const { return *(*this + n); } 102 103 bool operator==(const self& x) const { return cur == x.cur; } 104 bool operator!=(const self& x) const { return !(*this == x); } 105 bool operator<(const self& x) const { 106 return (node == x.node) ? (cur < x.cur) : (node < x.node); 107 } 108 //用来跳一个缓冲区 109 void set_node(map_pointer new_node) { 110 node = new_node; 111 first = *new_node; 112 last = first + difference_type(buffer_size()); 113 } 114 };
代码中最重要的就是迭代器重载的那些操作符，有*,->,-,前置++,后置++,前置--,后置--,+=,+,-=,-,[],==,!=,<！可以看出 deque 的迭代器是一个 Random Access Iterator。我们要注意的几个操作符是++,--,+=,-=,+,-，这些操作都涉及到指针的移动，而deque是伪连续线性空间，在到移动到一个缓冲区尾部时，应该要用函数set_node()跳到下一个缓冲区。也就是说，我们要处理好边界情况。deque 的迭代器有些复杂，关键我们要知道 deque 的逻辑结构，才能知道迭代器操作符的的具体操作步骤。