反向迭代器的介绍与实现（超详解哦）

引言

在之前STL学习中，我们认识了迭代器：
迭代器（iterator）提供一种通用的方法，使其能够依序访问某个容器所含的各个元素，而又无需暴露该容器的内部表达方式。 有利于算法于容器的泛化。

迭代器的使用与指针类似，可以定义一个对于某个容器的迭代器变量，它指向该容器类型的对象中的某一元素。这意味着迭代器支持类似于指针的*、->、++、-- 、==等操作。

对于迭代器的实现，其实就是原生指针或原生指针的封装，再通过运算符重载完成指针的行为：
例如容器vecter与string的迭代器就是原生指针：戳我看vector模拟实现详解哦
容器list、map、set等的迭代器就是原生指针的封装：戳我看list模拟实现详解哦

介绍与使用

反向迭代器的访问方向与迭代器相反：反向迭代器的++操作使其向前前进一个元素。

rbegin()返回一个反向迭代器，指向容器的最后一个元素；
rend()返回一个反向得带起，指向容器第一个元素的前面一个位置：

在定义反向呆呆器时，与普通迭代器类似：容器类型名::reverse_iterator ：

int main()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	l.push_back(5);
	l.push_back(6);

	list<int>::iterator it = l.begin(); //正向迭代器
	while(it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	list<int>::reverse_iterator rit = l.rbegin(); //反向迭代器
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;


	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

反向迭代器本质上其实是对普通迭代器的封装：反向迭代器的++就是底层迭代器的--。
但是由于在遍历时rend()与end()是作为终止符的，rend()获取的是首元素的前一个位置，begin()获取的是首元素迭代器，所以在反向迭代器与迭代器的对应关系中，反向迭代器是向前偏移一个元素的，但是这样的偏移在使用时是感受不到的：（所以上面的图示仅仅是逻辑上的图示）

int main()
{
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	l.push_back(4);
	l.push_back(5);
	l.push_back(6);

	list<int>::reverse_iterator rit(l.end()); //使用普通迭代器的end初始化反向迭代器
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

当我们使用普通迭代器的end()初始化反向迭代器，以反向遍历时，并没有出现越界访问。这说明在封装迭代器时，对解引用的操作进行了一些调整。

实现

为防止命名冲突，我们将模拟实现的反向迭代器ReverseIterator放在我们的命名空间qqq中；

ReverseIterator是一个模板类，可以适用于各种类型的容器以及各种类型的元素。
第一个模板参数为Iterator，表示封装的底层迭代器的类型；
第二个模板参数为Ref，表示迭代器 “指向” 元素的引用；
第三个模板参数为Ptr，表示迭代器 “指向” 元素的指针。

成员变量即其底层的迭代器对象：

namespace qqq
{
	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator
	{
		Iterator _rit; 
	};
};
1
2
3
4
5
6
7
8

默认成员函数

在默认成员函数中，我们只需要实现构造函数即可。对于其余的默认成员函数，使用编译器自动生成的即可，它会去调用底层迭代器的默认成员函数，实现析构、赋值重载等操作。

构造
对于构造函数，我们实现三个重载版本：无参构造、迭代器构造与拷贝构造：

无参构造写一个接口即可，编译器会自动调用底层迭代器的默认构造：

ReverseIterator()
{}
1
2

迭代器构造参数类型为Iterator，即一个迭代器。只需要在初始化列表中，用参数初始化成员迭代器即可：

ReverseIterator(Iterator it)
	: _rit(it)
{}
1
2
3

拷贝构造参数为const ReverseIterator<Iterator, Ref, Ptr>& 为方便起见，将ReverseIterator<Iterator, Ref, Ptr> 重定义为 self。在初始化列表中，使用参数的成员初始化当前反向迭代器的成员即可：

ReverseIterator(const self& rit)
	: _rit(rit._rit)
{}
1
2
3

operator* 与 operator->

在实现operator* 与 operator-> 时，就需要对反向迭代器指向的元素向前调整一个元素，防止出现遍历时的越界：

operator* 无参，返回值为Ref，即容器中元素类型的引用（T&）：
要对底层的迭代器向前调整一个元素，一定要进行--操作，但是这样迭代器的位置也就会发生移动。所以这里先创建一个临时的迭代器temp用来进行--操作。返回--temp指向的元素即可：

Ref operator*()
{
	Iterator temp = _rit;
	return *(--temp);
}
1
2
3
4
5

operator->无参，返回值为Ptr，即容器中元素类型的指针（T*）：
与operator*相同，需要首先创建一个Iterator的临时对象temp，用来进行--操作。最后返回--temp指向元素的指针即可：

Ptr operator->()
{
	Iterator temp = _rit;
	return &(*(--temp));
}
1
2
3
4
5

这里有一个与普通迭代器相同的问题：这个函数的返回值为指针，这也就意味着通过反向迭代器访问元素的成员时要对这个指针再次-> :rit->->_a。但是，这样的形式访问又与指针的用法不一致，所以这里有一个特殊的规定，即规定需要使用rit->_a;的方式通过迭代器访问元素中的成员，以获得与原生指针相同的使用方式。

operator++ 与 operator- -

重载++：

operator++分为前置++与后置++，对于后置++增加一个不传参的int来区分：

前置++ 返回值为反向迭代器对象的引用（self&）。在函数中调用底层迭代器的前置--即可：

self& operator++()
{
	--_rit;
	return *this;
}
1
2
3
4
5

后置++ 返回的是++前的反向迭代器对象（self），所以在进行++操作前，需要先创建一个临时变量temp来记录++前的反向迭代器；
然后调用上面实现的前置++对*this进行++操作；
最后返回临时对象temp（由于这个对象是临时的，所以不能返回引用）：

self operator++(int)
{
	self temp(*this);
	++(*this);
	return temp;
}
1
2
3
4
5
6

重载- -：

operator--的实现思路与operator++一样，这里就不再赘述了：
前置--：

self& operator--()
{
	++_rit;
	return *this;
}
1
2
3
4
5

后置--：

self operator--(int)
{
	self temp(*this);
	--(*this);
	return temp;
}
1
2
3
4
5
6

operator== 与 operator!=

operator==与operator!=的参数类型为const self& 返回值为bool：
判断反向迭代器的相同与否，就是在判断他们底层迭代器的相同与否，所以只需要调用底层迭代器的== 与 != 重载比较参数对象的成员与当前对象的成员即可：

bool operator==(const self& it)
{
	return _rit == it._rit;
}
bool operator!=(const self& it)
{
	return _rit != it._rit;
}
1
2
3
4
5
6
7
8

源码概览

namespace qqq
{
	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> self;

		Iterator _rit;

		ReverseIterator()
		{}
		ReverseIterator(Iterator it)
			: _rit(it)
		{}
		ReverseIterator(const self& rit)
			: _rit(rit._rit)
		{}

		Ref operator*()
		{
			Iterator temp = _rit;
			return *(--temp);
		}
		Ptr operator->()
		{
			Iterator temp = _rit;
			return &(*(--temp));
		}


		self& operator++()
		{
			--_rit;
			return *this;
		}
		self operator++(int)
		{
			self temp(*this);
			++(*this);
			return temp;
		}
		self& operator--()
		{
			++_rit;
			return *this;
		}
		self operator--(int)
		{
			self temp(*this);
			--(*this);
			return temp;
		}


		bool operator==(const self& it)
		{
			return _rit == it._rit;
		}
		bool operator!=(const self& it)
		{
			return _rit != it._rit;
		}
	};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

在模拟实现的list中测试ReverseIterator

实现完反向迭代器后，我们可以在直线实现过的list中来测试我们的ReverseIterator：

首先在list中进行相关的命名：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
1
2
3
4

使用时依旧类型名::reverse_iterator 定义对象即可：

namespace qqq
{
	void testfunc()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_back(4);
		l.push_back(5);

		list<int>::reverse_iterator rit(l.end()); //使用end构造rbegin
		list<int>::reverse_iterator rit2(rit); //这里进行了拷贝构造
		while (rit2 != l.rend())
		{
			cout << *rit2 << " ";
			rit2++; //直接测试后置++，后置没问题前置一定没问题
		}
	}
};

int main()
{
	qqq::testfunc();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

到此，关于反向迭代器的知识就介绍完了
相对于简单的实现，对于迭代器的理解才是重中之重

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出

如果本文对你有帮助，希望一键三连哦

希望与大家共同进步哦