【C++】反向迭代器的设计_c++ unordered_set反向迭代

+前言

STL中不少的容器需要有迭代器这样的设计，特别是正向迭代器，几乎每个容器都有自己的特定实现方式，有了正向迭代器之后，我们还要提供反向迭代器以供一些特殊的需求，但是许多容器的正向迭代器实现的方式不一样，如果我们要实现其反向迭代器，每个容器的反向迭代器的实现方式也不一样，有没有一种方法能够统一反向迭代器的实现方式呢？

有的，那就是拿已有的正向迭代器进行封装，这样只要我们实现了正向迭代器，反向迭代器自然而然就形成了，本篇文章我们就来一起探究这种设计方式。

一、反向迭代器的结构

我们设计的反向迭代器是用正向迭代器实现的，这样反向迭代器的实现方式就统一了，那么我们反向迭代器的成员变量就是一个正向迭代器，关于成员函数，我们反向迭代器提供的接口与正向迭代器提供的接口一样。

//第一个模板参数传递 正向迭代器，第二个传递 迭代器的引用 第三个传递 迭代器的地址
 template<class Iterator, class Ref, class Ptr>
 
 //用struct定义类，因为我们想要公开我们的接口
 struct _reverse_iterator
 {
 	//对自己进行typedef方便使用
 	typedef _reverse_iterator<Iterator, Ref, Ptr> self;
    //成员变量 是一个正向迭代器
    Iterator _current;
    
    //构造函数   用一个正向迭代器进行初始化反向迭代器对象
    _reverse_iterator(Iterator it)
        :_current(it)
    {}
    //*运算符重载
    Ref operator*();
    //前置++运算符重载
    self& operator++();
    //后置++运算符重载
    self operator++(int)
    //前置--运算符重载
    self& operator--()
    //后置--运算符
    self operator--(int)
    //->操作符
    Ptr operator->()
    //关系运算符
    bool operator!=(const self& s);
    bool operator==(const self& s);

 }
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

容器类内的rbegin与rend 函数

//类内使用反向迭代器
class myclass
{
     //此类内要配套有一个正向迭代器iterator，然后传给外面的反向迭代器

     //将反向迭代器进行typedef方便使用
     typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;
      //反向迭代器
     typedef _reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;

     //反向迭代器
     reverse_iterator rbegin()
     {
    	return reverse_iterator(end());
     }
     reverse_iterator rend()
     {
     	return reverse_iterator(begin());
     }

     //const反向迭代器
     const_reverse_iterator rbegin() const
     {
     	return const_reverse_iterator(end());
     }
     const_reverse_iterator rend() const
     {
    	return const_reverse_iterator(begin());
     }
};
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

注意: 反向迭代器这里我们采用了对称结构便于理解对比，但这也导致我们后面在进行*解引用操作符时要解引用前一个位置！

二、反向迭代器的接口实现

1、*运算符重载

我们可以创建一个局部对象，对局部对象进行--找到前一个位置，然后再进行解引用返回就行了。

//*运算符重载
Ref operator*()
{
	//这里是不用写拷贝构造的，默认的拷贝构造会对内置类型进行值拷贝，对自定义类型调用它的拷贝构造
	Iterator tmp = _current;
	--tmp;
	return *tmp;
}
1
2
3
4
5
6
7
8

2、算术运算符 ++ - -的重载

由于我们的反向迭代器是由正向迭代器实现的，反向迭代器++就相当于正向迭代器- - ，明白了这个就很好实现算术运算符重载了。

//前置++运算符重载
self& operator++()
{
	--_current;
	return(*this);
}
//后置++运算符重载
self operator++(int)
{
	//保存当前对象
	self tmp(*this);
	--_current;
	//返回--之前的对象
	return tmp;
}
//前置--运算符重载
self& operator--()
{
	++_current;
	return (*this);
}
//后置--运算符
self operator--(int)
{
	self tmp(*this);
	++_current;
	return tmp;
}
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

3、->操作符重载

->运算符重载我们只需要返回容器中存储的自定义类型的对象的地址就行了，我们可以先调用operator*()拿到容器中存储的对象，然后再进行取地址&

Ptr operator->()
{
	return &(operator*());
}
1
2
3
4

3、关系运算符

要判断两个反向迭代器相不相等，只需要判断反向迭代器里面的成员变量相不相等就行了。

//关系运算符
bool operator!=(const self& s)
{
	return _current != s._current;
}
bool operator==(const self& s)
{
	return _current == s._current;
}
1
2
3
4
5
6
7
8
9

到这里我们的反向迭代器就已经形成了。

三、关于反向迭代器的一些讨论

由于我们的反向迭代器是用模板写的，当我们将vector的迭代器类型传递过去时，我们的反向迭代器就变成了vector的反向迭代器，当我们将list的迭代器传递过去时，就形成了list的反向迭代器。

传递的迭代器必须的二元迭代器，可以++ ，- -。forward_list的迭代器就不行！

例如：实现vector的反向迭代器,我们只需要在类内部传递一下正向迭代器，然后typedef一下就行了。

template<class T>
class vector
{
public:
	//正向迭代器
	typedef  T* iterator;

	//反向迭代器   将正向迭代器进行传递给反向迭代器
	typedef _reverse_iterator<iterator, T&, T*> reverse_iterator;
	typedef _reverse_iterator<iterator, const T&, const T*> const_reverse_iterator;

	//普通迭代器  ------------------------------------------------
	iterator begin();
	iterator end();
	

	//const迭代器
	typedef const T* const_iterator;
	const_iterator begin() const;
	const_iterator end() const;
	
	//反向迭代器
	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}
	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}

	//const反向迭代器
	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(end());
	}
	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(begin());
	}
	...... 
	...... 
	...... 
};
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