C++迭代器iterator详解__stl_verify(_first._getcont() == _last._getcont(),

知识的学习在于点滴记录，坚持不懈；知识的学习要有深度和广度，不能只流于表面，坐井观天；知识要善于总结，不仅能够理解，更知道如何表达！

迭代器概念

最近有人春招面试互联网大厂被问到这样一个问题：迭代器有什么用处？泛型算法的参数为什么接收的都是迭代器？

迭代器iterator是C++ STL的组件之一，作用是用来遍历容器，而且是通用的遍历容器元素的方式，无论容器是基于什么数据结构实现的，尽管不同的数据结构，遍历元素的方式不一样，但是用迭代器遍历不同容器的代码是完全一样的。经典的迭代器遍历容器的代码如下：

vector<int>::iterator it = vec.begin();
for (; it != vec.end(); ++it)
{
	cout << *it << " ";
}
cout << endl;
1
2
3
4
5
6

unordered_set<int>::iterator it = us.begin();
for (; it != us.end(); ++it)
{
	cout << *it << " ";
}
cout << endl;
1
2
3
4
5
6

实际上，C++11新标准的foreach语句，对于容器的遍历就是通过迭代器iterator实现的，如果容器没有实现iterator迭代器，那么foreach语句也无法遍历容器，上面vector容器的遍历代码可以简化为：

for (int val : vec) // 实际上是用迭代器遍历容器vec
{
	cout << val << " ";
}
cout << endl;
1
2
3
4
5

迭代器一般实现为容器的嵌套类型，在容器内部提供具体的实现。但是容器不同，底层元素遍历的方式也不同，那么为什么说迭代器遍历所有容器的方式是一样的呢？那是因为迭代器提供了常用的operator!=，operator++，operator*等运算符的重载函数，把迭代容器的细节全部隐藏在这些通用的运算符重载函数里面，因此用户侧表现出来的就是，迭代器遍历所有容器的方式都是一样的，其实底层都是不一样的风景^^！

所以刚开始的那个问题就可以回答了，泛型算法是针对很多容器实现的通用算法，肯定需要一种统一的方式遍历容器的元素，只有迭代器才能做到！

iterator迭代器实现

这部分提供一个极简的vector容器实现，然后给它提供一个迭代器iterator的实现，看看容器迭代器的原理是什么，这里面容器的空间配置器直接使用C++标准库的allocator默认实现。

下面是极简vector容器以及迭代器的代码实现：

#include <iostream>

// 简单的vector容器实现，主要查看其嵌套类iterator迭代器的实现
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	// 容器迭代器的实现
	class iterator
	{
	public:
		friend class MyVector;
		iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		bool operator!=(const iterator &it) { return _ptr != it._ptr; }
		T& operator*() { return *_ptr; }
		T* operator->() { return _ptr; }
	private:
		T *_ptr;
	};
	// 容器的begin方法返回首元素迭代器
	iterator begin() { return iterator(_first._ptr); }
	// 容器的end方法返回末尾元素后继位置的迭代器
	iterator end() { return iterator(_last._ptr); }
private:
	iterator _first; // 指向数组其实地址
	iterator _last;  // 指向最后一个有效元素的后继位置
	iterator _end;   // 指向数据空间末尾元素的后继位置
	Alloc _allocator;// 容器底层的空间配置器

	// 容器的扩容函数
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};
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
73
74
75
76
77
78
79
80
81
82
83

从上面的代码可以看到，容器的iterator实现成容器的嵌套类类型，提供了迭代容器常用的运算符重载函数，容器本身提供了begin和end方法，begin返回容器首元素的迭代器，end返回容器末尾元素后继位置的迭代器。

容器迭代器失效问题

容器的迭代器失效问题还是比较常考到的，随着VS版本的迭代，g++版本的迭代，C++标准库容器以及迭代器的源码都有比较大的修改，但是迭代器失效的问题本质归纳起来就两点：

1>不同容器的迭代器是不能进行比较的
2>容器的元素进行增加、删除操作后，原来的迭代器就全部失效了

这个从源码上能够清晰的看出来，在两个迭代器iterator进行operator!=比较操作的时候，都会进行_Compat这样的一个判断：

const _Container_base12 *_Getcont() const noexcept
		{	// get owning container
		return (_Myproxy == nullptr ? nullptr : _Myproxy->_Mycont);
		}

