反向迭代器

前面在vector和list的模拟实现中都有讲到正向迭代器，今天我们就来讲解一下反向迭代器的思想和模拟实现，在某些场景下还是很实用的，下面正文直接开始。

文章目录：

反向迭代器
- 1. 反向迭代器结构
- 2. 反向迭代器实现
- - 2.1 多参数模板
  - 2.2 对称思想
  - 2.3 完整代码
- 3. 反向迭代器vector应用
- 4. 反向迭代器list引用

1. 反向迭代器结构

反向迭代器reverse_iterator用于反向遍历容器，它也是由一个类来封装的

template<class Iterator>
struct __reverse_iterator
{Iterator _cur;	//正向迭代器类做成员变量__reverse_iterator(Iterator cur) //构造正向迭代器:_cur(cur){}//...
};

STL库中反向迭代器的设计讲究完美的对称性，rbegin() 指向最后一个有效元素的下一个位置，rend() 指向第一个有效元素，与正向迭代器的指针位置刚好相反

拿vector对象举个例子

Self& operator++()
{--_cur; //正反迭代器，++，--反向操作return *this;
}Self& operator--()
{++_cur;return *this;
}

2. 反向迭代器实现

反向迭代器的实现主要还是依于对正向迭代器的复用，外加了一点小细节思想，这里我们实现的依旧是简易版本

2.1 多参数模板

前面在模拟实现list时，运用了多参数模板来解决const对象代码冗余问题，在反向迭代器的实现中也运用了相同原理，通过对形参传递不同的对象，变换为不同的迭代器

template<class Iterator, class Ref, class Ptr>
struct __reverse_iterator
{//...
};

其中Ref表示引用对象，Ptr表示指针对象

2.2 对称思想

STL大佬在设计反向迭代器时，为了追求与正向迭代器的对称，将首尾指针得到指向反向保持一致，如上图，即rbegin()在end()位置，rend()在begin()位置

在这样的设计下，rbegin()和rend()的实现就可以直接对应复用了，而operator*()返回的就不是当前所指向的对象，而是成了上一个对象

reverse_iterator rbegin() 
{ reverse_iterator(end()); 
}reverse_iterator rend() 
{ reverse_iterator(begin()); 
}

operator*()

Ref operator*()
{Iterator tmp = _cur;return *--tmp;	//返回上一个对象
}

2.3 完整代码

至于其他的实现都是复用的正向迭代器，比较简单，这里直接上完整代码，相信大佬，们一看就能明白

#pragma once
namespace Sakura
{template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{typedef __reverse_iterator<Iterator, Ref, Ptr> self; //重命名Iterator _cur; //正向迭代器类做成员变量__reverse_iterator(Iterator cur) //构造正向迭代器:_cur(cur){}Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){return &(operator*());}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);}};
}

3. 反向迭代器vector应用

在 vector 类中，定义出反向迭代器所需的函数即可

template<class T>
class vector
{
public://反向迭代器typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;typedef _reverse_iterator<iterator, const T&, const T*> 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());}//...
};

4. 反向迭代器list引用

在 list 类中，定义出反向迭代器所需的函数即可

template<class T>
class list
{
public://反向迭代器typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<const_iterator, const T&, const T*> 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()); }//...
};