C++ map和unordered_map的区别

映射和无序映射之间存在巨大差异。只有我们清楚知道两者的内部工作原理，才能决定如何选择适合的那一个使用。

不同之处：

比较项	map	unordered_map
排序	递增顺序(默认)	无排序
执行	自平衡BST(类似红黑树)	Hash Table
搜索时间	log(n)	O(1) -> 平均， O(n) -> 最坏情况
插入时间	log(n) + 重新平衡	与搜索时间相同
删除时间	log(n) + 重新平衡	与搜索时间相同

使用 `std::map`

需要有序数据。
必须打印/访问数据(按排序顺序)。
需要元素的前任/继任者。

示例代码：

// CPP program to demonstrate use of std::map
#include <bits/stdc++.h>

int main()
{
    // Ordered map
    std::map<int, int> order;

    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;

    // Iterating the map and
    // printing ordered values
    for (auto i = order.begin(); i
        != order.end(); i++) {
        std::cout << i->first
                << " : "\n                << i->second << 'n';
    }
}

运行结果：

使用 std::unordered_map

有以下情况时，可以考虑使用 std::unordered_map ：

需要保留一些数据的计数(示例 – 字符串)并且不需要排序。
需要单元素访问，即没有遍历。

// CPP program to demonstrate use of
// std::unordered_map
#include <bits/stdc++.h>

int main()
{
    // Unordered map
    std::unordered_map<int, int> order;

    // Mapping values to keys
    order[5] = 10;
    order[3] = 5;
    order[20] = 100;
    order[1] = 1;

    // Iterating the map and
    // printing unordered values
    for (auto i = order.begin();
        i != order.end(); i++)
    {
        std::cout << i->first
                << " : "\n                << i->second << 'n';
    }
}

运行结果：