C++：迭代器的封装思想

---

本博客将通过实现list的迭代器，以及它的反向迭代器，来帮助大家理解迭代器的底层逻辑，以及封装思想。

---

list迭代器实现

迭代器是一个遍历容器的工具，其可以通过自增自减来改变位置，通过解引用来访问节点，也就是模仿指针的行为。这为算法库提供了统一的方式来访问容器，也降低了用户的学习成本，可以用相同的方式来访问不同的容器。

那么迭代器是如何做到模仿指针行为的？
这还要归功于运算符重载这一设计，在类中，我们可以通过运算符重载来决定一个类在面对不同运算符时的行为，那么我们是否可以将迭代器封装为一个类，然后利用运算符重载，使得迭代器可以使用++，–，*这样的操作符，从而模仿指针的行为呢？
STL的底层迭代器就是利用这样的方式实现的。

我们先来看到list的基本结构：

list节点：

template <class T>
struct list_node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _data;
};
1
2
3
4
5
6
7

这是一个list的节点list_node，其有三个成员：_prev指向上一个节点，_next指向下一个节点，_data存储当前节点的数据。

template <class T>
	class list
	{
		typedef list_node<T> node;
		
	private:
		node* _head;
	};
1
2
3
4
5
6
7
8

这是一个list类，其将节点list_node重命名为了node，方便后续使用。
唯一一个成员变量是哨兵位头节点指针_head。

接下来我们就讨论要如何设计这个list的迭代器：
毫无疑问，我们需要把这个迭代器封装为一个类，而这个类的内部我们需要什么，才能让迭代器访问不同的节点呢？
想要访问不同的节点，毫无疑问就需要不同节点的指针，所以我们的迭代器需要把一个指向节点的指针给封装起来，然后利用运算符重载，改变这个指针的行为，从而实现迭代器。

现在我们将这个迭代器命名为__list_iterator，先看看基础结构：

template <class T>
struct __list_iterator
{
	typedef list_node<T> node;

	node* _node;
};
1
2
3
4
5
6
7

为了方便我们使用节点的指针，我们重命名list_node为node，而迭代器内部指向节点的指针名为_node。

---

构造函数：
代码如下：

__list_iterator(node* n)
	: _node(n)
{}
1
2
3

这就是一个很简单的初始化过程，这里不过多赘述了，那么我们要如何使用这个迭代器呢？

看看list类中获取迭代器的函数：

typedef __list_iterator<T> iterator;

iterator begin()
{
	return iterator(_head->_next);
}

iterator end()
{
	return iterator(_head);
}
1
2
3
4
5
6
7
8
9
10
11

先将我们的迭代器重命名为iterator，方便后续使用。
可以看到，我们的begin()函数就是返回了哨兵位节点的后一个节点，也就是第一个节点的指针，但是普通的指针的++，–操作不符合我们的要求，于是我们利用iterator(_head->_next)这个方式，利用这个指针来构造一个匿名对象，也就是迭代器的匿名对象，此时我们就完成了指针的封装，得到的指针就是被我们修改了行为后的迭代器了。

end()函数同理，iterator(_head)构造一个迭代器，将指针进行封装，修改其行为。

接下来我们回到迭代器的实现：

---

operator++：
我们希望我们的迭代器可以在++的时候到达下一个节点的位置，也就是_node = _node->_next这样的行为。
所以我们的需求就明确了，当迭代器++的时候，实际发生的是_node = _node->_next而不是简单的指针偏移。

先看到我们的实现：

__list_iterator<T> & operator++()
{
	_node = _node->_next;
	return *this;
}
1
2
3
4
5

++是要进行返回的，将自增后的节点作为返回值，所以最后我们还要return *this;，将修改后的节点作为返回值。

后置++同理：

