C++迭代器

一.什么是迭代器：

C++中，迭代器就是一个类似于指针的对象，它能够用来遍历C++标准模板库容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。以下面的string为例子介绍说明。

对string 对象s1正向遍历输出，代码如下所示：

	string::iterator it = s.begin();
	//此处的begin()函数有两个重载函数，分别是
	//iterator begin();
	//const_iterator begin() const;
	//调用他们的对象，分别是可以修改和不可修改的
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}

对string 对象s1逆向遍历输出，代码如下所示：

	string::reverse_iterator r_it = s.rbegin();
	while (r_it != s.rend())
	{
		cout << *r_it << " ";
		r_it++;
	}

二.迭代器的意义： 

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

三.迭代器的分类：

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

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

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

（3）正向迭代器：假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。实际对应的类型有：forward_list，unordered_map，unordered_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 之间的元素个数减一）。

 实际对应的类型有：vector，deque

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(20);
	v.push_back(3);
	v.push_back(10);
 
	//这里的sort函数需要用到随机访问迭代器，而vector对象的迭代器是随机迭代器，可用sort排序
	sort(v.begin(), v.end());
 
	list<int> a;
	a.push_back(1);
	a.push_back(20);
	a.push_back(3);
	a.push_back(10);
 
	//这里的sort函数需要用到随机访问迭代器，而list对象的迭代器是双向迭代器，不可用sort排序
	sort(a.begin(), a.end());
	//zhc::Test();
	return 0;
}

四.迭代器失效：

 我们以vector来讲解迭代器失效的问题，vector迭代器失效大多发生在改变vector容量，删除vector中元素等情况，因为迭代器是类似于指针的功能，他能够遍历整个vector数组，当vector改变容量的时候，迭代器指向的vector中的元素就可能会发生变化，这样子，迭代器就失去了它原本的意义，导致迭代器失效，另外也有可能，当vector扩容的时候，会配置新的空间，而释放原本的空间，这就导致正在使用的迭代器指向的vector空间被释放，从而导致迭代器失效，以下面代码和图为例说明。

（1）删除元素导致的迭代器失效：

	void Test()
	{
		// 三种场景去测试
		// 1 2 3 4 5 -> 正常
		// 1 2 3 4   -> 崩溃
		// 1 2 4 5   -> 没删除完
		vector<int> a;
		a.push_back(1);
		a.push_back(2);
		a.push_back(3);
		a.push_back(4);
		a.push_back(5);
		vector<int>::iterator pos = a.begin();
		//删除vector中的偶数
		while (pos != a.end())
		{
			if (*pos % 2 == 0)
			{
				a.erase(pos);
			}
			++pos;
		}
		for (auto e : a)
		{
			cout << e << endl;
		}
	}

解决方法：

每删除一个元素，就更新一次迭代器，是迭代器永远指向被删除位置的那个元素。 

 （2）扩容导致的迭代器失效：

解决方法：

每次扩容之前都把pos的相对位置记录下来，然后扩容之后，更新pos位置 

 

		iterator insert(iterator pos, const T& x)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _endofstorage)
			{
				//扩容可能会导致pos失效，所以需要在扩容之前记录pos的位置，扩容后更新一下pos
				int len = pos - _start;
				reverve(capacity() == 0 ? 4 : 2 * capacity());
				iterator pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *(end);
			}
			*(pos) = x;
			_finish++;
 
			return pos;
		}