c++ map 和 unorder_map 在遍历时候的性能

使用背景

我需要一个容器，它必须具有查询、遍历的功能，增加和删除不是很多。因此可以选择：

• map
• unorder_map

听网上说：map 是有序的，在遍历的时候会快一些。究竟是不是这样？

测试代码

/*
@ author: yinzp
@ detail: 测试有序字典和无序字典的性能
@ conclusion: 即使在遍历的时候，有序似乎没有比无序字典的速度好
*/

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

int main() {
    const int numElements = 1000000;

    // 测试有序字典的性能
    {
        std::map<int, int> orderedDict;
        
        // 向有序字典中插入数据
        for (int i = 0; i < numElements; ++i) {
            orderedDict[i] = i;
        }

        // 测量顺序访问有序字典的时间
        auto startTime = std::chrono::high_resolution_clock::now();

        for (const auto& pair : orderedDict) {
            // 顺序访问每个元素
            int key = pair.first;
            int value = pair.second;
        }

        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();

        std::cout << "有序字典顺序访问时间: " << duration << " 毫秒" << std::endl;
    }

    // 测试无序字典的性能
    {
        std::unordered_map<int, int> unorderedDict;
        
        // 向无序字典中插入数据
        for (int i = 0; i < numElements; ++i) {
            unorderedDict[i] = i;
        }

        // 测量顺序访问无序字典的时间
        auto startTime = std::chrono::high_resolution_clock::now();

        for (const auto& pair : unorderedDict) {
            // 顺序访问每个元素
            int key = pair.first;
            int value = pair.second;
        }

        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();

        std::cout << "无序字典顺序访问时间: " << duration << " 毫秒" << std::endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

输出

有序字典顺序访问时间: 10 毫秒
无序字典顺序访问时间: 11 毫秒

结论

在 10w 数量级别上，似乎没有差距。还是用 哈希map，毕竟空间还小一些。