c++ - 为什么在unordered_map中使用find()比直接读取要快很多？

Question

这很难描述，所以我只展示代码:

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

int main() 
{ 
    clock_t start, end; 
    unordered_map<int, int> m;
    long test=0;
    int size = 9999999;
    for (int i=0; i<size/3; i++) {
        m[i] = 1;
    }
    start = clock(); 
    for (int i=0; i<size; i++) {
        //if (m.find(i) != m.end())
            test += m[i];
    }
    end = clock(); 
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    cout << "Time taken by program is : " << fixed  
         << time_taken << setprecision(5); 
    cout << " sec " << endl; 
    return 0; 
} 

结果(3次): 没有 if (m.find(i) != m.end()):

Time taken by program is : 3.508257 sec 
Time taken by program is : 3.554726 sec 
Time taken by program is : 3.520102 sec 

用if (m.find(i) != m.end()):

Time taken by program is : 1.734134 sec 
Time taken by program is : 1.663341 sec 
Time taken by program is : 1.736100 sec 

谁能解释一下为什么？当 key 没有出现时，add m[i] 到底发生了什么？

Answer 1

在这一行

test += m[i];

operator[] 做两件事:首先它尝试找到给定键的条目，然后如果该条目不存在则创建一个新条目。

另一方面:

if (m.find(i) != m.end())
        test += m[i];

operator[] 只做一件事:它找到具有给定键的元素(并且因为您之前检查过它存在，所以不必构造新条目)。

由于映射仅包含最大 size/3 的键，您的结果表明创建元素的开销超过了首先检查元素是否存在的开销。

在第一种情况下， map 中有 size 元素，而在第二种情况下， map 中只有 size/3 元素。 请注意，映射中的元素越多，调用 operator[] 的开销就越大。是Average case: constant, worst case: linear in size. find 也是如此。但是，多次调用这些方法，最坏的情况应该分期偿还，剩下的就是平均常量。

感谢 Aconcagua 指出您没有在 map 中预留空间。在第一种情况下，您添加了许多需要分配空间的元素，而在第二种情况下， map 的大小在您测量的部分期间保持不变。尝试在循环之前调用 reserve。我天真地希望在那种情况下循环会非常相似。