C++ unordered_map operator[ ] 对比 unordered_map.find() 性能

Question

我正在 interviewbit.com 上解决竞争性编程问题我基本上使用 unordered_map 来跟踪访问过的数字。当我使用 operator[] 时，我的代码无法及时执行，但是当我使用 find 时它通过了所有测试。两者应该具有相同的时间复杂度。

我尝试使用 clock() 对两个代码进行计时，方法是运行对它们进行 10 次计算，并对运行次进行平均，它们都给出了或多或少相同的时间。我用的是g++ 7.4.0，网站提供的环境是g++ 4.8.4。会不会是这个原因。

int Solution::solve(vector<int> &A) {
    unordered_map<long long, int> hashmap;
    for(auto a : A)
        hashmap[a] = 1;
    int res = 0;
    for(int i = 0; i < A.size(); ++i){
        for(int j = i + 1; j < A.size(); ++j){
          // if(hashmap.find((long long)A[i] + A[j]) != hashmap.end())
            if(hashmap[(long long)A[i] + A[j]] == 1)
                ++res;
        }
    }
    return res;
}

问题是在数组中找到其和也存在于数组中的对。当我使用 [] 运算符时，我得到的数组大小约为 900 "time limit exceeded"。

Answer 1

[]-operator 会比 find 慢的原因有两个：

[]-operator 在地图上正确调用非常量函数，防止各种优化，如循环展开。
更重要的原因：[]-运算符使用默认值在地图中创建不存在的元素。地图将被所有之前不在地图中的 A[i] + A[j] 对膨胀，并将它们的值设置为 0。这将增加地图大小，从而增加时间。

由于以下一个或多个原因，我认为您的性能测量显示两个备选方案之间没有差异：

输入向量太小，无法产生差异
A[i] + A[j] 的大多数组合已经在向量中，因此 unordered_map 没有膨胀到足以产生差异
您没有优化您的代码（-O3 或 -Os）您的代码

C++ unordered_map operator[ ] 对比 unordered_map.find() 性能

C++ unordered_map operator[ ] vs unordered_map.find() performance

c++

unordered-map

hashmap

time-complexity