为什么我机器上的hash_map和unordered_map非常慢？

Question

我用这段代码测试了它们(在Visual Studio 2010 sp1上):

#include <ctime>
#include <iostream>
#include <map>
#include <unordered_map>
#include <hash_map>

int main()
{ 
    clock_t time;
    int LOOP = (1 << 16);
    std::map<int, int> my_map;
    std::unordered_map<int, int> map_unordered_map;
    std::hash_map<int, int> my_hash_map;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_map[i] = i;
    }
    std::cout << "map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        map_unordered_map[i] = i;
    }
    std::cout << "unordered_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_hash_map[i] = i;
    }
    std::cout << "hash_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

结果很奇怪:

在DEBUG中:map:0.289 unordered_map:10.738 hash_map:10.58按任意键继续...

在RELEASE中:map:0.101 unordered_map:0.463 hash_map:0.429按任意键继续...

Answer 1

1. 您只在每个地图中插入65536个项目 - 不足以使O(log N)和O(1)之间的差异意味着很多.
2. 你只是插入物品,之后没有进行任何搜索.
3. 您的键是按顺序递增的所有连续整数 - 不适合通常使用任何映射的方式.

结论:这不太可能告诉您有关数据结构的更多信息.