【C++】开始了解反向迭代器

叫我龙翔

发布于 2024-04-20 09:57:03

940

发布于 2024-04-20 09:57:03

1 前言

在复刻STL中的list容器时，我们首次采用了类封装的方式来构建迭代器，以此实现迭代器的递增、递减和元素访问功能。然而，当我们面临实现反向迭代器的需求时，是否需要重头开始，再次进行类的封装呢？

显然这种做法并非必要（不然就要手搓无数个反向迭代器了）。因为反向迭代器与正向迭代器在功能上存在高度一致性，唯一的区别在于它们在容器中的移动方向相反。因此，我们可以采用适配器设计模式，对现有的正向迭代器进行二次封装，以此满足反向迭代器的需求。

通过引入适配器，我们不仅可以避免重复造轮子的工作，还能够提升代码的复用性和简洁性。这种设计模式的应用，使得我们能够在保持代码高效和可维护性的同时，轻松实现反向迭代器的功能。

2 反向迭代器

我们先来看源码中是如何实现的：

template <class RandomAccessIterator, class T, class Reference = T&,
          class Distance = ptrdiff_t> 
#else
template <class RandomAccessIterator, class T, class Reference,
          class Distance> 
#endif
class reverse_iterator {
  typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
        self;
protected:
  RandomAccessIterator current;
public:
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef Reference                  reference;
 }
；

其想要通过提供的正向迭代器实现所有容器的反向迭代器。

这是链表中的反向迭代器：

  typedef reverse_bidirectional_iterator<const_iterator, value_type,
  const_reference, difference_type>
  const_reverse_iterator;
  typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  difference_type>
  reverse_iterator;

给链表的正向迭代器，就给出链表的反向迭代器。

接下来我们也来实现一下自己的反向迭代器：

3 复刻反向迭代器

通过对反向迭代器的设计模式的了解，我们可以大致写一个框架：

namespace bit
{
	// 适配器 -- 复用
	//给谁的正向迭代器就产生谁的正向迭代器
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		//简化书写
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
		//构造函数
		Reverse_iterator(Iterator it)
			:_it(it)
		{}
		//实例化一个正向迭代器
		Iterator _it;
	};
}

反向迭代器与正向迭代器在功能上相似，都用于遍历容器中的元素。然而，它们在操作方向上存在显著差异：

正向迭代器通过++运算符向前移动，而反向迭代器则通过–运算符向后移动。

实现反向迭代器的基本方法是通过编写一个类模板，该模板会被编译器用来生成具体容器对应的迭代器实例。在这个过程中，编译器负责实例化这些迭代器，从而提供一种便捷的方式来反向遍历容器中的元素。

3.1 加减操作

根据反向迭代器的性质，我们可以借助正向迭代器的函数来实现反向迭代器的加减操作。

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

		Self& operator++(int)
		{
			Self tmp = _it;
			--_it;
			return tmp;
		}
		//前置
		Self& operator--()
		{
			++_it;
			return *this;
		}
		//后置
		Self& operator--(int)
		{
			Self tmp = _it;
			++_it;
			return tmp;
		}

通过反向使用正向迭代器的加减操作，反向加就是正向减，反向减就是正向加。

3.2 判断操作

对于反向迭代器的== !=操作实质上也就是其封装的正向迭代器的比较：

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

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

这样比较就可以了。

3.3 访问操作

这个访问操作是由说法的：

		Ref operator*()
		{
			Iterator tmp = _it;
			return  *(--tmp);//下面进行解释
		}
		//会进行省略->
		Ptr operator->()
		{
			return &(operator*());
		}

为什么这里的访问要有--操作？？？因为为了与正向迭代器对称，反向迭代器的开始位置并不是结尾，而是哨兵位。

下面这种可以直接使用已有的end() , begin()函数进行复用，增加代码可读性。所以对应的访问方式就要减一再访问。效果其实两种区别不大，但是第二种的代码更加简洁。

4 链表的反向迭代器

我们来在链表里实现一下反向迭代器(记得包含对应头文件)：首先先实例化两种反向迭代器：

typedef Reverse_iterator<iterator , T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator , const T&, const T*> const_reverse_iterator;

接着通过相应的rend() rbegin()函数：

reverse_iterator rbegin()  { return reverse_iterator(_head); }
reverse_iterator rend()  { return reverse_iterator(_head->_next); }

const_reverse_iterator rbegin() const { return const_reverse_iterator(_head); }
const_reverse_iterator rend() const { return const_reverse_iterator(_head->_next); }

这样就可以访问了：

#include"List.h"
#include<iostream>

using namespace bit;
using namespace std;

int main()
{
	list<int> lt ;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	list<int>::reverse_iterator rit = lt.rbegin();

	while (rit != lt.rend())
	{
		cout << (*rit) << " ";
		rit++;
	}

	return 0;
}

来看效果：