文章目录

• 反向迭代器和正向迭代器
• 1. 正向迭代器
• • 1.1 list结构
  • 1.2 list代码框架
  • 1.3 代码结合框架
  • • 1.3.0 list_node类
    • 1.3.1 list类
    • 1.3.2 list_iterator类
• 2. 反向迭代器
• • 2.1 引入
  • 2.2 反向迭代器结构
  • 2.3 代码结合框架
  • • 2.3.1 list反向迭代器的分析
    • 2.3.2 vector反向迭代器的分析

反向迭代器和正向迭代器

1. 正向迭代器

1.1 list结构

先来看list(双向带头链表)：从结构到框架到代码

这是基本的结构，双向指向，_guard哨兵位头节点指向尾部，尾部指向 _guard哨兵位头节点。

1.2 list代码框架

这里list类是主类（链表类），成员变量是_guard哨兵位头节点。list_node类是节点类，其成员变量有 _prev指针和 _next指针分别用来指向前一个节点和后一个节点，也有一个用来存储数值的 _val成员变量。 list_iterator类是迭代器类，主要功能是拿到节点来对其进程解引用和访问数据操作，具体细节后面讲述。

1.3 代码结合框架

1.3.0 list_node类

template 
struct list_node
{list_node* _prev;list_node* _next;T _val;list_node(const T& val = T()) :_prev(nullptr), _next(nullptr), _val(val){}
};

1.3.1 list类

