【c++】反向迭代器的探究实现

🔥个人主页：Quitecoder

🔥专栏：c++笔记仓

在list中我们实现了正向的迭代器，学习完优先级队列后，我们也对适配器模式有了一个深刻的理解，这篇文章基于这种模式下，实现各类容器的反向迭代器

目录

1.引入：list的反向迭代器

首先来回顾一下我们实现list的正向迭代器：

template<classT,classRef,classPtr>structListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;

        Node* _node;ListIterator(Node* node):_node(node){}// *it//T& operator*()
        Ref operator*(){return _node->_data;}// it->//T* operator->()
        Ptr operator->(){return&_node->_data;}// ++it
        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;}booloperator!=(const Self& it){return _node != it._node;}booloperator==(const Self& it){return _node == it._node;}};

在list类里面这样声明：

template<classT>classlist{// ... 省略其他代码 ...public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;// ... 省略其他代码 ...};

为了实现一个反向迭代器，需要创建一个新的迭代器类，该类的增加（

operator++

）和减少（

operator--

）操作符与标准迭代器的行为相反。也就是说，对于一个反向迭代器，

operator++

将会移动到前一个元素（

_prev

），而

operator--

将会移动到下一个元素（

_next

）。这意味着它将沿着相反的方向遍历列表。以下是如何定义一个

ListIterator

的反向版本的示例：

template<classT,classRef,classPtr>structReverseListIterator{typedef ListNode<T> Node;typedef ReverseListIterator<T, Ref, Ptr> Self;

    Node* _node;ReverseListIterator(Node* node):_node(node){}// 解引用操作符
    Ref operator*(){return _node->_data;}// 成员访问操作符
    Ptr operator->(){return&_node->_data;}// 前置自增操作符，移动到前一个元素
    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;}booloperator!=(const Self& it){return _node != it._node;}booloperator==(const Self& it){return _node == it._node;}};

这里的

ReverseListIterator

和原来的

ListIterator

很相似，**区别就在于迭代器前进(

++

)和后退(

--

)的方向相反**。

通常情况下，标准库容器（比如

list

或

vector

）会有

.rbegin()

和

.rend()

方法来获取反向迭代器的开始和结束。为了实现类似的功能，需要在容器类中添加生成

ReverseListIterator

实例的方法：

typedef ReverseListIterator<T, T&, T*> reverse_iterator;typedef ReverseListIterator<T,const T&, constT*>const_reverse_iterator;

reverse_iterator rbegin(){returnreverse_iterator(end());}

reverse_iterator rend(){returnreverse_iterator(begin());}

2.适配实现反向迭代器

typedef ReverseListIterator<T, T&, T*> reverse_iterator;typedef ReverseListIterator<T,const T&, constT*>const_reverse_iterator;

reverse_iterator rbegin(){returnreverse_iterator(end());}

reverse_iterator rend(){returnreverse_iterator(begin());}

这种实现只是对原有类的一个修改，只是对list这个反向迭代器的实现，我们下面来实现另一种适配模式，我传入某一容器的正向迭代器来适配生成反向迭代器

比如传入List类的正向迭代器，适配出List的反向迭代器，传入vector正向迭代器，适配出vector的反向迭代器

template<classIterator,classRef,classPtr>structReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;
        Iterator _it;ReverseIterator(Iterator it):_it(it){}
        Ref operator*(){
            Iterator tmp = _it;return*(--tmp);}
        Ptr operator->(){//return _it->;//return _it.operator->();return&(operator*());}
        Self&operator++(){--_it;return*this;}
        Self&operator--(){++_it;return*this;}booloperator!=(const Self& s){return _it != s._it;}};}

在这个模板代码示例中，

ReverseIterator

类型是一个反向迭代器，**它是基于提供的正向迭代器类型

Iterator

来实现的。当使用

ReverseIterator

时，编译器将会按照模板代码的描述来生成一个特定于所使用迭代器类型的类实例**。以下是各个操作符和成员函数的作用，以及编译器如何处理它们：

