在线GDB C++编译器调试突然停止的原因及代码问题排查

问题描述 #

我在做GeeksforGeeks上的「Count More than n/k Occurences」问题，用Moore投票算法的扩展写了代码，已经过了32个测试用例，但第33个测试用例输出结果是2，正确答案应该是3。另外用在线GDB调试时，代码执行到标记的注释行就突然停了，没法继续运行，想弄明白这俩问题的原因。

代码实现 #

#include<bits/stdc++.h>
using namespace std;

int countOccurence(int arr[], int n, int k) {
    unordered_map<int,int> mp;
    for(int i=0;i<n;i++)
    {
        if(mp.find(arr[i])!=mp.end())
        {
            mp[arr[i]]++;
        }
        else if(mp.size()<k-1)
        {
            mp.insert({arr[i],1});   
        }
        else{
            for(auto &i:mp)
                i.second--;
            for(auto &i:mp)
                if(i.second<1)  // debugger stops here<--
                    mp.erase(i.first);
        }
    }
    int res=0;
    
    for(auto i:mp)
    {   
        int count=0;
        for(int j=0;j<n;j++)
        {
            if(arr[j]==i.first)
                count++;
        }
        if(count>n/k)
            res++;
    }
    return res;
}
int main()
{
    int arr[] = {54 ,214 ,548 ,54 ,32 ,34 ,32};
    cout<<countOccurence(arr,7,4);
}

问题原因 #

1. 调试器突然停止的原因 #

你在使用范围for循环遍历unordered_map的同时调用了erase方法，这会导致迭代器失效。范围for循环本质上依赖容器的迭代器进行遍历，当你删除容器中的元素时，当前迭代器会变成无效状态，调试器检测到这种非法内存访问，就会直接终止程序。

2. 测试用例结果错误的原因 #

同样是上述的迭代器失效问题，导致map中计数小于1的元素没有被正确清理，后续统计真实出现次数时，候选元素集合包含了不该存在的元素，或者漏掉了应该保留的元素，最终计算出的结果和正确答案不符。

修复方案 #

把原来在范围for循环里直接erase的代码，改成用迭代器安全遍历并删除的方式：

// 替换原来的erase循环部分
auto it = mp.begin();
while (it != mp.end()) {
    if (it->second < 1) {
        it = mp.erase(it); // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

修改后的完整代码中，else块应该是：

else{
    for(auto &i:mp)
        i.second--;
    // 安全删除计数小于1的元素
    auto it = mp.begin();
    while (it != mp.end()) {
        if (it->second < 1) {
            it = mp.erase(it);
        } else {
            ++it;
        }
    }
}

内容的提问来源于stack exchange，提问作者Mithilesh yadav