为什么在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 

谁能解释为什么？当密钥不出现时，加m [i]里面真正发生了什么？

Answer 1

在这条线

test += m[i];

这operator[]有两件事：首先，它尝试查找给定键的条目，然后，如果该条目不存在，它将创建一个新条目。

另一方面，这里：

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

该operator[]做的只有一件事：它查找与给定键的元素（因为你它的存在前检查，没有新的条目将建造）。

由于地图仅包含取决于size/3您结果的键，因此建议创建元素会超出首先检查元素是否存在的开销。

在第一种情况下size，地图中只有size/3元素，而在第二种情况下，地图中只有元素。请注意，operator[]地图中的元素越多，调用就会变得越昂贵。这是一般情况下：恒定的，最坏的情况：在大小呈线性关系。同样适用于find。但是，多次调用这些方法，最坏的情况应该摊销，您将获得平均常数。

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