C++ [STL容器反向迭代器]_c++容器反向迭代

本文已收录至《C++语言》专栏！
作者：ARMCSKGT

---

---

前言

我们知道STL大部分容器都有迭代器，迭代器又分为正向迭代器和反向迭代器，对于正向迭代器以及实现前面我们已经了解了不少，而反向迭代器的设计思想是适配器模式，本节我们介绍反向迭代器的实现！

---

正文

适配器

---

适配器是把一个类的接口变换成客户端所期待的另一种接口，从而使原本接口不匹配而无法在一起工作的两个类能够在一起工作！

那么到底什么是适配器？

我们常用的充电器就是一个例子，充电器也叫电源适配器，一个充电器可以充相同接口的不同手机，这就是适配器！

适配器思想是利用已有的对象对其进行封装以满足我们的需要！


作为STL六大组件之一的适配器，一共有三类！

STL中有三类适配器：

• container adapters：容器适配器
  – 容器适配器底层套用其他容器作为底层容器，封装容器，改变容器的行为作为本容器适配器；容器适配器底层的容器可以修改，只要实现了容器适配器底层所需函数都可以作为容器适配器的底层容器；例如stack容器的底层是使用deque(双端队列)，也可以修改为vector，在后面我们会着重介绍容器适配器
  
  
• functor adapters：仿函数适配器
  – 如果说仿函数的设计是为了让必须有两个参数的普通函数能够被只能有传入一个参数的算法所使用的话，仿函数适配器则是为了让必须有两个参数的仿函数被算法调用；仿函数适配器非常厉害，几乎可以无限制的创造出各种可能的表达式
  
  
• iterator adapters：迭代器适配器
  – 迭代器适配器主要是可以实现反向迭代器，反向迭代器独立实现与一个头文件，只要容器支持双向迭代器，都可以支持反向迭代器，反向迭代器是对正向迭代器的封装，改变其行为，满足条件的容器只需要声明反向迭代器的头文件便可以使用反向迭代器

图片出自《STL源码剖析》

---

反向迭代器

---

反向迭代器适用于所有的容器，因此它是作为一个单独的 .h 文件出现的，别的容器如果想使用，直接包含就行了!

反向迭代器 reverse_iterator 可以用来反向遍历容器，在某些场景下很实用!

图片出自《STL源码剖析》

---

反向迭代器框架

反向迭代器是对正向迭代器的封装，所以使用多模板参数！

模板参数：

• Iterator：正向(普通)迭代器类型
• Ref：迭代器下元素数据类型的引用类型
• Ptr：迭代器下元素数据类型的指针类型
  
  
  之所以这样设计，也是为了简化代码，增强代码的复用性；对于 string ，vector，list，可以共用这一套代码就能同时实现反向迭代器。(对于其他容器，要么不支持迭代器或不支持双向迭代器，无法满足反向迭代器需求；又或之其容器迭代器底层实现复杂，需要单独实现，例如map和set)
  

在迭代器对象中，我们需要一个成员变量保存当前的正向迭代器，所以定义一个普通迭代器变量 current 保存正向迭代器，方便操作！

反向迭代器在 ++ 和 - - 后需要返回一个反向迭代器，为了书写简单，我们将反向迭代器类型在类中typedef，定义为 self

template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
	Iterator current; //迭代器对象

	typedef Reverse_iterator<Iterator, Ref, Ptr> self; //反向迭代器类型
};
1
2
3
4
5
6
7

注意：反向迭代器思想与正向迭代器一样，只是用于封装，改变被封装对象的行为；所以在反向迭代器中的大部分操作都会调用正向迭代器中的函数进行操作！

---

默认成员函数

对于默认成员函数，我们只需要实现构造和拷贝构造即可！

	//Reverse_iterator() {} //默认构造
	explicit Reverse_iterator(Iterator x) //构造封装迭代器 - 禁止类型转换
		:current(x)
	{}

	Reverse_iterator(const self& x) //自对象(reserve_iterator)构造-拷贝构造
		:current(x.current)
	{}
1
2
3
4
5
6
7
8

因为是反向迭代器是对正向迭代器的封装，我们严格要求传入的参数必须是正向迭代器，禁止在构造时类型转换，防止出现以外！

---

反向迭代器的遍历

反向迭代器分别为 rbegin 和 rend ，rbegin 是对 end 的封装，rend 是对 begin 的封装！

//反向迭代器
//普通反向迭代器
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()); }
//const反向迭代器
const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
1
2
3
4
5
6
7
8
9
10

对于 vector<int> v = {1,2,3,4,5}; 遍历

• 正向迭代器通过++遍历：1 2 3 4 5
• 反向迭代器通过++遍历：5 4 3 2 1
  

