C++迭代器失效问题及解决_C/C++

什么是迭代器

迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，通过重载了指针的一些操作符，->,*,++ --等封装了指针，是一个“可遍历STL（ Standard Template Library）容器内全部或部分元素”的对象，本质是封装了原生指针，他可以根据不同类型的数据结构来实现不同的++，–，*等操作；

迭代器只能指向容器,而指针还可以指向函数，

迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用*取值后的值而不能直接输出其自身。

迭代器失效

迭代器失效就是迭代器底层对应指针所指向的空间倍销毁了，导致使用了一块已经被释放了的空间。

容器操作可能使迭代器失效，一个失效的迭代器将不再表示任何元素。使用失效的迭代器是一个严重的程序设计错误，很可能产生与使用未初始化化指针一样的问题。

顺序容器迭代器失效

添加操作

容器是vector或者string的情况下，在向容器添加元素后，如果容器扩容，即容器的存储空间重新分配，则指向容器的迭代器失效。

以vector为例，当我们插入一个元素时它的预分配空间不够时，它会重新申请一段新空间，将原空间上的元素复制到新的空间上去，以满足vector元素要求连续存储的目的，而原空间会被系统撤销或征做他用，于是指向原空间的迭代器就成了类似于“空悬指针”一样的东西，指向了一片非法区域，从而使得指向原空间的迭代器失效。

int main()
{
	vector<int>v1;
	vector<int>::iterator it1 = v1.begin();
	for (int i = 0;i < 10;i++) {
		v1.push_back(i);
		cout << "Size:" << v1.size() << "  Capacity:" << v1.capacity() << "  address:" << &v1[0] << endl;
	}
	return 0;
}

C++迭代器失效问题及解决

容器是vector或者string的情况下，在向容器添加元素后，如果容器未扩容，则指向插入位置之前的元素的迭代器有效，但指向插入位置之后元素的迭代器将会失效，这是因为插入位置后的元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素。

对于push_back()操作，end操作返回的迭代器肯定失效

int main()
{
	vector<int>v1 = { 0,1,2,3 };
	v1.reserve(10);//分配至少能容纳10个元素的内存空间
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.begin() + 1;
	vector<int>::iterator it3 = v1.begin() + 2;
	v1.insert(v1.begin() + 2, 4);
	while (it1 <= it2) {	//输出0 1
		cout << *it1 << endl;
		it1++;
	}
	cout << *it3 << endl; //此时该迭代器已失效，指向非法的区域
	return 0;
}

C++迭代器失效问题及解决

容器是deque的情况下，插入到任何位置都会导致迭代器。

插入前迭代器处于正常状态

C++迭代器失效问题及解决

插入后所有迭代器失效

C++迭代器失效问题及解决

容器是list和forward_list的情况下，插入到任何位置，指向容器的迭代器仍然有效，

删除操作

删除操作会导致元素次序发送改变而导致迭代器失效

容器是vector或者string的情况下，在删除容器元素后，指向被删元素之前元素的迭代器有效，被删元素之后的迭代器失效

注意：当我们删除元素时，尾后迭代器总是会失效

容器是deque的情况下，如果删除的是首尾元素，则只有首尾迭代器失效，如果删除的是其他元素，则所有迭代器失效。

C++迭代器失效问题及解决

容器是list和forward_list的情况下，删除任何元素，仅仅会使被删除元素的迭代器失效，这是因为 list 之类的容器，使用了链表来实现，插入、删除一个结点不会对其他结点造成影响。

关联容器迭代器失效

对于关联容器map、multimap、set、multiset，底层是使用红黑树实现的，所以删除某个元素，仅仅会删除元素的迭代器失效。

插入、删除一个结点不会对其他结点造成影响。

swap()操作迭代器为什么不失效

因为swap操作不会对容器的任何元素进行拷贝、删除或插入操作，也意味着元素不会被移动，这也就是迭代器为什么不失效的原因，因为指向容器的迭代器swap操作之后，仍指向swap操作之前所指向的那些元素，只不过这些元素已经属于不同的容器了

注意：对于string容器调用swap操作会导致迭代器失效，而swap两个array会真正交换它门的元素

int main()
{
	vector<int>v1 = { 0,1,2,3 };
	vector<int>v2 = { 4,5,6,7};
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v2.begin();
	vector<int>::iterator tmp1 = v1.begin();
	vector<int>::iterator tmp2 = v2.begin();
	cout << "v1: ";
	for (const auto&n : v1) {
		cout << n << " ";
	}
	cout << endl;
	cout << "v2: ";
	for (const auto&n : v2) {
		cout << n << " ";
	}
	cout << endl;
	while (it1 != v1.end()) {
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
	while (it2 != v2.end()) {
		cout << *it2 << " ";
		it2++;
	}
	cout << endl;
	swap(v1, v2); //交换容器v1,v2;
	it1 = tmp1;
	it2 = tmp2;
	cout << "v1: ";
	for (const auto&n : v1) {
		cout << n << " ";
	}
	cout << endl;
	cout << "v2: ";
	for (const auto&n : v2) {
		cout << n << " ";
	}
	cout << endl;
	while (it1 != v2.end()) {
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
	while (it2 != v1.end()) {
		cout << *it2 << " ";
		it2++;
	}

	cout << endl;
	return 0;
}

输出：

C++迭代器失效问题及解决