__list_iterator<T>& operator++(int)
{
	__list_iterator<T> tmp(*this);
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6

由于后置++需要将自增前的值作为返回值，所以我们要先拷贝一份原先的值tmp，自增完成后，将原先的值tmp返回。

为了简化代码，我们可以将__list_iterator重命名为self代表迭代器自己的类型。

最后代码如下：

typedef __list_iterator<T> self;

self& operator++()
{
	_node = _node->_next;
	return *this;
}

self& operator++(int)
{
	self tmp(*this);
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这样一来，我们的迭代器++，表面上和指针自增一样，但是底层却是_node = _node->_next到达下一个节点的位置了。

---

operator–：
迭代器–同理，我们需要实现迭代器到达上一个节点，其实就是_node = _node->_prev。
实现如下：

self& operator--()
{
	_node = _node->_prev;
	return *this;
}

self& operator--(int)
{
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

迭代器判断相等：
想要判断两个迭代器是否相等，其实就是判断其内部封装的指针_node是否相等。

代码如下：

bool operator!=(const self& s)
{
	return _node != s._node;
}

bool operator==(const self& s)
{
	return _node == s._node;
}
1
2
3
4
5
6
7
8
9

这个比较简单，不做赘述了。

---

operator*：

*是迭代器中十分重要的操作符，指针就是利用解引用来访问指向内容的，迭代器就模仿指针，也通过解引用来访问节点值。
迭代器内部的成员_node是指向节点的指针，那么访问这个节点的值就是：_node->_data了。

所以解引用代码如下：

T& operator*()
{
	return _node->_data;
}
1
2
3
4

但是这个代码有一个问题，那就是：如果我们的list被const修饰了怎么办？
这样的话，由于我们返回的是T&，而这个_data就有可能会被修改，这就不符合const的行为了。

是否我们要写一个重载，比如这样：

T& operator*()
{
	return _node->_data;
}

const T& operator*()
{
	return _node->_data;
}
1
2
3
4
5
6
7
8
9

这是不行的，因为两个函数只有返回值不同，并不构成重载。
我们只希望返回值的类型不同，这要怎么办？

注意：我们的迭代器是利用模板生成的，而模板最大的用处就是泛型编程，可以无视类型的限制，我们完全可以给模板多传一个参数，让第二个参数作为operator*的返回值。

//-----迭代器-----
template <class T, class Ref>
struct __list_iterator
{
	typedef __list_iterator<T, Ref> self;

	Ref operator*()
	{
		return _node->_data;
	}
};
1
2
3
4
5
6
7
8
9
10
11

这样，当我们需要普通迭代器，第二个参数Ref就传入T&，如果需要const迭代器，那么第二个参数就传入const T&。
不过要注意的是，刚刚我们重命名了一个self， 即typedef __list_iterator self，此时由于模板参数改变，这个重命名也要一起改变：typedef __list_iterator self。

现在我们就可以在list中加入const迭代器了，接下来让类中定义的迭代器一起改变：

template <class T>
class list
{
	typedef __list_iterator<T, T&> iterator;
	typedef __list_iterator<T, const T&> const_iterator;

	//普通迭代器
	iterator begin()
	{
		return iterator(_head->_next);
	}

	iterator end()
	{
		return iterator(_head);
	}

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

	const_iterator end() const
	{
		return const_iterator(_head);
	}
};
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

看到两行typedef：

typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
1
2

当我们传入的第二个模板参数为T&，那么解引用的返回值就是可以修改的，此时就是一般的迭代器iterator。
当我们传入的第二个模板参数为const T&，那么解引用的返回值就是不可以修改的，此时就是const迭代器const_iterator。

相比于开始，我们现在多了一个迭代器const_iterator;，我们的this指针被const修饰时，说明此时需要调用const迭代器，那么我们就返回const_iterator类型的迭代器。

const_iterator begin() const
{
	return const_iterator(_head->_next);
}

const_iterator end() const
{
	return const_iterator(_head);
}
1
2
3
4
5
6
7
8
9

operator->：
接下面我们看到最后一个问题，那就是类的嵌套问题，假设我们的list内部是一个A类：

class A
{
public:
	int num;
};
1
2
3
4
5

那么如果我们想要通过迭代器访问A类的num成员，要怎么做？

假设我们有一个list的迭代器it，接下来我用it尝试访问这个A的成员num。

(*it).num
1

先解引用迭代器(*it)，此时就得到了list内部的A类，然后再利用.来访问内部的num成员。

这样访问是没有问题的，但是我们的迭代器是模仿指针的行为，我们会对一个指针先解引用，再用点操作符访问成员吗？
我们完全可以指针 -> 成员这样访问。

也就是说，我们还要对迭代器重载一个->操作符，实现这种直接访问的方式

代码：

T* operator->()
{
	return &_node->_data;
}
1
2
3
4

我们的返回值是_data的地址，而_data就是A类，所以我们可以就得到了一个A类的指针，此时T*就是其实就是A*。
那么我们看看现在要如何访问：

list.operator->()->num
1

你也许不是很能理解以上代码，我们拆解一下：
list.operator->()返回了一个A*类型的指针，而A*类型的指针可以直接访问num：

A* ptr;
ptr->num
1
2

所以以上代码list.operator->()->num就可以访问到num这个成员了。
而.operator->()其实就是->操作符，所以可以变形为以下代码：
list->->num
连用->->不太美观，也容易让人费解，但是编译器会将两个->优化为一个->，所以此时我们已经可以直接像指针一样访问成员了：

list->num
1

我们再回顾一遍推导过程：

list.operator->()->num == list->->num == list->num

这个访问和刚刚的operator*会遇到同样的问题，那就是const问题，所以我们要传入第三个模板参数Ptr，来控制operator->的返回值：

template <class T, class Ref, class Ptr>
struct __list_iterator
{
	Ptr operator->()
	{
		return &_node->_data;
	}
};
1
2
3
4
5
6
7
8

在list中：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
1
2

至此，我们就实现了一个list的迭代器了。

---

代码展示：

template <class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> self;
	node* _node;

	__list_iterator(node* n)
		: _node(n)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	self& operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	self& operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

	bool operator==(const self& s)
	{
		return _node == s._node;
	}
};
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

---

反向迭代器实现

那么我们要如何实现反向迭代器呢？

一开始我们实现正向迭代器的时候，遇到的问题就是：原生指针的行为不符合我们的要求，于是我们将原生指针进行了封装，利用运算符重载来修改其行为。

那么我们的反向迭代器还需要封装一个原生指针吗？
其实我们可以换一个思路：现在我们有正向迭代器，而正向迭代器并不符合反向迭代器的预期行为，我们不妨对正向迭代器进行一次封装，让其++变成–，–变成++，这不就是一个反向迭代器了吗？

结构如下：

template <class Iterator, class Ref, class Ptr>
struct ReverseIterator
{
	Iterator _cur;
};
1
2
3
4
5

我们定义了一个反向迭代器的类ReverseIterator，在内部封装了一个迭代器Iterator _cur，接下来我们就重载这个反向迭代器，让其行为符合预期：

先看看我们在list中是如何定义反向迭代器的：

	template <class T>
	class list
	{
		typedef ReverseIterator<iterator, T&, T*>  reverse_iterator;

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

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

首先我们重命名了反向迭代器typedef ReverseIterator reverse_iterator;，其第一个模板参数为iterator，也就是我们封装的正向迭代器。
随后在rbegin()中，我们直接将end()返回的末尾迭代器，作为我们反向迭代器的起始迭代器rbegin()；
将begin()返回的正向迭代器的起始迭代器，作为我们反向迭代器的末尾迭代器。

注意，end()返回的是最后一个元素的后面一个位置，所以我们在后续++,–操作时，要进行其他的操作，来矫正这个位置的偏差。

---

operator++：
现在由于我们是反向迭代器，我们的反向迭代器++，其实就是正向迭代器的–。

代码如下：

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

---

operator*

由于我们的迭代器位置是往后偏一位的，所以我们要返回前一个位置的迭代器而不是当前位置的迭代器：

Ref operator*()
{
	Iterator tmp = _cur;
	--tmp;
	return *tmp;
}
1
2
3
4
5
6

我们用tmp拷贝了一份当前的迭代器，随后--tmp，将其往前走一个位置，再返回tmp位置的迭代器，这样就可以矫正我们起初的位置偏差了。

---

而其它的操作符重载，几乎没有太大的差别，基本就围绕以上两种类型的改动，此处我们直接展示代码了：

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

		ReverseIterator(Iterator it)
			:_cur(it)
		{}

		Ref operator*()
		{
			Iterator tmp = _cur;
			--tmp;
			return *tmp;
		}

		Ptr operator->()
		{
			Iterator tmp = _cur;
			--tmp;
			return &tmp->_data;
		}

		self& operator++()
		{
			--_cur;
			return *this;
		}

		self& operator++(int)
		{
			self tmp(*this);
			--_cur;
			return tmp;
		}

		self& operator--()
		{
			++_cur;
			return *this;
		}

		self& operator--(int)
		{
			self tmp(*this);
			++_cur;
			return tmp;
		}

		bool operator!=(const self& s)
		{
			return _cur != s._cur;
		}

		bool operator==(const self& s)
		{
			return _cur == s._cur;
		}
	};
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

这个反向迭代器的实现，可以作用于任何正向迭代器，也就是说，不论是list，vector等等各种容器，都可以使用这一套反向迭代器来封装原本的迭代器，从而获得反向迭代器，

---