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时，我遇到了“超时”错误。

- Yash Aggarwal

---

unordered_set 是解决这个问题的正确数据结构。 - Omnifarious

输入数组是否保证以任何顺序排列？负值是否允许？ - Omnifarious

@Omnifarious，没有真正的模式，负值可能存在。约束条件并不明确，但是一个O(n^2)算法应该可以通过。 - Yash Aggarwal

出于好奇，我想到了一种有些不同的解决方法，涉及对值进行排序，这也是n^2复杂度，但乘数要低得多。它主要努力限制查找答案的范围。它假设没有重复的值。您可以在此处找到它们：https://godbolt.org/z/JeLsOQ - Omnifarious

@Omnifarious 对不起，一开始我没有理解，然后就把它放在了后面，直到现在。这种方法似乎类似于双指针方法。在实际情况下，这种方法是否比我使用的方法更好？ - Yash Aggarwal

除非情况需要非常注重性能，否则我不会选择它。它的主要问题是其工作方式明显较少明显，并且它很“琐碎”，有很多移动部件。在没有一个真正好的理由的情况下，这总是不好的。尽管如此，这个问题仍然困扰着我。我觉得一定有一个n log n的解决方案，一旦有人看到它，它会变得显而易见和优雅。 - Omnifarious

Answer 1

使用 [] 操作符比 find() 方法慢的原因主要有两个：

1. [] 操作符在 map 上调用了一个非 const 函数，从而阻止了各种优化，如循环展开。
2. 更重要的原因是：[] 操作符会创建不存在的元素，并将它们的值设置为默认值。map 将充斥着所有 A[i] + A[j] 对，这些对之前不在 map 中，且将它们的值设置为 0。这会增加 map 的大小，从而增加时间。

我认为你的性能测试结果没有显示出两种方法之间的差异，可能是以下一种或多种原因造成的：

1. 输入向量太小，无法产生差异
2. A[i] + A[j] 的大部分组合已经存在于向量中，因此 unordered_map 不会充斥到足以产生影响的程度
3. 你没有对代码进行优化（使用 -O3 或 -Os 选项）。

- MofX

---

我使用了在平台上失败的相同测试用例。我认为我的测量结果没有显示出任何显著差异，因为我没有进行优化。由于某些原因，我无法在我的系统上使用o2或o3进行优化。一旦我解决了这个问题，我会更新这个评论并公布结果。谢谢。 - Yash Aggarwal

通过 O3 优化，unordered_map.find() 的速度大约比 unordered_map.at() 快6倍。 - Yash Aggarwal