关于stl容器的迭代器失效问题

场景

  在项目中使用stl容器的时候，多线程环境下出错，调试很久发现问题是使用容器的时候由于容器扩容导致的线程不安全，还有扩容导致的迭代器失效问题，于是就想着把迭代器失效的问题总结一下。

场景重现1
  我在项目开发中使用vector时，由于扩容导致的迭代器失效。

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <unordered_map>
#include <thread>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);
    auto iter = find(v.begin(), v.end(), 1);  //iter指向的是数组中第一个元素
    cout << "iter所指元素的值:" << *iter << endl;
    cout << "容器容量capacity:" << v.capacity() << endl << endl;

    for (int i = 0; i < 10; i++)
    {
        v.push_back(666);
    }
    
    cout << "iter所指元素的值:" << *iter << endl;
    cout << "容器容量capacity:" << v.capacity() << endl;
    return 0;
}

运行结果：可以看到，iter迭代器一开始指向的元素是1，但是由于vector底层扩容，导致元素从一个空间迁移到另一个空间，原来的空间释放，iter指向了已经释放的内存（悬挂指针），从而导致结果出错。

场景重现2
  在我另一个项目里面使用到了unordered_map，但是和前面的迭代器失效不一样，这里是一个线程在执行find函数的时候，另一个线程插入元素，导致哈希表扩容rehash，从而原来应该在哈希表中的数据find不到出现错误。

  调用find函数的流程：哈希表每个元素可以看做是一个桶，下满挂着的是链表（或者是红黑树）,调用find的时候首先会通过哈希映射找到对应的桶，然后在桶下面去遍历找对应的键，如果找不到就会返回umap.end()；

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <unordered_map>
#include <thread>
#include <algorithm>
using namespace std;

int main()
{
    // unordered_map线程不安全
    unordered_map<int, int> umap;
    umap[3] = 1;
    thread t1([&]()
    {
        for (int i = 0; i < 100000; i++)
        {
            auto iter = umap.find(3);
            iter->second = 3;
        } 
    });
    t1.detach();

    thread t2([&]()
    {
        for (int i = 10; i < 100000; i++)
        {
            umap[i] = i;
        } 
    });
    t2.detach();

    return 0;
}

  运行结果：可能会运行成功，但是有时候也会报段错误。使用gdb调试可以看到，在通过iter访问值的时候，会报错，但是3在umap中是一定存在的，我们一开始就已经初始化了键为3的值。
  原因：当一个线程在调用find函数的时候，通过哈希映射找到了桶的指针，此时另一个线程往umap中插入元素导致哈希表扩容rehash，每个桶指针从原来的内存迁移到另一个内存空间中，此时find继续往后找就会找到nullptr，于是就返回umap.end()，里面是一个空指针，通过空指针去访问变量自然会报段错误。

其他

   vector底层是连续的内存空间，除了扩容导致的迭代器失效，即使没有发生扩容，插入元素也会导致后面的迭代器失效，因为插入位置之后的元素都会向后移动，使得原来的迭代器不再指向原来的元素。删除也是同理，也会造成插入位置之后的迭代器都失效，同时删除位置的迭代器也会失效。
   list底层是不连续的内存空间，所以插入元素，扩容都不会导致迭代器失效，但是删除元素会导致指向删除元素的迭代器失效。

如何解决删除的时候迭代器失效的问题：

    for (auto iter = v.begin(); iter != v.end();)
    {
        if (*iter % 2 == 0)
        {
            iter = v.erase(iter);
        }
        else
        {
            ++iter;
        }
    }

  可以使用如上所示的方法，删除数组中所有的偶数，删除后erase会返回下一个元素的迭代器，用它重新赋值迭代器即可。

测试程序

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <unordered_map>
#include <thread>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (auto num : v)
    {
        cout << num << endl;
    }
    for (auto iter = v.begin(); iter != v.end();)
    {
        if (*iter % 2 == 0)
        {
            iter = v.erase(iter);
        }
        else
        {
            ++iter;
        }
    }
    cout << "***" << endl;
    for (auto num : v)
    {
        cout << num << endl;
    }

    return 0;
}

运行结果