概述
map 和 unordered_map 是 C++ STL 中最常用的关联容器，都提供键值对的存储和快速查找。但它们的底层实现完全不同，适用的场景也各有侧重。
简单来说：
map：基于红黑树，按键有序unordered_map：基于哈希表，按键无序，查找更快
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
| #include <iostream>
#include <map>
#include <unordered_map>
int main() {
std::map<std::string, int> m;
m["banana"] = 3;
m["apple"] = 5;
m["cherry"] = 2;
std::cout << "map (有序):" << std::endl;
for (auto& [k, v] : m) {
std::cout << " " << k << ": " << v << std::endl;
}
std::unordered_map<std::string, int> um;
um["banana"] = 3;
um["apple"] = 5;
um["cherry"] = 2;
std::cout << "\nunordered_map (无序):" << std::endl;
for (auto& [k, v] : um) {
std::cout << " " << k << ": " << v << std::endl;
}
return 0;
}
|
底层实现原理
map —— 红黑树
std::map 的底层是一棵红黑树（Red-Black Tree），它是一种自平衡二叉搜索树。
核心特性：
- 每个节点是红色或黑色
- 根节点是黑色
- 叶子节点（NIL）是黑色
- 红色节点的子节点必须是黑色
- 从任一节点到其所有叶子节点的路径上，黑色节点数相同
这些约束保证了树的高度始终为 O(log n)，从而确保：
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
| #include <iostream>
#include <map>
int main() {
std::map<int, std::string> m;
m[5] = "five";
m[3] = "three";
m[8] = "eight";
m[1] = "one";
m[4] = "four";
for (auto& [k, v] : m) {
std::cout << k << ": " << v << std::endl;
}
return 0;
}
|
unordered_map —— 哈希表
std::unordered_map 的底层是一个哈希表，核心组件：
- 哈希函数：将 key 映射到 bucket 索引
- 桶数组（buckets）：存储元素
- 冲突解决：链地址法（每个桶挂一个链表）
核心特性：
- 平均查找、插入、删除是 O(1)
- **最坏情况 O(n)**（所有 key 哈希冲突时）
- 元素无序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> um;
um[5] = "five";
um[3] = "three";
um[8] = "eight";
um[1] = "one";
um[4] = "four";
std::cout << "bucket count: " << um.bucket_count() << std::endl;
std::cout << "max load factor: " << um.max_load_factor() << std::endl;
std::cout << "load factor: " << um.load_factor() << std::endl;
std::cout << "key 3 in bucket: " << um.bucket(3) << std::endl;
std::cout << "bucket 3 has " << um.bucket_size(3) << " elements" << 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
| #include <iostream>
#include <map>
#include <unordered_map>
int main() {
std::map<std::string, int> m;
m["apple"] = 5;
m.insert({"banana", 3});
m.insert(std::make_pair("cherry", 2));
m.insert(std::pair<std::string, int>("date", 7));
auto [it, success] = m.insert({"apple", 10});
if (!success) {
std::cout << "apple already exists, value: " << it->second << std::endl;
}
m.emplace("elderberry", 4);
m.try_emplace("fig", 6);
m.insert_or_assign("apple", 10);
m.insert_or_assign("grape", 8);
for (auto& [k, v] : m) {
std::cout << k << ": " << v << 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
| #include <iostream>
#include <map>
int main() {
std::map<std::string, int> m = {{"apple", 5}, {"banana", 3}};
auto it = m.find("apple");
if (it != m.end()) {
std::cout << "Found: " << it->first << " = " << it->second << std::endl;
}
if (m.count("banana")) {
std::cout << "banana exists" << std::endl;
}
int val = m["cherry"];
std::cout << "cherry (auto-inserted): " << val << std::endl;
try {
int v = m.at("apple");
std::cout << "apple: " << v << std::endl;
m.at("nonexistent");
} catch (const std::out_of_range& e) {
std::cout << "Key not found: " << e.what() << std::endl;
}
if (m.contains("banana")) {
std::cout << "banana exists (C++20)" << 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
| #include <iostream>
#include <map>
int main() {
std::map<std::string, int> m = {
{"apple", 5}, {"banana", 3}, {"cherry", 2}
};
m.erase("banana");
auto it = m.find("cherry");
if (it != m.end()) {
m.erase(it);
}
std::map<int, int> nums = {{1, 10}, {2, 20}, {3, 30}, {4, 40}, {5, 50}};
auto first = nums.begin();
auto last = nums.find(4);
nums.erase(first, last);
size_t count = m.erase("apple");
std::cout << "Erased " << count << " elements" << 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
| #include <iostream>
#include <map>
int main() {
std::map<std::string, int> scores = {
{"Alice", 95}, {"Bob", 87}, {"Charlie", 92}
};
for (const auto& [name, score] : scores) {
std::cout << name << ": " << score << std::endl;
}
std::cout << "\nReverse order:" << std::endl;
for (auto it = scores.rbegin(); it != scores.rend(); ++it) {
std::cout << it->first << ": " << it->second << std::endl;
}
std::cout << "\nAll scores: ";
for (const auto& [_, score] : scores) {
std::cout << score << " ";
}
std::cout << std::endl;
std::cout << "All names: ";
for (const auto& [name, _] : scores) {
std::cout << name << " ";
}
std::cout << std::endl;
return 0;
}
|
自定义 Key 类型
map —— 自定义比较器
map 要求 key 支持比较（默认 < 运算符）。自定义类型需要提供比较器：
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
| #include <iostream>
#include <map>
#include <string>
struct Person {
std::string name;
int age;
bool operator<(const Person& other) const {
if (age != other.age) return age < other.age;
return name < other.name;
}
};
int main() {
std::map<Person, std::string> m1;
m1[{"Alice", 25}] = "Engineer";
m1[{"Bob", 30}] = "Manager";
m1[{"Charlie", 25}] = "Designer";
for (const auto& [person, role] : m1) {
std::cout << person.name << " (" << person.age << "): " << role << std::endl;
}
auto cmp = [](const Person& a, const Person& b) {
if (a.name != b.name) return a.name < b.name;
return a.age < b.age;
};
std::map<Person, std::string, decltype(cmp)> m2(cmp);
m2[{"Alice", 25}] = "Engineer";
return 0;
}
|
unordered_map —— 自定义哈希函数
unordered_map 要求 key 支持 == 比较和哈希函数：
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
| #include <iostream>
#include <unordered_map>
#include <string>
struct Person {
std::string name;
int age;
bool operator==(const Person& other) const {
return name == other.name && age == other.age;
}
};
struct PersonHash {
size_t operator()(const Person& p) const {
size_t h1 = std::hash<std::string>{}(p.name);
size_t h2 = std::hash<int>{}(p.age);
return h1 ^ (h2 << 1);
}
};
int main() {
std::unordered_map<Person, std::string, PersonHash> um;
um[{"Alice", 25}] = "Engineer";
um[{"Bob", 30}] = "Manager";
for (const auto& [person, role] : um) {
std::cout << person.name << ": " << role << 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
| #include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <string>
const int N = 1000000;
void benchmark() {
std::vector<std::string> keys;
keys.reserve(N);
for (int i = 0; i < N; i++) {
keys.push_back("key_" + std::to_string(i));
}
{
auto start = std::chrono::high_resolution_clock::now();
std::map<std::string, int> m;
for (int i = 0; i < N; i++) {
m[keys[i]] = i;
}
for (int i = 0; i < N; i++) {
auto it = m.find(keys[i]);
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "map: "
<< std::chrono::duration<double, std::milli>(end - start).count()
<< " ms" << std::endl;
}
{
auto start = std::chrono::high_resolution_clock::now();
std::unordered_map<std::string, int> um;
um.reserve(N);
for (int i = 0; i < N; i++) {
um[keys[i]] = i;
}
for (int i = 0; i < N; i++) {
auto it = um.find(keys[i]);
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "unordered_map: "
<< std::chrono::duration<double, std::milli>(end - start).count()
<< " ms" << std::endl;
}
}
int main() {
benchmark();
return 0;
}
|
常见陷阱
1. [] 的副作用——会插入默认值
1
2
3
4
5
6
7
8
9
10
11
| std::map<std::string, int> m = {{"apple", 5}};
if (m["banana"] > 0) {
std::cout << "found" << std::endl;
}
if (m.find("banana") != m.end()) { ... }
if (m.contains("banana")) { ... }
|
2. unordered_map 的 rehash 导致性能抖动
1
2
3
4
5
6
7
8
9
10
11
12
|
std::unordered_map<int, int> um;
for (int i = 0; i < 1000000; i++) {
um[i] = i * 2;
}
std::unordered_map<int, int> um;
um.reserve(1000000);
for (int i = 0; i < 1000000; i++) {
um[i] = i * 2;
}
|
3. 迭代器稳定性
1
2
3
4
5
6
7
8
9
10
11
12
13
| std::map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};
auto it1 = m.find(3);
m.insert({0, 0});
std::unordered_map<int, int> um = {{1, 10}, {2, 20}, {3, 30}};
auto it2 = um.find(3);
um.insert({0, 0});
|
如何选择？
| 考量因素 |
选 map |
选 unordered_map |
| 需要有序遍历 |
✅ |
❌ |
| 需要 lower_bound/upper_bound |
✅ |
❌ |
| 查找性能最重要 |
❌ (O(log n)) |
✅ (O(1)) |
| Key 不支持哈希 |
✅ |
❌ |
| 内存占用敏感 |
✅（3个指针/节点） |
❌（哈希表开销大） |
| 迭代器稳定性要求高 |
✅ |
❌ |
经验法则：大多数场景下 unordered_map 更快，选它。需要有序性或范围查询时才选 map。