void _Compat(const _Vector_const_iterator& _Right) const
		{	// test for compatible iterator pair
 #if _ITERATOR_DEBUG_LEVEL == 0
		(void)_Right;
 #else /* ^^^ _ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 0 vvv */
		_STL_VERIFY(this->_Getcont() == _Right._Getcont(), "vector iterators incompatible");
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

用迭代器遍历容器的时候，每一次都会判断当前迭代器it != container.end()是否已经到达容器的末尾迭代器，当上面两个条件发生以后，这里_STL_VERIFY(this->_Getcont() == _Right._Getcont(), “vector iterators incompatible”);这个判断就失败了，程序运行报错，提示迭代器不匹配，意思就是迭代器失效了！

那迭代器失效怎么办？答案就是要对迭代器进行实时更新，如下面的代码：

#include <vector>
#include <iostream>
int main()
{
	std::vector<int> vec1;
	for (int i = 0; i < 20; ++i)
	{
		vec1.push_back(rand() % 100);
	}

	// 删除所有偶数
	auto it = vec1.begin();
	while (it != vec1.end())
	{
		if (*it % 2 == 0)
		{
			// 这里要对迭代器进行实时更新，否则容器元素改变，it迭代器失效！
			it = vec1.erase(it);
		}
		else
		{
			++it;
		}
	}

	for (int v : vec1)
	{
		std::cout << v << " ";
	}
	std::cout << std::endl;
	return 0;
}
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

const_iterator迭代器实现

const_iterator和上面的普通iterator比较起来就是，通过iterator可读可写，而const_iterator只能读取容器元素，不能修改容器元素，const_iterator在设计上，一般作为iterator的基类而存在，因为一个iterator对象可以初始化const_iterator，反过来是不行的，它们的操作几乎一样，除了读写权限不同。

在上面MyVector演示代码的基础上，实现const_iterator常量迭代器，代码如下：

#include <iostream>

// 简单的vector容器实现，主要查看其嵌套类iterator迭代器的实现
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	// 容器常量迭代器的实现
	class const_iterator
	{
	public:
		friend class MyVector;
		const_iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		bool operator!=(const const_iterator &it) { return _ptr != it._ptr; }
		// 返回值被const修饰，只能读，不能修改
		const T& operator*()const { return *_ptr; }
		const T* operator->()const { return _ptr; }
	protected:
		T *_ptr;
	};

	// 普通iterator继承自const_iterator
	class iterator : public const_iterator
	{
	public:
		iterator(T *ptr = nullptr)
			:const_iterator(ptr) {}
		// 返回类型是T&的普通引用，可读可写
		T& operator*() { return *const_iterator::_ptr; }
		T* operator->() { return const_iterator::_ptr; }
	};
	// 容器的begin方法返回首元素迭代器
	iterator begin() { return iterator(_first._ptr); }
	// 容器的end方法返回末尾元素后继位置的迭代器
	iterator end() { return iterator(_last._ptr); }

	// 常对象调用常begin和end方法返回的是常量迭代器，只能读容器数据，不能修改
	const_iterator begin()const { return const_iterator(_first._ptr); }
	const_iterator end()const { return const_iterator(_last._ptr); }

private:
	iterator _first; // 指向数组其实地址
	iterator _last;  // 指向最后一个有效元素的后继位置
	iterator _end;   // 指向数据空间末尾元素的后继位置
	Alloc _allocator;// 容器底层的空间配置器

	// 容器的扩容函数
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

可以写如下代码测试，常量迭代器只能读取，不能修改：

int main()
{
	MyVector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	MyVector<int>::const_iterator cit = vec.begin();
	for (; cit != vec.end(); ++cit)
	{
		std::cout << *cit << " ";  // 这里*cit不能被赋值作为左值
	}
	std::cout << std::endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

reverse_iterator和const_reverse_iterator的设计

实际上反向迭代器reverse_iterator和反向常量迭代器const_reverse_iterator就是通过正向迭代器iterator和const_iterator实现的，通过用正向迭代器实例化得到相应的反向迭代器，看下面代码演示实现：

#include <iostream>

// 反向迭代器实现
template<typename Iterator>
class _reverse_iterator
{
public:
	using value_type = typename Iterator::value_type;
	// 通过一个正向迭代器构建一个反向迭代器
	_reverse_iterator(Iterator it) :_it(it) {}

	template<typename Other>
	_reverse_iterator(const _reverse_iterator<Other> &src)
		: _it(src._it) {}

	bool operator!=(const _reverse_iterator<Iterator> &it)
	{
		return _it != it._it; // 实际调用的还是正向迭代器的operator!=函数
	}
	void operator++() { --_it; } // 反向迭代器的++操作，就是正向迭代器的--操作
	value_type& operator*() { return *_it; }
	value_type* operator->() { return &(*this); } // 获取迭代的元素的地址
private: 
	Iterator _it; // 反向迭代器依赖容器的正向迭代器实现

	template<typename Other>
	friend class _reverse_iterator;
};

// 简单的vector容器实现，主要查看其嵌套类iterator迭代器的实现
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	// 类型前置声明
	class const_iterator;
	class iterator;
	// 定义反向迭代器和反向常量迭代器的类型名称
	using reverse_iterator = _reverse_iterator<iterator>;
	using const_reverse_iterator = _reverse_iterator<const_iterator>;

	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	// 容器常量迭代器的实现
	class const_iterator
	{
	public:
		using value_type = const T;

		friend class MyVector;
		const_iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		void operator--() { --_ptr; }
		bool operator!=(const const_iterator &it) { return _ptr != it._ptr; }
		// 返回值被const修饰，只能读，不能修改
		const T& operator*()const { return *_ptr; }
		const T* operator->()const { return _ptr; }
	protected:
		T *_ptr;
	};

	// 普通iterator继承自const_iterator
	class iterator : public const_iterator
	{
	public:
		using value_type = T;

		iterator(T *ptr = nullptr)
			:const_iterator(ptr) {}
		// 返回类型是T&的普通引用，可读可写
		T& operator*() { return *const_iterator::_ptr; }
		T* operator->() { return const_iterator::_ptr; }
	};
	// 容器的begin方法返回首元素迭代器
	iterator begin() { return iterator(_first._ptr); }
	// 容器的end方法返回末尾元素后继位置的迭代器
	iterator end() { return iterator(_last._ptr); }

	// 常对象调用常begin和end方法返回的是常量迭代器，只能读容器数据，不能修改
	const_iterator begin()const { return const_iterator(_first._ptr); }
	const_iterator end()const { return const_iterator(_last._ptr); }

	// rbegin返回的是最后一个有效元素的迭代器表示
	reverse_iterator rbegin() { return reverse_iterator(iterator(_last._ptr-1)); }
	// rend返回的是首元素的前导位置
	reverse_iterator rend() { return reverse_iterator(iterator(_first._ptr - 1)); }
	// rbegin返回的是最后一个有效元素的迭代器表示
	const_reverse_iterator rbegin()const { return const_reverse_iterator(iterator(_last._ptr - 1)); }
	// rend返回的是首元素的前导位置
	const_reverse_iterator rend()const { return const_reverse_iterator(iterator(_first._ptr - 1)); }
private:
	iterator _first; // 指向数组其实地址
	iterator _last;  // 指向最后一个有效元素的后继位置
	iterator _end;   // 指向数据空间末尾元素的后继位置
	Alloc _allocator;// 容器底层的空间配置器

	// 容器的扩容函数
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

上面新增加的代码，就是反向迭代器的代码，可以安装Beyond Compare软件来对比代码的更改，体会反向迭代器的优秀设计。代码测试如下：

int main()
{
	MyVector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	// 正向遍历容器元素
	auto it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	// 反向遍历容器元素
	MyVector<int>::const_reverse_iterator rit = vec.rbegin();
	for (; rit != vec.rend(); ++rit)
	{
		std::cout << *rit << " ";
		// *rit = 20; 反向常量迭代器不能修改容器元素的值
	}
	std::cout << std::endl;

	return 0;
}
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

当然实际使用中，左值的类型我们可以直接用auto关键字代替，通过自动推导右值的类型，我们就不用手动写复杂的类型了。

insert插入型迭代器

C++标准库中提供了一些插入型迭代器，主要用于泛型算法当中，给容器添加元素，插入行迭代器有：

示例代码：

#include <vector>
#include <list>
#include <algorithm> // 包含泛型算法
#include <iterator> // 包含各类迭代器
using namespace std;

int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	vector<int> vec2;
	// 通过back末尾插入型迭代器，把vec容器的元素按末尾插入方式，到vec2中
	copy(vec.begin(), vec.end(), back_inserter(vec2));
	for (int v : vec2)
	{
		cout << v << " ";
	}
	cout << endl;

	list<int> mylist;
	// 把vec容器的元素逆序，插入到list容器当中
	reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
	for (int v : mylist)
	{
		cout << v << " ";
	}
	cout << endl;

	return 0;
}
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

流迭代器

在C++中，不管是标准的输入输出流，还是文件流，或者是字符串流，也可以看作容器，那么C++库提供了流迭代器，看下面代码示例：

#include <vector>
#include <list>
#include <algorithm> // 包含泛型算法
#include <iterator> // 包含各类迭代器
using namespace std;

int main()
{
	vector<int> vec;
	// 通过输入流迭代器，从标准输入设备获取int，头插到vec容器当中
	copy(istream_iterator<int>(cin), istream_iterator<int>(),
		inserter(vec, vec.begin()));

	vector<int> vec2;
	copy(vec.begin(), vec.end(), back_inserter(vec2));
	// 通过输出流迭代器，把vec2容器的元素输出到cout中
	copy(vec2.begin(), vec2.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	list<int> mylist;
	reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
	// 通过输出流迭代器，把mylist容器的元素输出到cout中
	copy(mylist.begin(), mylist.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	return 0;
}
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

可以看到，借助copy泛型算法、插入行迭代器、istream_iterator输入流迭代器和ostream_iterator输出流迭代器，可以很方便的进行流操作，文件流和字符串流同理。