template 
class list
{typedef list_node node; //节点类public:typedef list_iterator iterator; //迭代器类typedef list_iterator const_iterator;typedef list_reverse_iterator reverse_iterator; //反向迭代器类typedef list_reverse_iterator const_reverse_iterator;iterator begin(){return iterator(_guard->_next);}iterator end(){return iterator(_guard);}const_iterator begin() const{return const_iterator(_guard->_next);}const_iterator end() const{return const_iterator(_guard);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}list(){_guard = new node;_guard->_next = _guard;_guard->_prev = _guard;}void insert(iterator pos, const T& val){node* cur = pos._node;node* prev = pos._node->_prev;node* new_node = new node(val);prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}void erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node; //迭代器失效}void push_back(const T& val){insert(end(), val);}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:node* _guard; //哨兵位头节点};

list类中包含list_node类和list_iterator类和list_reverse_iterator类。这里上面结构少了一个反向迭代器，但是不要急，下面会依依讲解，这里就不会操作进行说明，下面来看正向迭代器：

这里的end()也就是对_guard的再次封装，begin()也就是对 _guard-> _next的再次封装。

1.3.2 list_iterator类

template 
struct list_iterator 
{typedef list_node node;typedef list_iterator self;node* _node; //成员变量list_iterator(node* node) :_node(node) {}reference operator*(){return _node->_val; //const是否修饰}pointer operator->(){return &_node->_val; //const是否修饰}self& operator++() //前置++{_node = _node->_next;return *this; }self operator++(int) //后置++{self tmp(*this);_node = _node->_next;return tmp;}self& operator--() //前置--{_node = _node->_prev;return *this;}self operator--(int) //后置--{self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};

这里有个list_iterator(node* node)构造函数：这里这个构造函数非常关键，因为构造函数都是对成员变量做初始化，这个初始化这个成员变量_node，就是对 _guard和 _guard-> _next的封装。

上面就证明了_node 就是对 _guard-> _next和 _guard的再次封装，拿begin()这个list类的成员函数来说，会调用 list_iterator(node* node)的list_iterator类的构造函数，对 _guard-> _next进行指针赋值，让其list_iterator类的 _node成员变量指向 _guard-> _next，也就是这样 _node = _guard-> _next; 现在再来看其迭代器中的操作函数，比如operator*()去调用时，会指向return _node-> _val；换句话说就是 return _guard-> _next-> _val；再来看operator->()操作函数，调用时会执行return & _node-> _val； 换句话说就是 return & _guard-> _next-> _val; 再来看前置++操作函数，调用时会执行 _node = _node-> _next; 换句换说就是 _guard-> _next = _guard-> _next-> _next;这就是怎么来理解迭代器，我所理解的就是对指针进行封装，然后对封装后的指针进行操作，同时某种操作会改变指针的指向。

2. 反向迭代器

2.1 引入

上面我们所看到的是正向迭代器，我们可不可以直接在原有基础上来改变一下就变成了反向迭代器呢？

template 
struct list_reverse_iterator 
{typedef list_node node;typedef list_reverse_iterator self;node* _node; //成员变量list_reverse_iterator(node* node) :_node(node) {}reference operator*(){return _node->_val; //const是否修饰}pointer operator->(){return &_node->_val; //const是否修饰}self& operator++() //前置++{_node = _node->_prev;return *this; }self operator++(int) //后置++{self tmp(*this);_node = _node->_prev;return tmp;}self& operator--() //前置--{_node = _node->_next;return *this;}self operator--(int) //后置--{self tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};

这样写也可以通过list的测试，这里有两点是不好的：1. 代码冗余，前面要用到正向迭代器，后面还要手动改成反向迭代器再次使用，关键还需要手动就很烦，2.仅仅适用于list类，假设vector类的反向迭代器呢，怎么实现，原生指针不需要所以这里怎么实现呢，能实现也需要手动再次搓一次就很烦，有没有一种通用的反向迭代器呢，我就很懒，这里就不想手动，其实可以，来看看STL设计者大佬的思路吧：通过对正向迭代器复用来得到反向迭代器，这里还是先拿list来举例，首先来看代码：

template 
struct list_reverse_iterator
{typedef list_reverse_iterator Self;iterator _cur; //成员变量list_reverse_iterator(iterator self):_cur(self){}reference operator*(){iterator tmp = _cur;--tmp;return *tmp;}pointer operator->(){return &_cur->_val;}Self& operator++(){--_cur;return *this;}Self operator++(int){Self tmp(*this);--_cur;return tmp;}Self& operator--(){++_cur;return *this;}Self operator--(int){Self tmp(*this);++_cur;return tmp;}bool operator!=(const Self& s){return _cur != s._cur;}bool operator==(const Self& s){return _cur == s._cur;}
};

list_reverse_iterator类中有成员变量iterator _cur， 这里通过上面正向迭代器的描述很容易想到，这里的 _cur就是对正向迭代器的再次封装，通过直接控制 _cur来间接控制被封装的迭代器。这里代码给出了，我们先来讲讲反向迭代器的设计。

2.2 反向迭代器结构

这里STL大佬设计的是讲究的对称性，所以实现也是依据这个结构来实现的。

2.3 代码结合框架

2.3.1 list反向迭代器的分析

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lFuaUXnW-1679060406548)(https://jinyinhan.oss-cn-beijing.aliyuncs.com/QQ截图20230317211202.png)]

这里就很清晰的理清了调用关系，下面用文字梳理一边：首先rbegin()会调用end()拿到一个迭代器类型的封装节点后的变量，然后调用reverse_iterator的构造函数，通过构造函数，对原有的迭代器进行的二次封装成了 _cur;然后操作都是对 _cur来进行操作，比如完成解引用(*)运算符重载操作：首先tmp = _cur; --tmp会去调用list_iterator类(iterator类)的前置–运算符重载， *tmp直接调用list_iterator类的解引用( *)运算符重载，最后返回 _node-> _val的引用形式返回。下面几个操作也一样的，都是对 _cur迭代器封装，通过操作迭代器内部的节点来得到对应的结果。*注意：上面reference operator ()函数中应该是return & _node-> _val;而不是return _node-> _val;

2.3.2 vector反向迭代器的分析

template 
typedef T* iterator;
typedef const T* const_iterator;
typedef vector_reverse_iterator reverse_iterator;
typedef vector_reverse_iterator const_reverse_iterator;reverse_iterator rbegin()
{return reverse_iterator(end());
}reverse_iterator rend()
{return reverse_iterator(begin());
}const_reverse_iterator rbegin() const
{return const_reverse_iterator(end());
}const_reverse_iterator rend() const
{return const_reverse_iterator(begin());
}

下面就拿rebgin()函数的调用流程来理解反向迭代器：

原生指针被封装后如此简单，并没有list自定义类型复杂，理解基本的vector反向迭代器再来回头看看list反向迭代器就能知道它的动作行为是什么了。反向迭代器需要注意一下模板参数传递的有正向迭代器。