什么是迭代器失效问题？

问题一

删除第一个偶数元素

int main() {
	vector<int> vec;
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it % 2 == 0) {
			vec.erase(it);
			break;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

删除所有偶数元素

int main() {
	vector<int> vec;
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it % 2 == 0) {
			vec.erase(it);
			// break;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

为什么删除第一个偶数元素正常，删除所有的偶数元素就报错呢？

这是因为删除第一个偶数元素后，此迭代器就失效了，不能再进行++

问题二

在第一个偶数前插入一个比该偶数小1的奇数

int main() {
	vector<int> vec;
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it % 2 == 0) {
			vec.insert(it, *it-1);
			break;
		}
	}

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

在第所有偶数前插入一个比该偶数小1的奇数

int main() {
	vector<int> vec;
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it % 2 == 0) {
			vec.insert(it, *it-1);
			// break;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

同理，迭代器在第一个insert后就失效了

分析问题

当删除88这个元素后，从指向88的迭代器开始，到容器末尾这个区间内，所有的迭代器都失效了（容器开始到删除点区间内迭代器是有效的），再对迭代器操作就会报错。

同理，增加一个元素后，容器开始到增加点区间内迭代器是有效的，从增加点到容器末尾的迭代器都会失效

增加还有一种情况是扩容，扩容需要重新申请新的内存，将老内存的数据拷贝到新内存中，然后释放老内存，即原来的迭代器全部失效

解决迭代器失效问题

对insert和erase点的迭代器进行更新。insert和erase方法都会返回一个新的迭代器，这个迭代器就指向insert和erase的点，我们接收这个返回值，再往后进行遍历即可

int main() {
	vector<int> vec;

	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (int val : vec) {
		cout << val << " ";
	}
	cout << endl;
	
	for (auto it = vec.begin(); it != vec.end();) {
		if (*it % 2 == 0) {
			it = vec.erase(it);
		}
		else {
			it++;
		}
	}
	for (int val : vec) {
		cout << val << " ";
	}

	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

这样就成功删除了所有的偶数

int main() {
	vector<int> vec;

	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for (int val : vec) {
		cout << val << " ";
	}
	cout << endl;
	
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it % 2 == 0) {
			// 由于插入新元素后，会返回插入点的迭代器，原来指向的偶数会后移，下一次循环我们不希望再指向后移的偶数，需要++两次
			it = vec.insert(it, *it - 1);
			it++;
		}
	}
	for (int val : vec) {
		cout << val << " ";
	}
	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

可以看到，我们在所有的偶数前都有了一个小1的奇数

当我们insert或erase后，迭代器底层会将当前迭代器指向容器的指针置空（迭代器不仅要指向容器元素，还有一个成员记录指向的是哪个容器对象），并把操作点到容器末尾的迭代器全部释放（底层会把所有被用户获取的迭代器都用一个链表保存起来，遍历链表，即可释放迭代器），如果我们再操作已经释放的空间或变量，则会报错

底层会把所有被用户获取的迭代器都用一个链表保存起来，遍历链表，即可检查处于失效区间的迭代器，并进行释放迭代器

不同容器对象的迭代器比较是没有意义的，同时也不能比较，这会报错