C++迭代器失效问题及处置

VVeraVV · 发布于 2023-4-19 15:54:37

什么是迭代器

迭代器不是指针，是类模板，表现的像指针。他只是模仿了指针的一些功能，通过重载了指针的一些操作符，->,*,++ --等封装了指针，是一个“可遍历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;
}

容器是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;
}

容器是deque的情况下，插入到任何位置都会导致迭代器。
插入前迭代器处于正常状态

插入后所有迭代器失效

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

删除操作

删除操作会导致元素次序发送改变而导致迭代器失效
容器是vector或者string的情况下，在删除容器元素后，指向被删元素之前元素的迭代器有效，被删元素之后的迭代器失效
注意：当我们删除元素时，尾后迭代器总是会失效
容器是deque的情况下，假设删除的是首尾元素，则只要首尾迭代器失效，假设删除的是其他元素，则所有迭代器失效。

容器是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;
}
输出：

可以看到swap操作后，迭代器未失效，且指向相同的元素，只不过这些元素已经属于不同的容器了；

注意事项

不用在循环之前保管end返回的迭代器，不时当做容器末尾使用，因为假设在循环中添加/删除 vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总会失效。
因而在循环中我们必需反复调用end()来获取迭代器

对于删除元素导致的迭代器失效处置方法
方法1.erase§时，尾后递增当前迭代器,即erase(p++);
方法2.由于erase()可以返回一个指向被删除元素之后元素的迭代器，所以也可以直接把erase§的返回值赋给当前迭代器，即p=erase§
注意：对于vector、string这种在内存中连续存储的只能使用方法1，因为删除元素后，后面元素的迭代器也失效了
对于关联容器，也只能使用方法1，因为它们的erase操作返回值为void。

总结

以上为个人经历，希望能给大家一个参考，也希望大家多多支持网站。