1. 构造函数：

ReverseIterator(Iterator it):_it(it){}

构造函数接收一个正向迭代器

it

并存储在

_it

成员变量中。编译器处理构造函数的方式与普通的构造函数相同

2. 解引用操作符

operator*

：

Ref operator*(){
    Iterator tmp = _it;return*(--tmp);}

这个操作符创建了

_it

的一个副本

tmp

，然后对

tmp

应用前置自减

operator--

，将其后移一位，然后解引用。对于反向迭代器而言，这意味着解引用的是当前位置之前的元素。

编译器生成了一个临时变量

tmp

，调用了对应类型

Iterator

的前置自减

operator--

，并调用了解引用

operator*

。注意，由于这是一个底层实现细节，编译器有权优化这些步骤（如通过直接调用必要的函数）以优化性能

3. 成员访问操作符

operator->

：

Ptr operator->(){return&(operator*());}

这个操作符通过调用解引用操作符

operator*

来获取值的引用，然后取地址得到对应元素的指针

编译器会生成代码，使用上面定义的解引用操作符

operator*

来获取一个引用，然后获取该引用的地址

4. 前置自增操作符

operator++

：

Self&operator++(){--_it;return*this;}

对于反向迭代器来说，“自增”实际上会使内部正向迭代器

_it

自减。编译器调用

_it

的前置自减操作符

operator--

并返回

*this

实现反向迭代器的自增操作

5. 前置自减操作符

operator--

：

Self&operator--(){++_it;return*this;}

对于反向迭代器来说，“自减”实际上会使内部正向迭代器

_it

自增。编译器调用

_it

的前置自增操作符

operator++

并返回

*this

实现反向迭代器的自减操作

6. 不等于操作符

operator!=

：

booloperator!=(const Self& s){return _it != s._it;}

这个操作符比较两个反向迭代器，实际上它比较了内部正向迭代器

_it

是否不相等。

编译器根据

Iterator

类型生成了比较操作，这通常是调用

Iterator

给定的

operator!=

总结编译器处理：

本来每个容器都要写一个反向迭代器的累，但是自己写，太费劲了 本质写一个反向迭代器的类模板，给编译器传不同的容器的正向迭代器实例化，编译器帮助我们实例化出各种容器的对应反向迭代器

**编写一个通用的反向迭代器类模板可以省去为每个容器单独定义反向迭代器的麻烦。C++ 标准库中的

std::reverse_iterator

就是这样一个通用的反向迭代器适配器。它接收一个正向迭代器作为模板参数，反转了其遍历方向，使得利用正向迭代器的容器可以很容易地提供反向迭代能力**

使用类模板可以使得编译器根据你向模板传递的不同正向迭代器类型，为每个具体的容器类型生成对应的反向迭代器实例。这个通用反向迭代器适配器遵循了一种 编写一次，处处使用的原则，极大地提高了代码的复用性

例如，在

ReverseIterator

模板中，只要定义一次，就可以用来产生各种支持正向迭代器的容器的反向迭代器，如下所示：

std::vector<int> vec ={1,2,3,4,5};
ReverseIterator<std::vector<int>::iterator,int&,int*>rIt(vec.end());// 使用反向迭代器遍历 vectorfor(; rIt !=ReverseIterator<std::vector<int>::iterator,int&,int*>(vec.begin());++rIt){
    std::cout <<*rIt <<" ";}

在这段代码中，**

ReverseIterator

对

std::vector<int>::iterator

类型进行了实例化。实际上，因为

std::reverse_iterator

已经存在于标准库中，通常不需要自己写这个，并且可以直接这样使用**：

std::vector<int>::reverse_iterator rIt = vec.rbegin();// 标准库已经提供 begin 和 end 了，不需要我们手动构建 ReverseIterator 实例for(; rIt != vec.rend();++rIt){
    std::cout <<*rIt <<" ";}

本篇文章到此结束！！感谢大家阅读！！