C++：反向迭代器

一、什么是反向迭代器？

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

1.1 反向迭代器与正向迭代器的关系

反向迭代器其实是由正向迭代器适配出来的，它的++,--与正向迭代器相反，它的rbegin是正向迭代器的end，它的rend是正向迭代器的begin，反向迭代器与正向迭代器是镜面对称的。

反向迭代器也是一个模板，传list的迭代器，就是list的反向迭代器，传vector的迭代器就是vector的反向迭代器。

1.2 反向迭代器实现原理

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，它的rbegin是正向迭代器的end，它的rend是正向迭代器的begin，因此它的解引用需要返回当前迭代器--的迭代器解引用。

1.3 反向迭代器代码

这里为了能有返回值，也要传Ref和Ptr

namespace bit
{
	template<class T, class Ref, class Ptr>
	struct ReverseIterator
	{
		typedef ReverseIterator<T, Ref, Ptr> Self;

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

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

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

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

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

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

	};
}

二、list中的反向迭代器

2.1 定义

首先要typedef出来反向迭代器，像这样：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

typedef ReverseIterator<T, T&, T*> reverse_iterator;
typedef ReverseIterator<T, const T&, const T*> const_reverse_iterator;

接着还要提供对应rbegin与rend的获取:

iterator begin()
{
	//return _head->_next;
	return iterator(_head->_next);
}

iterator end()
{
	return _head;
	//return iterator(_head);
}

const_iterator begin() const
{
	//return _head->_next;
	return const_iterator(_head->_next);
}

const_iterator end() const
{
	return _head;
	//return const_iterator(_head);
}

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

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

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

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

2.2 使用

反向迭代器就像这样使用：

	void test_list()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int>::reverse_iterator rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			++rit;
		}
		cout << endl;
	}
}

三、vector中的反向迭代器

3.1 定义

typedef T* iterator;
typedef const T* const_iterator;

//这里都是一模一样的，不过传的迭代器不一样罢了，这就是模板的魅力！
//编译器会帮我们完成工作！！！
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

接着还要提供对应rbegin与rend的获取:

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

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

iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

const_iterator begin() const
{
	return _start;
}

const_iterator end() const
{
	return _finish;
}

3.2 使用

它的使用从表面上看和list的一模一样

	void test_vector1()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int>::reverse_iterator rit = v1.rbegin();
		while (rit != v1.rend())
		{
			cout << *rit << " ";
			++rit;
		}
		cout << endl;
	}
}

总结

list 和 vector 的反向迭代器表面上看起来使用相同，但它们背后的实现其实有较大的差异。以下是对 list 和 vector 反向迭代器的区别总结：

1. 容器结构的不同

   • vector：vector 是连续存储的动态数组，所有元素在内存中是连续排列的，反向迭代器在 vector 中只需调整指针的偏移量。
   • list：list 是一个双向链表，元素分散在不同的内存位置，反向迭代器必须沿着链表的指针进行跳转，而不是简单的指针加减操作。

2. 访问方式的不同

   • vector 反向迭代器：vector 允许随机访问，因此反向迭代器可以通过简单的指针运算快速定位任意元素，比如通过 rit + n 访问偏移 n 的元素。
   • list 反向迭代器：list 不支持随机访问，因此不能通过 + 或 - 来偏移反向迭代器，只能通过逐个遍历（++ 或 --）来前进或后退。

3. 底层机制的不同

   • vector 反向迭代器：在 vector 中，反向迭代器其实是基于普通迭代器的简单封装，它只是改变了普通迭代器的前进和后退方向。rbegin() 返回的是指向最后一个元素的迭代器，而 rend() 返回的是第一个元素前面的虚拟位置。
   • list 反向迭代器：在 list 中，反向迭代器是通过链表的前驱指针来完成反向遍历。每次前进时，反向迭代器都会通过前驱指针找到前一个元素的位置，因此遍历时比 vector 复杂得多。

因此，虽然表面上看起来一模一样，实际上编译器替我们完成了复写一遍的行为，这就是模板和适配器造就的迭代器！

谢谢大家！！！🤞🤞🤞💖💖💖☆*: .｡. o(≧▽≦)o .｡.:*☆