c++ - 为什么我机器上的 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;
}

结果很奇怪:

在调试中: map :0.289无序 map :10.738 HashMap :10.58按任意键继续 。 . .

在发布中: map :0.101无序映射:0.463 HashMap :0.429按任意键继续 。 . .

Answer 1

1. 您只在每张 map 中插入 65536 个项目——不足以让 O(log N) 和 O(1) 之间的差异表示很多。
2. 您仅插入项目，之后不进行任何搜索。
3. 您的键都是按升序排列的连续整数——不适合任何映射的通常使用方式。

底线:这不太可能告诉您有关所讨论数据结构的太多信息。