用正向迭代器封装实现反向迭代器

如何用正向迭代器封装出反向迭代器

概述

STL中有很多容器，例如vector，list，string，set，map它们都是支持迭代器的，其中迭代器有包括正向迭代器和反向迭代器，本文主要就是介绍如何用自己实现的正向迭代器来封装实现反向迭代器。

迭代器遍历容器的过程

正向迭代器

这里以上篇文章的list为例讲解，上文介绍了list的正向迭代器的实现，是将其封装为一个类在里实现迭代器的加减、解引用、箭头等运算符的重载。迭代器最常使用的就是begin()、end()函数了，它们会分别返回该容器的起始元素的迭代器，和最后一个元素的下一个位置的迭代器，它们两个构成的是一个左闭右开的迭代器区间。

封装实现的迭代器支持加减、解引用等操作，因此我们可以通过迭代器去遍历容器中的数据。

void test
{
    list<int> lt;
    lt.push_back(11);
    lt.push_back(22);
    lt.push_back(33);
    lt.push_back(44);
    list<int>::iterator it=lt.begin();//获得起始位置的迭代器
    while(it!=lt.end())//当begin()和end()相等时就说明容器遍历完成了
    {
        cout<<*it<<endl;//*it 就是访问迭代器指向的数据 
        ++it;//it 往后++
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

反向迭代器遍历

知道了正向迭代器的原理，那么反向跌迭代器就是反着来，我们会很自然的想到反向迭代器就是将正向迭代器的begin()封装一下变成rend(),end()封装一下变成rbegin(),然后反向就是反着走就可以实现一个反向迭代器了，也就是rbegin()++就是套用的正向迭代器的end()的- -，rend()的- -套用的就是正向迭代器begin()的++，是完全相反的。

用反向迭代器遍历就是从rbegin()开始，往一个结点的方向走，走向是与正向迭代器相反的，上图的rbegin()往下走到的第一个结点是4而不是1，反向迭代器的走向要和正向迭代器区分开来。

注意：这里的rbegin()是原本正向迭代器的enc(),因为迭代器区间是左闭右开的，所以end()实际上是最后一个元素位置的下一个位置，那么再方向迭代器中我们对rbegin()解引用是得不到反向的第一个数据的，因为此时的rbegin()是再4的前一个位置，所以再解引用的时候要提前将rbegin()拷贝一份，对该拷贝中的正向迭代器进行–操作后再解引用的值才是反向的第一个元素！！（对应下面的实现）

Ref operator*()
{
	T temp=rit;//因为下面是返回的--temp 指向的对象 那么防止自生迭代器不变 那么就得一份拷贝让拷贝去减减不会影响到temp
	return *(--temp);
}
1
2
3
4
5

第一种三模板参数的反向迭代器的结构

template<class T>
class list
{
    //对正向迭代器的处理
    typedef Iterator<T,T&,T*> iterator;
    typedef Iterator<T,const T&,const T*> const_iterator;
    //对反向迭代器的处理
    typedef Reverse_Iterator<iterator,T&,T*> reverse_iterator;
    typedef const_Reverse_Iterator<const_iterator,const T&,const T*> const_reverse_iterator;
    
    ....
}

//这里的T就是正向迭代器类型，因为反向迭代器使用正向迭代器改变逻辑封装出来的
template<class T,class Ref,class Ptr>//三个模板参数
struct Reverse_Iterator
{
    typedef Reverse_Iterator<T,Ref,Ptr> Self;//类型重定义 简化代码
    //成员变量是一个正向迭代器
    T rit;
    Reverse_Iterator(T it)
   		:rit(it)
    {
        
    }
}
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

重点剖析：

1.成员变量 rit 得放在初始化列表初始化 因为传过来的是迭代器类型，是一个自定义类型，如果其默认的构造函数不匹配那么就没有了可用的构造函数，就必须通过初始化表初始化。所以自定义类型最好是放到初始化列表初始化，另外常量和引用也得在初始化列表初始化！

Reverse_Iterator(T it)
	:rit(it)//这里必须得在初始化列表初始化 因为其默认的构造函数没有给缺省值 不匹配 
{
	
}
1
2
3
4
5

2.反向迭代器的解引用和 -> 的重载都是套用的正向迭代器中的已经有的 * 和 -> 运算符重载函数

3.其中的Ptr operator ->()重载返回的是一个地址，但是使用的时候编译器有一个优化，两个连续的->会被优化为一个 例如容器中存的类型是B，B中有两个成员变量 _a _b,用迭代器->重载函数返回的是该结构体的地址，要想访问里面的成员还得用一个 -> 成员 的方式才能访问，但是编译器会有优化，原本两个箭头才能办到的事现在一个箭头就可以实现了！！

//例
struct B
{
    B(int a=0,int b=0)
    {
        _a=a;
        _b=b;
    }
    int _a;
    int _b;
}
B b1(3,3);
B b2(4,4);
B b3(5,5);
list<B> lt;
lt.push_back(b1);
lt.push_back(b2);
lt.push_back(b3);
list<B>::iterator it=lt.begin();
whiel(it!=lt.end())
{
    cout<<it->_a<<" "<<it->_b<<endl;//一个箭头就可以直接访问成员变量了
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

整体代码：

template<class T,class Ref,class Ptr>//这里的T是正向迭代器 因为是用正向迭代器封装出来的
	struct Reverse_Iterator
	{
		typedef Reverse_Iterator<T, Ref, Ptr> Self;
		T rit;//自定义类型 如果没有初始化 编译器会调用自身的默认构造函数初始化 如果自身的默认构造函数也不匹配那么就必须在初始化列表初始化
		Reverse_Iterator(T it)
			:rit(it)//这里必须得在初始化列表初始化 因为其默认的构造函数没有给缺省值 不匹配 
		{
			//rit._node = it._node;
			//T temp = it;
			/*rit = it;*/
		//这里不能直接写成赋值的形式 rit=it; 
		}
		//Ref& operator*()
		Ref operator*()
		{
			T temp=rit;//因为下面是返回的--temp 指向的对象 那么防止自生迭代器不变 那么就得一份拷贝让拷贝去减减不会影响到temp
			return *(--temp);
		}
		Ptr operator->()
		{
			return &(operator*());
		}

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

		Self& operator++(int)
		{
			Self temp(*this);
			--rit;
			return temp;
		}

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

		Self& operator--(int)
		{
			Self temp(*this);
			++rit;
			return temp;
		}

		//下面这样写会出错 因为等于的左操作数是const 类型的那么就会有权限放大的问题了 const this* 传给非const 类型的指针
		//解决方法就是将原来的正向迭代器的判断相等的函数变成const成员函数 const修饰this指针 达到一致
		bool operator==(const Self& Rit)
		{
			return Rit.rit == rit;
		}

		bool operator!=(const Self& Rit)
		{
			return Rit.rit != 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

第二种单模板参数的迭代器结构

因为迭代器有const 迭代器和非const 迭代器 ，为了区分* 和 -> 重载函数的返回值类型是否带const （const 迭代器就需要有const ，非const迭代器不需要带const) 所以上面的反向迭代器的实现的模板中有三个参数，后面两个参数就是专门为了区分上面两个函数的返回值是否带const而设置的。但是还有一种方法就是在正向迭代器中设置一些内嵌的类型来存储传入迭代器指向数据的数据类型，然后反向迭代器就可以到传进的正向迭代器中去找数据的具体类型，这样就不用特意定义一个三参数的模板了。（具体看代码)

正向迭代器中的相关处理：

list类中的对应处理：

单参数模板的反向迭代器的主要代码：

• 这里需注意的是，既然是正向迭代器中已经重定义了存储类型的引用类型和指针类型，那么到它里面去找就可以得到对应的类型来作为这里的operator()和operator->()的返回值类型，想法是没有错的，但是需要引起注意的是，这里的模板还没有示例化，那Iterator就是模板虚拟类型，编译器是不会到里面去找重定义的内嵌类型的，直接去里面找会报错！！！*

解决方法，加上关键字typename 去告诉编译器这里的Iterator::refrence 和 Iterator::pointer是一个具体的类型，需要等Iterator实例化之后再去里面找，这样就不会报错了！（也可以直接用auto 让编译器自己推导类型）

代码：

//传单参数的   测试没有问题 
template<class Iterator>
struct Reverse_Iterator
{
	Iterator _it;
	typedef Reverse_Iterator<Iterator> Self;

	Reverse_Iterator(const Iterator it)
		:_it(it)//内置类型没有合适的默认构造函数就放在初始化列表初始化
	{
		/*_it = it;*/  //初始化列表初始化
	}

	//高能！！！
	//这里的模板参数是Iterator 类模板没有实例化 那么这里的Iterator就是模板虚拟类型 
	//编译器是不会到里面去找其内嵌定义的类型
	//类模板没有实例化 找出来也是虚拟类型  后期无法处理 
	//Iterator::refence  必须用到关键字typename 来告诉编译器这个Iterator::pointer 是一个类型 
	// 在其实例化之后再去里面找想要的内嵌定义的类型！！！
	//也可用用auto关键字 让编译器自动推   根据右边的实例化的模板返回类型进行推演 
	typename Iterator::refrence operator*()
	{
		Iterator temp(_it);

		return *(--temp);
	}

	typename Iterator::pointer operator->()
	{
		return &(operator*());
	}

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

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

	bool operator==(const Self& Rit)
	{
		//这里的比较顺序不同 就涉及权限问题了  Rit是const类型 那么其接收它的指针就得是const修饰的指针！！！！
		return Rit._it == _it;
	}
	bool operator!=(const Self& Rit)
	{
		return Rit._it != _it;
	}

};
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
65
66
67