c++STL使用时的迭代器失效问题

迭代器失效本质上有两种情况：

????????一是pos的意义变了（指向的位置不是想要指向位置），二是pos变成了野指针（使用了一块已经被释放了的空间）。

????????迭代器失效会导致程序出现莫名其妙的越界访问、编译报错和获取的位置跟预期不符

STL容器迭代器失效分3类讨论

序列式容器迭代器失效

? ? ? ? 容器底层内存连续，允许随机访问。常见下面成员函数的使用可能会导致迭代器失效，本质上还是分 内存重新分配导致的全失效和元素被删除移动导致的意义改变了。

1、push_back() 使迭代器失效。

????????在容器末尾添加一个元素。如果容器有剩余空间(capacity() > size())，则直接添加新元素到容器尾部。此时，原迭代器中end()会失效，其他的都不会失效。如果容器没有剩余空间(capacity() == size())，会导致容器重新分配内存，然后将数据从原内存复制到新内存，再在尾部添加新元素。此时，由于内存重新分配，原迭代器(所有)都失效。

2、pop_back() 使迭代器失效。

?????????直接将容器中的最后一个元素删除，原迭代器中最后一个元素的迭代器和end()会失效，其余的都不会失效。

3、insert(iterator, n) 使迭代器失效。

????????如果没有内存的重新分配，原迭代器中插入点及插入点之后的迭代器(包括end())都失效。如果有内存的重新分配，原迭代器(所有)都失效。

4、erase(iterator) 使迭代器失效。

????????将删除点及之后的元素都向前移动一位，然后删除最后一个元素。因此，原迭代器中删除点之前的迭代器都有效，删除点之后的元素迭代器都失效。

vector容器迭代器失效

失效类型1--迭代器意义变了：

????????对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

明白上面的机制之后，我们就要注意在for循环里面?使用erase方法，必要时候要适当修正 已经改变意义的迭代器。

案例：

#include<iostream>
#include<vector>
 
using namespace std;
 
int main(){
    
    vector<int> q{1,2,3,4,5,6};
    //在这里想把大于2的元素都删除
    for(auto it=q.begin();it!=q.end();it++){
        if(*it>2)
            q.erase(it);//这里就会发生迭代器失效
    }
    //打印结果
    for(auto it=q.begin();it!=q.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
    return 0;
}

输出： 1 2 4 6

解决方案：

//在这里想把大于2的元素都删除
    for(auto it=q.begin();it!=q.end();)
    {
        if(*it>2)
        {
            q.erase(it);//这里删除结束，原来的空就会被后续元素补上，it会直接指向原下一个元素，因此不需要再自加了
        }
        else
        {
            it++;
        }
    }

//或：
    for(auto it=q.begin();it!=q.end();it++)
    {
        if(*it>2)
        {
            it=q.erase(it);//这里会返回指向下一个元素的迭代器，因此不需要再自加了
        }
        else
        {
            --it;
        }
    }

输出： 1 2? ?

失效类型2--直接变成野指针：

????????对于序列容器vector，deque来说，使用可能改变容器内存大小的成员函数，容器就可能重新开空间。原来的封装指针的迭代器就失去了意义:? push_back()、reserve()、insert()

????????例如，当使用push_back方法后：

• 原end返回的迭代器肯定失效（意义变了，end()代表的实际并不是容器末尾了）。
• end() 之前的迭代器则可能失效，也可能不会失效。取决于push_back操作后，容器capacity有没有变化。如果有变化则会失效，原迭代器成野指针不能再用了，都需要重新赋值。??????；capacity没有变化，原迭代器则没什么影响，正常使用。

案例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
 	vector<int> v{ 1, 2, 3, 4, 5 };
  	auto pos =find(v.begin(), v.end(), 3);
   	v.reserve(100);
    *pos = 30;

 	return 0;
}

修改：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
 	vector<int> v{ 1, 2, 3, 4, 5 };
  	auto pos =find(v.begin(), v.end(), 3);
  	//扩容导致迭代器成为野指针
   	v.reserve(100);
   	
   	//这时如果还想更改指定位置的值，那么我们需要进行一个迭代器的更新
  	pos =find(v.begin(), v.end(), 3);
    *pos = 30;

 	return 0;
}

迭代器失效的解决方案就是：更新迭代器，或者通过矫正，让迭代器重新找回定位。

list迭代器失效

????????对于list来说，底层结构为带头双向循环链表，它使用了不连续分配的内存。

????????插入并不会导致迭代器的失效，不会扩容开辟新空间。

????????只有在删除的时候才会导致被删除结点的迭代器失效（野指针）了，其它的迭代器并不会收到影响。

关联式容器迭代器失效【map】

????对于关联容器map、multimap、set、multiset，底层是使用红黑树实现的，所以删除某个元素，仅仅会删除元素的迭代器失效。插入、删除一个结点不会对其他结点造成影响。

????????关联容器使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器。

参考：

【C++知识】关于迭代器失效的几种情况_c++迭代器失效-CSDN博客

STL迭代器失效的场景总结_stl 迭代器失效-CSDN博客

https://blog.csdn.net/qq_43148810/article/details/127088856?