STL-reverse_iterator 反向迭代器

回顾

对于STL中的容器，迭代器(iterator)是很重要的部分，同时迭代器也是STL六大组件之一，在之前我们实现vector和list中，我们已经对于迭代器有了初步的认识，为什么设计迭代器？ 就是为了能像数组中的指针一样，可以通过++ , -- 的操作遍历数据。

比如说vector，它本身底层就是一个数组，一串连续的数据，而它的迭代器就是原生指针。

而list，它并不是连续存储的空间，但是可以通过每个节点的_next指针找到下一个节点（数据），而它的迭代器是一个类，类的底层成员是节点指针，再重载++,--操作，就能像vector一样遍历数据。

反向迭代器（reverse_iterator）

反向迭代器，就是迭代器（正向迭代器）的反过来遍历，从尾部向头部遍历，这个不难理解。

正向迭代器，我们知道，它是一个左闭右开的区间，那么反向迭代器，是怎么样的一个区间呢？

这个问题我们先放着，大家可以思考一会。

如果我们要实现一个反向迭代器，是否又要写一个反向迭代器的实现？这是否会与我们实现的正向迭代器的代码大幅度相似？ 对于STL来说，太多重复的代码会显得很臃肿浪费，那么STL是如何实现反向迭代器的呢？

STL对于反向迭代器的实现，采用了适配器的做法，对正向迭代器进行了封装。而对于适配器，我们已经了解了stack，queue等。所以，反向迭代器，不仅仅是迭代器，还是适配器！

反向迭代器作为适配器适配在什么地方？STL让能支持逆序遍历的容器都能把各自的正向迭代器适配出各自的反向迭代器！

template<typename Iterator , typename Ref, typename Ptr>
	struct __reverse_iterator {
		typedef __reverse_iterator RIterator;
 
		Iterator _data;    //成员变量
 
        __reverse_iterator(Iterator it)
			:_data(it)
		{}
 
	};

这里模版的第一个参数是你需要适配的正向迭代器，第二个和第三个参数与正向迭代器一致，是用来识别判断你这个迭代器是否是const的。

怎么反向遍历？不过是把正向迭代器的++操作，替换成了--操作！

RIterator& operator++()
{
	--_data;
	return *this;
}
 
RIterator operator++(int)
{
	__reverse_iterator tmp(_data);
	--_data;
	return tmp;
}
 
RIterator& operator--()
{
	++_data;
	return *this;
}
 
RIterator operator--(int)
{
	__reverse_iterator tmp(_data);
	++_data;
	return tmp;
}

反向迭代器区间

那么已经知道了反向迭代器的运作原理，是否对于它的遍历区间有了一些猜想？

而STL是这样设计的

 以vector为例

Ref operator*()
{
	Iterator tmp = _data;
	return *(--tmp);
}
 
Ptr operator->()    //针对自定义类型指针访问成员
{
	return &(operator*());
}
 
bool operator!=(const RIterator& it)
{
	return _data != it._data;
}

RIterator rbegin()
{
	return RIterator(end());
}
 
const_RIterator rbegin() const
{
	return RIterator(end());
}
 
RIterator rend()
{
	return RIterator(begin());
}
 
const_RIterator rend() const
{
	return RIterator(begin());
}

而反向迭代器的遍历则是这样

vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(3);
v1.push_back(3);
v1.push_back(6);
v1.push_back(4);
vector<int>::RIterator Rit = v1.rbegin();
while (Rit != v1.rend())
{
	cout << *Rit << " ";
	++Rit;
}
cout << endl;

反向迭代器不仅仅是迭代器，还是一个适配器，写一个反向迭代器就能造福许多容器，为什么是许多而不是全部？  因为有些容器的迭代器不支持--操作，就比如单向链表，不支持逆序遍历。