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

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

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

代码语言：javascript复制

	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		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;
		}
     	bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

在list类里面这样声明：

代码语言：javascript复制

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

    // ... 省略其他代码 ...
};

为了实现一个反向迭代器，需要创建一个新的迭代器类，该类的增加（operator ）和减少（operator--）操作符与标准迭代器的行为相反。也就是说，对于一个反向迭代器，operator 将会移动到前一个元素（_prev），而operator--将会移动到下一个元素（_next）。这意味着它将沿着相反的方向遍历列表。以下是如何定义一个ListIterator的反向版本的示例：

代码语言：javascript复制

template<class T, class Ref, class Ptr>
struct ReverseListIterator
{
    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;
    }

    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }

    bool operator==(const Self& it)
    {
        return _node == it._node;
    }
};

这里的ReverseListIterator和原来的ListIterator很相似，区别就在于迭代器前进( )和后退(--)的方向相反。

通常情况下，标准库容器（比如list或vector）会有.rbegin()和.rend()方法来获取反向迭代器的开始和结束。为了实现类似的功能，需要在容器类中添加生成ReverseListIterator实例的方法：

代码语言：javascript复制

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

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

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

2.适配实现反向迭代器

代码语言：javascript复制

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

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

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

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

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

代码语言：javascript复制

template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator
	{
		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;
		}
		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}
	};
}

在这个模板代码示例中，ReverseIterator 类型是一个反向迭代器，它是基于提供的正向迭代器类型 Iterator 来实现的。当使用 ReverseIterator 时，编译器将会按照模板代码的描述来生成一个特定于所使用迭代器类型的类实例。以下是各个操作符和成员函数的作用，以及编译器如何处理它们：

1. 构造函数：

代码语言：javascript复制

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

构造函数接收一个正向迭代器 it 并存储在 _it 成员变量中。编译器处理构造函数的方式与普通的构造函数相同

2. 解引用操作符 operator*：

代码语言：javascript复制

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

这个操作符创建了 _it 的一个副本 tmp，然后对 tmp 应用前置自减 operator--，将其后移一位，然后解引用。对于反向迭代器而言，这意味着解引用的是当前位置之前的元素。

编译器生成了一个临时变量 tmp，调用了对应类型 Iterator 的前置自减 operator--，并调用了解引用 operator*。注意，由于这是一个底层实现细节，编译器有权优化这些步骤（如通过直接调用必要的函数）以优化性能

3. 成员访问操作符 operator->：

代码语言：javascript复制

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

这个操作符通过调用解引用操作符 operator* 来获取值的引用，然后取地址得到对应元素的指针

编译器会生成代码，使用上面定义的解引用操作符 operator* 来获取一个引用，然后获取该引用的地址

4. 前置自增操作符 operator ：

代码语言：javascript复制

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

对于反向迭代器来说，“自增”实际上会使内部正向迭代器 _it 自减。编译器调用 _it 的前置自减操作符 operator-- 并返回 *this 实现反向迭代器的自增操作

5. 前置自减操作符 operator--：

代码语言：javascript复制

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

对于反向迭代器来说，“自减”实际上会使内部正向迭代器 _it 自增。编译器调用 _it 的前置自增操作符 operator 并返回 *this 实现反向迭代器的自减操作

6. 不等于操作符 operator!=：

代码语言：javascript复制

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

这个操作符比较两个反向迭代器，实际上它比较了内部正向迭代器 _it 是否不相等。

编译器根据 Iterator 类型生成了比较操作，这通常是调用 Iterator 给定的 operator!=

总结编译器处理：

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

编写一个通用的反向迭代器类模板可以省去为每个容器单独定义反向迭代器的麻烦。C 标准库中的 std::reverse_iterator 就是这样一个通用的反向迭代器适配器。它接收一个正向迭代器作为模板参数，反转了其遍历方向，使得利用正向迭代器的容器可以很容易地提供反向迭代能力

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

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

代码语言：javascript复制

std::vector<int> vec = {1, 2, 3, 4, 5};
ReverseIterator<std::vector<int>::iterator, int&, int*> rIt(vec.end());

// 使用反向迭代器遍历 vector
for (; rIt != ReverseIterator<std::vector<int>::iterator, int&, int*>(vec.begin());   rIt) {
    std::cout << *rIt << " ";
}

在这段代码中，ReverseIterator 对 std::vector<int>::iterator 类型进行了实例化。实际上，因为 std::reverse_iterator 已经存在于标准库中，通常不需要自己写这个，并且可以直接这样使用：

代码语言：javascript复制

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

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

return self 编译器 c++ 容器

0 人点赞