2.2 关联容器
关联容器通过键(key)来组织数据,提供高效的查找、插入和删除操作。标准库提供两大类:有序关联容器(基于红黑树,按键排序)和无序关联容器(基于哈希表,O(1) 平均查找)。C++23 还引入了 std::flat_map——一种缓存友好的有序容器。
1. 有序关联容器
std::map<K, V> — 有序键值对
std::map 内部使用红黑树实现,所有元素按键的 operator< 排序。查找、插入、删除均为 O(log n)。
#include <map>
#include <string>
#include <iostream>
int main() {
// 初始化
std::map<std::string, int> scores{
{"Alice", 95},
{"Bob", 87},
{"Carol", 92}
};
// 插入元素
scores.insert({"Dave", 78}); // insert 方式
scores.emplace("Eve", 88); // emplace: 就地构造
scores["Frank"] = 73; // operator[]: 不存在则默认构造后赋值
// 查找
if (auto it = scores.find("Alice"); it != scores.end()) {
std::cout << it->first << ": " << it->second << "\n";
}
// C++20: contains() — 更简洁的存在性检查
if (scores.contains("Bob")) {
std::cout << "Bob is in the map\n";
}
// 删除
scores.erase("Frank");
// 遍历 — 总是按 key 升序
for (const auto& [name, score] : scores) {
std::cout << name << " -> " << score << "\n";
}
// 输出: Alice -> 95, Bob -> 87, Carol -> 92, Dave -> 78, Eve -> 88
}
提示:operator[] 在键不存在时会默认构造一个值并插入。如果只是想查找而不插入,请使用 find() 或 contains()。
std::set<T> — 有序唯一元素集合
std::set 存储唯一元素,同样基于红黑树。没有"值"部分,元素本身就是键。
#include <set>
#include <iostream>
int main() {
std::set<int> primes{2, 3, 5, 7, 11, 13};
primes.insert(17);
primes.insert(7); // 重复元素,插入无效
std::cout << "count(7) = " << primes.count(7) << "\n"; // 1
std::cout << "count(4) = " << primes.count(4) << "\n"; // 0
// 范围查找: [5, 13)
auto lo = primes.lower_bound(5);
auto hi = primes.lower_bound(13);
for (auto it = lo; it != hi; ++it) {
std::cout << *it << " "; // 5 7 11
}
}
自定义比较器
有序容器默认使用 std::less<Key>(即 operator<)。你可以通过模板参数或构造函数提供自定义比较逻辑:
#include <map>
#include <string>
// 方式一:函数对象
struct CaseInsensitiveLess {
bool operator()(const std::string& a, const std::string& b) const {
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(),
[](char c1, char c2) {
return std::tolower(c1) < std::tolower(c2);
});
}
};
// 大小写不敏感的 map
std::map<std::string, int, CaseInsensitiveLess> config;
config["Timeout"] = 30;
config["timeout"] = 60; // 视为相同 key,覆盖上面的值
// config.size() == 1
C++20 提示:有序容器支持透明比较器(heterogeneous lookup)。定义 using is_transparent = void; 后,find() 可以接受不同类型的参数,避免构造临时 key 对象。
2. 无序关联容器
当不需要有序遍历时,无序容器提供更快的平均性能。它们内部使用哈希表:元素通过哈希函数映射到桶(bucket),查找、插入平均 O(1),最坏 O(n)。
std::unordered_map 与 std::unordered_set
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <iostream>
int main() {
// unordered_map: 哈希表实现的键值对
std::unordered_map<std::string, double> prices{
{"apple", 3.5},
{"banana", 2.8},
{"cherry", 12.0}
};
prices["durian"] = 45.0;
// 查找:平均 O(1)
if (auto it = prices.find("banana"); it != prices.end()) {
std::cout << "banana: " << it->second << " yuan\n";
}
// unordered_set: 哈希表实现的唯一集合
std::unordered_set<std::string> visited{"home", "about"};
visited.insert("contact");
if (visited.contains("home")) { // C++20
std::cout << "Already visited home\n";
}
// 查看内部状态
std::cout << "bucket_count: " << prices.bucket_count() << "\n";
std::cout << "load_factor: " << prices.load_factor() << "\n";
}
自定义哈希函数
标准库为基本类型和 std::string 提供了 std::hash 特化。对于自定义类型,需要提供哈希函数:
#include <unordered_map>
#include <functional>
struct Point {
int x, y;
bool operator==(const Point&) const = default; // C++20
};
// 方式一:特化 std::hash
template<>
struct std::hash<Point> {
size_t operator()(const Point& p) const noexcept {
// 组合多个哈希值的常用技巧
size_t h1 = std::hash<int>{}(p.x);
size_t h2 = std::hash<int>{}(p.y);
return h1 ^ (h2 << 32) ^ (h2 >> 32);
}
};
// 现在可以直接使用
std::unordered_map<Point, std::string> labels;
labels[{0, 0}] = "origin";
labels[{1, 2}] = "point A";
注意:哈希函数的质量直接影响性能。糟糕的哈希函数会导致大量冲突,使查找退化为 O(n)。避免使用简单的异或(x ^ y),因为 {1,2} 和 {2,1} 会产生相同的哈希值。
有序 vs 无序:性能对比
// 性能特征对比
// std::map<K,V>:
// - 插入: O(log n)
// - 查找: O(log n)
// - 删除: O(log n)
// - 有序遍历: O(n),天然有序
// - 内存: 每个节点单独分配(指针开销大)
// std::unordered_map<K,V>:
// - 插入: O(1) 平均, O(n) 最坏
// - 查找: O(1) 平均, O(n) 最坏
// - 删除: O(1) 平均
// - 遍历: O(n),顺序不确定
// - 内存: 桶数组 + 链表节点
3. std::flat_map (C++23)
std::flat_map 是 C++23 引入的有序关联容器适配器。它将键和值分别存储在两个连续的 std::vector 中,保持有序排列。这带来了显著的缓存友好性。
#include <flat_map> // C++23
#include <string>
#include <iostream>
int main() {
// API 与 std::map 几乎相同
std::flat_map<std::string, int> scores;
scores.insert({"Alice", 95});
scores.emplace("Bob", 87);
scores["Carol"] = 92;
// 查找: O(log n) 二分搜索,但缓存命中率高
if (scores.contains("Alice")) {
std::cout << scores["Alice"] << "\n";
}
// 遍历: 连续内存,对 CPU 缓存非常友好
for (const auto& [name, score] : scores) {
std::cout << name << ": " << score << "\n";
}
// 可以自定义底层容器
// std::flat_map<int, std::string,
// std::less<int>,
// std::vector<int>,
// std::vector<std::string>> custom_map;
}
何时使用 flat_map:
- 元素数量较少(几百到几千),查找远多于插入/删除
- 需要有序遍历且追求缓存效率
- 一次性构建后主要做查询("build once, query many")
不适用场景:频繁插入/删除(因为底层 vector 需要移动元素,O(n) 代价)。
4. 实用操作
结构化绑定遍历
C++17 的结构化绑定让 map 遍历变得极其简洁:
std::map<std::string, std::vector<int>> student_scores{
{"Alice", {95, 87, 92}},
{"Bob", {78, 85, 90}}
};
// 结构化绑定 + const 引用:零拷贝遍历
for (const auto& [name, scores] : student_scores) {
int sum = 0;
for (int s : scores) sum += s;
std::cout << name << " avg: " << sum / scores.size() << "\n";
}
// 可修改值
for (auto& [name, scores] : student_scores) {
scores.push_back(100); // 给每人加一个满分
}
try_emplace — 避免冗余构造
try_emplace 只在键不存在时构造值。与 emplace 不同,如果键已存在,参数不会被移动走:
#include <map>
#include <string>
#include <vector>
std::map<std::string, std::vector<int>> data;
// emplace 的问题:即使 key 已存在,参数也可能被移动
std::vector<int> vals{1, 2, 3};
data.emplace("key", std::move(vals));
// 如果 "key" 已存在,vals 可能已被移动但插入失败!
// try_emplace:key 已存在时不会触碰参数
std::vector<int> safe_vals{4, 5, 6};
auto [it, inserted] = data.try_emplace("key", std::move(safe_vals));
if (!inserted) {
// safe_vals 保证未被移动,仍然有效
std::cout << "key exists, safe_vals still has "
<< safe_vals.size() << " elements\n";
}
insert_or_assign — 明确的"插入或更新"
std::map<std::string, int> config;
// insert_or_assign: 存在则赋值,不存在则插入
// 返回 {iterator, bool},bool 表示是否为新插入
auto [it1, was_new1] = config.insert_or_assign("timeout", 30);
// was_new1 == true (新插入)
auto [it2, was_new2] = config.insert_or_assign("timeout", 60);
// was_new2 == false (已存在,执行赋值)
// config["timeout"] == 60
// 对比 operator[]:
// config["timeout"] = 60; // 功能相同,但无法区分是插入还是更新
extract 和 merge (C++17)
extract 可以从容器中"摘出"一个节点而不销毁它,实现零拷贝的键修改或容器间移动:
#include <map>
#include <string>
#include <iostream>
int main() {
std::map<std::string, int> src{
{"alpha", 1}, {"beta", 2}, {"gamma", 3}
};
std::map<std::string, int> dst{
{"delta", 4}
};
// extract: 摘出节点,修改 key(唯一合法修改 key 的方式)
auto node = src.extract("beta");
if (!node.empty()) {
node.key() = "BETA"; // 修改 key!
dst.insert(std::move(node)); // 移入目标 map
}
// merge: 批量移动节点(零拷贝)
dst.merge(src); // src 中不冲突的节点全部移入 dst
// src 现在只保留与 dst 冲突的节点
std::cout << "dst: ";
for (const auto& [k, v] : dst) {
std::cout << k << "=" << v << " ";
}
// dst: BETA=2 alpha=1 delta=4 gamma=3
}
contains() vs find() != end()
std::map<std::string, int> m{{"x", 1}, {"y", 2}};
// C++20 之前:冗长的存在性检查
if (m.find("x") != m.end()) { /* ... */ }
if (m.count("x") > 0) { /* ... */ } // count 对 map 只能是 0 或 1
// C++20:简洁明了
if (m.contains("x")) { /* ... */ }
// 注意:如果需要使用找到的值,仍然用 find()
if (auto it = m.find("x"); it != m.end()) {
use(it->second); // 使用值
}
// contains() 只告诉你"存在与否",不返回值
5. 选择指南
下表对比三种主要的键值对容器,帮助你根据场景选择:
| 特性 | std::map | std::unordered_map | std::flat_map (C++23) |
|---|---|---|---|
| 底层结构 | 红黑树 | 哈希表 | 排序的 vector 对 |
| 查找复杂度 | O(log n) | O(1) 平均 | O(log n),缓存友好 |
| 插入复杂度 | O(log n) | O(1) 平均 | O(n)(需移动元素) |
| 有序遍历 | 天然有序 | 无序 | 天然有序 |
| 内存布局 | 散落的节点(指针跳转) | 桶数组 + 链表 | 连续内存 |
| 缓存友好性 | 差 | 中等 | 优秀 |
| 迭代器稳定性 | 插入/删除不失效 | rehash 时失效 | 插入/删除均失效 |
| 最佳场景 | 需要有序遍历、频繁增删 | 大量数据、快速查找 | 构建后主要查询、小规模 |
| Key 要求 | operator< 或自定义比较 | std::hash + operator== | operator< 或自定义比较 |
性能陷阱:std::map 的每个节点都是独立的堆分配,对 CPU 缓存极不友好。在百万级元素的纯查找场景中,std::unordered_map 可能比 std::map 快 5-10 倍。但如果你需要范围查询(range query)或有序输出,std::map 是唯一直接支持的选择。
本节小结
std::map/std::set:红黑树实现,O(log n) 操作,元素总是有序std::unordered_map/std::unordered_set:哈希表实现,O(1) 平均查找,需要提供哈希函数std::flat_map(C++23):底层使用排序 vector,缓存友好,适合"写少读多"场景- C++17 引入
try_emplace、insert_or_assign、extract、merge,大幅增强了 map 操作的精确性和效率 - C++20 的
contains()取代了繁琐的find() != end()模式 - 选择容器时,先明确你的核心需求:有序?高速查找?缓存友好?频繁增删?