C++ unordered_map访问不存在的元素出现了很奇怪的问题

LauZyHou
  • 43

下面的代码在输入[1,3,2,2,5,2,3,7]后返回5。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        //注意:子序列不要求连续,子串要求连续
        //用哈希表统计一下
        unordered_map<int,int> ump;
        for(int n:nums)
            if(ump.find(n)==ump.end())
                ump.insert(make_pair(n,1));
            else
                ump[n]++;
        int ans = 0;
        for(auto item:ump){
            if(ump.find(item.first+1)!=ump.end())
                ans = max(ans,ump[item.first+1]+ump[item.first]);
            if(ump.find(item.first-1)!=ump.end())
                ans = max(ans,ump[item.first-1]+ump[item.first]);
        }
        return ans;
    }
};

如果将14,16行的if语句注释掉,返回的竟然是1?这里明明是求max的操作,无论如何不可能得到比之前的5更小的值吧?

这是在做LeetCode 594时遇到的问题。

另外,即使使用注释掉了两个if语句后的代码,如果将输入的第一个数字1改成某些数字,如数字8,那么该函数又能正常返回5了,这是为什么?

回复
阅读 3.9k
2 个回答

这个代码我看了下,应该是求无序map的连续两个key的vaule之和的最大值,打印一下ump=std::unordered_map with 5 elements = {[7] = 1, [5] = 1, [2] = 3, [1] = 1, [3] = 2},可直观的看到2和3连续,并且ump[2]+ump[3]最大,即为5。

如果去掉两个if判断是否存在ump[key],就无法保证存在连续的key,如ump[7+1]就不存在,根据stakoverflow的描述,它会补充一个默认的值在ump[8];调试时打印ump如下

(gdb) p ump
$1 = std::unordered_map with 5 elements = {[7] = 1, [5] = 1, [2] = 3, [1] = 1, [3] = 2}
(gdb) p ump
$2 = std::unordered_map with 6 elements = {[7] = 1, [5] = 1, [2] = 3, [8] = 0, [1] = 1, [3] = 2}
(gdb) p ump
$3 = std::unordered_map with 7 elements = {[6] = 0, [3] = 2, [1] = 1, [8] = 0, [2] = 3, [5] = 1, [7] = 1}

这时候ump的size会增大,遍历一个在自增的map结局我也不知道会发生什么,我这里测试的是执行完一轮就跳出for循环了。

range-base for 相当于如下的语句:

{
  auto &&__range = ump ;
  auto __begin = ump.being() ;
  auto __end = ump.end() ;
  for ( ; __begin != __end; ++__begin ) {
    item = *__begin;
    //statement
  }
}

unordered_map 的 operator[] 是一个写操作,它会插入 unordered_map 中不存在的值。而 unordered_map 的插入操作有可能导致它的所有 iterator 失效。

使用失效的 iterator 就什么都有可能发生了(未定义行为)。

宣传栏