【C++】反向迭代器

一、什么是反向迭代器

反向迭代器是一种反向遍历容器的迭代器。也就是，从最后一个元素到第一个元素遍历容器。反向迭代器将自增(和自减)的含义反过来了：对于反向迭代器，++ 运算将访问前一个元素，而 -- 运算则访问下一个元素

所有容器都定义了 begin 和 end 成员，分别返回指向容器首元素和尾元素下一位置的迭代器。这两个迭代器通常用于标记包含容器中所有元素的迭代范围。容器还定义了 rbegin 和 rend 成员，分别返回指向容器尾元素和首元素前一位置的反向迭代器。与普通迭代器一样，反向迭代器也有const和非const版本
综上，反向迭代器的特点如下：

• rbegin()相当于end()
• rend()相当于begin()
• 反向迭代器++相当于正向迭代器–
• 其他操作* != ->和正向迭代器相同

反向迭代器和正向迭代器的使用完全相同

void vector_reverse_iterator_test()
{
    hdp::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    hdp::vector<int>::reverse_iterator rit = v.rbegin();
    while (rit != v.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、STL源码中反向迭代器的实现

我们可以通过参考STL源码中的反向迭代器的实现方式来学习如何实现反向迭代器

//vector反向迭代器
template <class T, class Alloc = alloc>
class vector {
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type* iterator;
    typedef const value_type* const_iterator;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    typedef reverse_iterator<const_iterator, value_type, const_reference, 
                           difference_type>  const_reverse_iterator;
    
    typedef reverse_iterator<iterator, value_type, reference, difference_type>
          reverse_iterator;
    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    const_reverse_iterator rbegin() const
    { 
        return const_reverse_iterator(end()); 
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    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

// list反向迭代器
template <class T, class Alloc = alloc>
class list
{
public:
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
  
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    typedef reverse_iterator<const_iterator> const_reverse_iterator;
    typedef reverse_iterator<iterator> reverse_iterator;
}
1
2
3
4
5
6
7
8
9
10
11
12

我们可以看到，STL中vector和list的反向迭代器都是reverse_iterator类的typedef，而reverse_iterator类位于源码的stl_iterator.h中，其中部分源码如下：

template<typename _Iterator>
class reverse_iterator
{
protected:
    _Iterator current;
public:
    reverse_iterator()
        : current()
        {}
    reverse_iterator(iterator_type __x)
        : current(__x)
        {}
    reference operator*() const
    {
	     _Iterator __tmp = current;
	     return *--__tmp;
    }
    pointer operator->() const
    {
         return &(operator*());
    }
    reverse_iterator& operator++()
    {
	     --current;
	     return *this;
    }
    reverse_iterator operator++(int)
    {
	     reverse_iterator __tmp = *this;
	     --current;
	     return __tmp;
     }
     reverse_iterator& operator--()
     {
	     ++current;
	     return *this;
     }
     reverse_iterator operator--(int)
     {
	     reverse_iterator __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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

如上图我们可以知道，正向迭代器是reverse_iterator的模板参数，而反向迭代器是reverse_iterator的对象，所以反向迭代器是一个容器适配器，它的适配容器是对应的正向迭代器，这样它就可以根据传递过来的正向迭代器的不同实例化出对应的反向迭代器，所以，只要我们实现了reverse_iterator类，不管是任何容器，只要支持反向迭代器，就可以传递其正向迭代器作为参数，就能够适配出对应的反向迭代器。

三、反向迭代器的模拟实现

我们有几个需要注意的地方：

1.我们为了其对称性，使得rbegin()等价于end(),rend()等价于begin(),所以++reverse_iterator等价于–iterator,–reverse_iterator等价于++iterator;由于end是指向最后一个元素的下一个位置，而rbegin由end适配得到，所以反向迭代器中的operator*()不是返回迭代器的当前位置的数据，而是返回迭代器当前位置的前一个位置的数据，如果我们需要返回当前位置的数据，可以将rbegin()由–end(),rend()由–begin()进行适配即可。

2.我们在实现operator*()和operator->()时，我们不知道T的类型(const/非const),所以我们不能确定函数的返回值类型，在STL源码中使用迭代器萃取的方法来解决这个问题

template<typename _Iterator>
class reverse_iterator
public:
      typedef _Iterator					iterator_type;
      typedef typename __traits_type::difference_type	difference_type;
      typedef typename __traits_type::pointer		pointer;
      typedef typename __traits_type::reference		reference;
protected:
      _Iterator current;

      typedef iterator_traits<_Iterator>		__traits_type;
	reference
      operator*() const
      {
	      _Iterator __tmp = current;
	      return *--__tmp;
      }
      pointer
      operator->() const
      { return &(operator*()); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

但是这种方式实现得比较复杂，所以我们像正向迭代器那样增加两个模板参数分别作为operator*()和operator->()的函数返回值即可：

template<class Iterator,class Ref,class Ptr>
class ReverseIterator
{
Ref& operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}
	// 返回节点的地址
	Ptr operator->()
	{
		return &(operator*());
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

完整代码如下：

template<class Iterator,class Ref,class Ptr>

class ReverseIterator
{
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
public:
	// 构造
	ReverseIterator(Iterator it)
		:_it(it)
	{}
	// 解引用返回的是最后一个位置的前一个数据
	Ref& operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}
	// 返回节点的地址
	Ptr operator->()
	{
		return &(operator*());
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}
	// 后置++，返回值不加引用，tmp是局部变量
	Self operator++(int)
	{
		Iterator tmp = _it;
		--_it;
		return tmp;
	}
	Self& operator--()
	{
		++_it;
		return *this;
	}

	Self operator--(int)
	{
		Iterator tmp = _it;
		++_it;
		return tmp;
	}
	bool operator!=(const Self& s) const
	{
		return _it != s._it;
	}

	bool operator==(const Self& s) const
	{
		return _it == s._it;
	}
private:
	// 成员变量为正向迭代器
	Iterator _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

四、vector和list迭代器的实现

vector迭代器

namespace hdp
{
	template<class T>
	class vector
	{
	public:
		// 迭代器
		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;
        
		// 迭代器
		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		// const 迭代器
		const_iterator begin()  const
		{
			return _start;
		}

		const_iterator end()  const
		{
			return _finish;
		}

		// 反向迭代器
		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
45
46
47
48
49
50
51
52
53
54
55
56
57
58

list迭代器

namespace hdp
{
    template<class T>
	class list
	{
		// list 节点
		typedef list_node<T> node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;  //迭代器
		typedef __list_iterator<T, const T&, const T*> const_iterator;  //const迭代器

		//反向迭代器
		typedef ReverseIterator<iterator,T&,T*> reverse_iterator;
		typedef ReverseIterator<const_iterator,const T&,const T*> const_reverse_iterator;
        
		// 迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			// iterator it(_head);
			// return it;
			// 匿名对象构造
			return iterator(_head);
		}

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

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

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

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

		// const 反向迭代器
		const_reverse_iterator rbegin() const
		{
			const_reverse_iterator(end());
		}

		const_reverse_iterator rend() const
		{
			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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

五、迭代器的意义

它是一种通用的遍历方式，所有的容器都可以使用迭代器这种方式去访问修改，对于string类来说，无论是正向遍历，还是反向遍历，下标+[]都足够好用，但是对于其他容器，对于那些以链表形式连接的数据结构，如list，map/set等，就不能使用下标+[]的方式去访问容器里的元素，所以就需要采用迭代器来访问这些容器里的元素。

六、迭代器的分类

根据迭代器实现的不同功能，C++迭代器分为：输入迭代器，输出迭代器，正向迭代器，双向迭代器，随机迭代器。

(1)输入迭代器：从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两次遍历一个序列

(2)输出迭代器：向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，同一输出迭代器不能两次遍历一个序列

(3)正向迭代器：假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。实际对应的类型有：forward_list，unordered_mapunordered_set。

(4)双向迭代器：双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则–p和p–都是有定义的。–p使得 p 朝和++p相反的方向移动。实际对应的类型有：list，map，set。

(5)随机迭代器：随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

p+=i：使得 p 往后移动 i 个元素。

p-=i：使得 p 往前移动 i 个元素。

p+i：返回 p 后面第 i 个元素的迭代器。

p-i：返回 p 前面第 i 个元素的迭代器。

p[i]：返回 p 后面第 i 个元素的引用。

此外，两个随机访问迭代器 p1、p2 还可以用 < > <= >=运算符进行比较。p1 < p2的含义是：p1 经过若干次（至少一次）++操作后，就会等于 p2。其他比较方式的含义与此类似。

对于两个随机访问迭代器 p1、p2，表达式p2-p1也是有定义的，其返回值是 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。