[c++]遍历map时要注意的一个小问题

我们都知道用迭代器遍历容器的时候，如果对容器进行插入或者删除操作，会造成迭代器失效，从而无法正常遍历。但有时候对容器的插入或者删除操作不是那么显而易见。

比如考虑这样一个题目：给定一个数组，对于数组中的数字k，如果数组中存在k+1出现的次数比k出现的次数多，则输出k

如果写下如下的代码：

#include <bits/stdc++.h>
using namespace std;
vector<int> work(const vector<int>& nums)
{
    map<int,int> counter;
    for(const int& x:nums)
    {
        ++counter[x];
    }
    vector<int> ret;
    for(const auto&[k,v]:counter)
    {
        if(counter[k+1]>counter[k])
            ret.emplace_back(k);
    }
    return ret;
}
int main()
{
    vector<int> nums{1,1,2,2,2,3,3,3,3};
    vector<int> ret = work(nums);
    for(const int& x:ret)
    {
        cout<<x<<" ";
    }
    cout<<endl;
    return 0;
}

就出错了。。。

在我的测试环境下，debian，g++，得到的结果是一直运行，类似死循环了。。

问题在哪呢？问题在于在遍历counter这个map的时候，for循环中有一句： if(counter[k+1]>counter[k])

这一句话中 counter[k+1] 进行了什么操作呢？如果counter中有k+1这个key，就会返回对应的value。但是如果不存在k+1这个key，就会创建一个key=k+1,并对对应的value执行默认初始化。

因此如果counter中没有k+1这个key，执行counter[k+1]就会对counter进行插入的操作。相当于counter.emplace(k+1,0)

因为在遍历过程中对容器进行了插入操作，造成了迭代器失效，所以这个遍历的循环无法正常终止，就一直循环了。。估计会直到碰到无法访问的内存才会报错然后退出。

将work函数改下即可正常运行：

vector<int> work(const vector<int>& nums)
{
    map<int,int> counter;
    for(const int& x:nums)
    {
        ++counter[x];
    }
    vector<int> ret;
    for(const auto&[k,v]:counter)
    {
        auto it = counter.find(k+1);
        if(it!=counter.end()&&it->second>counter[k])
            ret.emplace_back(k);
    }
    return ret;
}