STL迭代器失效问题

STL中的容器按存储方式分为两类，一类是按以数组形式存储的容器（如：vector 、deque)；另一类是以不连续的节点形式存储的容器（如：list、set、map）。在使用erase方法来删除元素时，会涉及迭代器失效的问题，需要注意。

数组形式存储容器

1. vector

当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。
当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。
当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。

2. deque

在deque容器首部或者尾部插入元素不会使得任何迭代器失效。
在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。
在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

3. vector的特殊情况

删除一个元素并不一定会移动容器的其他元素

示例

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v{1,2,3};
    auto it = v.begin();
    v.erase(v.begin());

    cout << *it << endl;
    cout << *v.begin() << endl;

    getchar();
    return 0;
}

输出结果

1
2

2
2

虽然删除了第一个元素，但是容器内的元素并没有移动。但是必须注意的是：这种不移动是编译器无法保证的，迭代器仍然是失效的。但是迭代器本质上是一个指针，仍然指向了那一块内存区域，所以仍然能够获取那块内存的数据。

vector如何遍历删除顺序存储容器

通过erase方法的返回值来获取下一个元素的位置
不能在遍历之后，仍然使用所删除的迭代器极其++等运算得到的迭代器

非连续存储容器

4. list

插入元素对所有迭代器没有影响
删除操作仅使得指向被删除节点的迭代器失效

5. map/set

插入操作对所有迭代器没有影响
删除操作，使得被删除的节点的迭代器失效。

list如何遍历删除顺序存储容器

通过erase方法的返回值来获取下一个元素的位置
在调用erase方法之前先使用 “++”来获取下一个元素的位置
不能在遍历之后，仍然使用所删除的迭代器极其++等运算得到的迭代器

总结

综合来看，主要是要搞清楚，删除或者插入操作，有没有改变容器的内存结构，特别是连续顺序存储的容器。