对于反向迭代器的遍历，从最后一个元素的下一个位置开始，反向迭代器的 ++ 就是对正向迭代器的 - - ！
因为我们封装的current就是正向迭代器，所以直接对current进行 ++ 或 - - 即可！

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

---

反向迭代器的比较

迭代器的比较，常用于遍历时的终止条件，即 == 和 != 比较！
对于这两种比较，直接调用正向迭代器的比较运算符即可！

// != 比较
bool operator!=(const self& n) const
{
	return current != n.current;
}
// == 比较
bool operator==(const self& n) const
{
	return current == n.current;
}
//直接调用正向迭代器的比较即可
1
2
3
4
5
6
7
8
9
10
11

---

反向迭代器数据访问

对于反向迭代器，我们也会使用 * 和 -> 来访问数据，对于反向迭代器，访问数据就有所不同了！

前面我们提到，反向迭代器rbegin是封装end实现的，那么如果我们要访问反向遍历中的第一个元素，不能直接对反向迭代器中的正向迭代器调用 operator*() 和 operator->() 否则就属于野指针访问了！

所以对于反向迭代器元素的访问，我们整体向前移动一位，即迭代器在end位置时，访问end-1位置的元素，这样既可以解决元素访问的问题，也可以解决了遍历时漏掉元素的问题！

如果不进行这样的设计，还会引发另一个问题：

如果按照我们想象的方式设计，遍历时第一个元素无法遍历到，因为当rbegin==rend时就退出了，于是设计者在设计时规定，迭代器访问元素时，默认访问迭代器位置的上一个位置元素，这样当迭代器处于2时，访问的就是1，这样就避免了这个问题且也不会出现rbegin越界访问问题！

// T&
Ref operator*() //解引用访问数据
{ //因为是反向迭代器，如果是begin访问则是end位置，此时需要先--再解引用
	Iterator tmp(current);
	--tmp;
	return *tmp;
}

// T*
Ptr operator->()
{
	Iterator tmp(current);
	--tmp;
	return &(operator*());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对于 operator->() 只需要复用 operator*() 对其返回值取地址即可！

---

反向迭代器代码

#pragma once
#include<iostream>
#include<assert.h>

template<class Iterator,class Ref,class Ptr>
struct Reverse_iterator
{
	Iterator current;

	typedef Reverse_iterator<Iterator, Ref, Ptr> self;

	//Reverse_iterator() {} //默认构造
	explicit Reverse_iterator(Iterator x) //构造封装迭代器 - 禁止类型转换
		:current(x)
	{}

	Reverse_iterator(const self& x) //自对象(reserve_iterator)构造-拷贝构造
		:current(x.current)
	{}

	//反向迭代器 ++ 相当于 --
	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;
	}

	bool operator!=(const self& n) const
	{
		return current != n.current;
	}

	bool operator==(const self& n) const
	{
		return current == n.current;
	}

	//T&
	Ref operator*() //解引用访问数据
	{ //因为是反向迭代器，如果是begin访问则是end位置，此时需要先--再解引用
		Iterator tmp(current);
		--tmp;
		return *tmp;
	}

	Ptr operator->()
	{
		Iterator tmp(current);
		--tmp;
		return &(operator*());
	}
};
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
68
69
70
71
72

本节简单的介绍反向迭代器的思想，反向迭代器中还有一些功能，感兴趣的小伙伴可以研究研究！

---

测试反向迭代器

我们将反向迭代器植入我们自己实现的string，vector和list中进行实验！

list

void test()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> x(arr,arr+10);
	auto it = x.rbegin();
	while (it != x.rend())
	{
		cout << *(it) << " ";
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11

vector

void test()
{
	int arr[] = { 448,558,668,778,888 };
	vector<int> x(arr, arr + 5);
	auto it = x.rbegin();
	while (it != x.rend())
	{
		cout << *(it) << " ";
		++it;
	}
	cout << endl << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

string

void test()
{
	string x("droW elloH");
	auto it = x.rbegin();
	while (it != x.rend())
	{
		cout << *(it) << " ";
		++it;
	}
	cout << endl << endl;
}
1
2
3
4
5
6
7
8
9
10
11

关于上面三个容器的测试代码如下：

• string模拟实现
• vector模拟实现
• list模拟实现

代码仅简单实现，存在部分问题，敬请谅解！

---

最后

本节简单介绍了反向迭代器思想，将类和对象的封装意义体现的淋漓尽致，关于迭代器的介绍就告一段落，在后期，对于复杂容器，其迭代器的设计将会更加复杂，我们后面继续学习！

本次 <C++ STL容器反向迭代器> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/390729