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;
}

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