std::map 与 std::unordered_map 特性对比#

概述#

基于键值对（Key-Value）的关联容器，分别提供底层为红黑树的有序存储，与底层为哈希表的无序存储。

基本用法与底层原理#

头文件：<map> 与 <unordered_map>

1
template< class Key, class T >
2
class map; // (C++98) 基于红黑树实现，按键排序
3

4
template< class Key, class T >
5
class unordered_map; // (C++11) 基于哈希表实现，无序

数据打包单元：插入数据时，容器内的每个元素是一个 std::pair<const Key, T> 对象。std::pair （头文件 <utility>）负责把键与值组合为一个具有 first（只读的 Key）和 second（可修改的 Value）的整体。
两个容器提供极为相似的 API：insert, erase, find, count, 以及 operator[]。

进阶用法与多角度对比#

1. 排序与遍历行为#

std::map 默认按键（Key）进行升序排列，可以在定义时通过提供自定义比较仿函数来改变排序规则：

1
// 默认升序（小到大）
2
std::map<int, std::string> map_asc;
3

4
// 降序排列
5
std::map<int, std::string, std::greater<int>> map_desc;

而 std::unordered_map 的迭代器遍历顺序通常表现为哈希桶的散列顺序，这不仅无序，而且在重新哈希（扩容）后甚至会发生改变。

2. 性能选择指南#

需要键保持有序（如范围查询、按顺序输出） $\rightarrow$ 使用 std::map，查找时间复杂度为 O(log N)。
只要求快速查找，不关心顺序 $\rightarrow$ 优先使用 std::unordered_map，平均查找时间复杂度为 O(1)，最坏退化为 O(N)。

示例#

1
#include <iostream>
2
#include <map>
3
#include <unordered_map>
4
#include <string>
5

6
int main() {
7
    std::map<std::string, int> scores;
8
    scores["Alice"] = 95;           // 使用 [] 赋值（若不存在则插入）
9
    scores.insert({"Bob", 87});     // 使用初始化列表插入
10
    scores.insert(std::make_pair("Charlie", 92)); // make_pair 自动推导类型
11

12
    // 查找时推荐使用 find
13
    auto it = scores.find("Bob");
14
    if (it != scores.end()) {
15
        std::cout << it->first << " : " << it->second << std::endl;
16
    }
17

18
    // 遍历：每个元素均为 const pair<const Key, Value>&
19
    for (const auto& entry : scores) {
20
        std::cout << entry.first << " -> " << entry.second << std::endl;
21
    }
22
}

算法用例：打破输入顺序的“排序陷阱”#

题目（如 P5740：最厉害的学生）：记录多名学生的各项成绩并输出总分最高的一名。如果有多个总分相同的学生，要求输出输入顺序靠前的那位。

分析：如果在代码中使用 std::map<string, vector<int>> 来保存数据：

std::map 会自动根据学生姓名的字典序进行重排，导致遍历顺序不再是输入顺序。
当调用 max_element 并在总分相同时，它会返回第一次遇到的最大值，但这个顺序是按姓名排好序后的顺序。
如果总分相同的学生字典序靠前、但输入较晚，系统会错误地输出该学生。

正确解法：舍弃关联容器，使用结构体 std::vector<Student> 保留原始输入顺序。

1
#include <iostream>
2
#include <vector>
3
#include <string>
4
#include <algorithm>
5

6
struct Student {
7
    std::string name;
8
    int total;
9
};
10

11
int main() {
12
    std::vector<Student> stu = {{"senpai", 169}, {"lxl", 147}, {"fafa", 153}};
13

14
    // vector 天然保持输入顺序，max_element 返回遇到的首个最大值
15
    auto best = std::max_element(stu.begin(), stu.end(),
16
        [](const Student& a, const Student& b) {
17
            return a.total < b.total;
18
        });
19
    std::cout << best->name;
20
}

常见问题#

operator[] 的默认构造陷阱 当键不存在时，使用 [] 访问不仅查不到结果，还会隐式地插入一个执行默认构造（例如 int 的 0）的新元素。

1
std::map<std::string, int> m;
2
// 错误：意图检查是否存在 "apple"，却导致无意插入了 ("apple", 0)
3
if (m["apple"] == 100) {}
4

5
// 正确：使用 count 或 find 查找而不引入副作用
6
if (m.find("apple") != m.end() && m["apple"] == 100) {}

遍历时修改键 在 for (const auto& entry : my_map) 循环中，entry.first 的类型强制为 const Key，无法修改键名。

复杂度#

std::map 查找、插入、删除复杂度均为 O(log N)。 std::unordered_map 查找、插入、删除平均复杂度为 O(1)，最坏（哈希冲突严重）退化为 O(N)。

关联知识点#

std::make_pair：便捷的模板函数，无需指定模板参数即可生成 std::pair。
std::multimap / std::unordered_multimap：允许存储重复键的版本。

std::map 与 std::unordered_map 特性对比