Chapter 17: Map and Set
核心问题与阅读主线
全章共用代码样本(下文各节持续拆解)
贯穿全章的事件索引样本同时维护按用户名排序的得分映射与活跃用户集合,涵盖比较器、节点、查找与写入路径:
#include <map>
#include <set>
#include <string>
#include <string_view>
struct UserLess {
bool operator()(const std::string& left, const std::string& right) const {
return left < right;
}
};
using ScoreTable = std::map<std::string, int, UserLess>;
using ActiveUsers = std::set<std::string, UserLess>;
void record_score(ScoreTable& scores, ActiveUsers& active,
std::string user, int score) {
active.insert(user);
scores[user] = score;
}
这两行调用在底层展开为一条明确路径:user 经 UserLess 引导树搜索 → 缺失等价键时分配节点并构造元素(scores[user] 先值初始化再赋值)→ 旋转与变色维持树高约束 → 迭代器稳定指向节点且中序遍历保持比较器序。
17.1 key ordering、comparator 与 std::less
map / set 的有序性不是插入顺序,而是由二元比较器(comparator)维护的键空间顺序。std::map<Key, T> 与 std::set<Key> 默认使用 std::less<Key>,对 std::string 表现为字典序,对自定义类型则完全取决于比较器实现。
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> scores;
scores.emplace("bob", 70);
scores.emplace("alice", 90);
scores.emplace("carol", 80);
for (const auto& [name, score] : scores) {
std::cout << name << ' ' << score << '\n';
}
}
遍历时 begin() 指向比较器意义下的最小键,++iterator 走向中序后继节点;容器不记录插入先后,不能把 ordered associative container 当成插入日志。
comparator 同时决定键的唯一性:当 !comp(a, b) && !comp(b, a) 成立时,容器判定 a 与 b 等价。树搜索命中等价节点后,insert 不会创建重复元素。
#include <set>
#include <string>
struct UserKey {
int id;
std::string name;
};
struct CompareById {
bool operator()(const UserKey& left, const UserKey& right) const {
return left.id < right.id;
}
};
void demo() {
std::set<UserKey, CompareById> users;
auto first = users.insert({42, "alice"});
auto second = users.insert({42, "bob"});
// first.second == true, second.second == false
}
第二次插入失败是因为 CompareById 只比较 id,容器不检查 name 或对象二进制内容。设计自定义比较器时,必须把“排序字段”与“唯一性字段”一并确定。
比较器必须满足严格弱序(strict weak ordering):
- 非自反:
comp(x, x)必须为false(如下方BadLessEqual用<=会返回true,直接破坏等价判定)。 - 反对称:若
comp(a, b)为true,comp(b, a)必须为false。 - 传递性:若
comp(a, b)与comp(b, c)成立则comp(a, c)必成立,且“互不小于”的等价关系同样须传递。
struct BadLessEqual {
bool operator()(int left, int right) const {
return left <= right;
}
};
边界与误区
违背严格弱序通常能通过编译,却会让树有序前提失效,导致查找、插入定位和遍历语义全部失真。阅读源码时,应把 key_comp()、value_comp()、_Compare、__comp_ 视为容器核心不变量,而非普通可替换回调。
17.2 底层红黑树、节点结构与 iterator 实现
标准只约束有序性、唯一键与对数复杂度,具体结构由标准库实现决定;libstdc++、libc++ 与 MSVC STL 通常采用红黑树或等价自平衡二叉搜索树(颜色位、哨兵节点、父指针命名与旋转函数名均属实现细节)。
节点式有序容器的最小模型可分为三层:
- 容器对象:持有根节点(或哨兵头节点)、大小、
Compare与allocator。 - 树节点:保存父指针、左右子指针、颜色状态以及元素对象
Value。 - 迭代器:持有当前节点指针,按中序后继/前驱规则移动。
// 教学简化形状,不代表某个标准库源码。
template<class Value>
struct tree_node {
tree_node* parent;
tree_node* left;
tree_node* right;
bool red;
Value value;
};
template<class Node>
class tree_iterator {
Node* current_;
public:
// operator++ 会从 current_ 走到中序后继节点。
};
set 节点中的 Value 就是 Key,map 节点中的 Value 是 std::pair<const Key, T>。const Key 强制保护定位键不被原地篡改;mapped value 不参与树序,可以直接修改。
#include <map>
#include <string>
void update_value(std::map<std::string, int>& scores) {
auto it = scores.find("alice");
if (it != scores.end()) {
it->second = 100; // mapped value 可以修改
// it->first = "bob"; // key 是 const,普通路径不允许改
}
}
节点位置由键值决定,原地改键会破坏“左子树小于当前键、右子树大于当前键”的搜索前提;C++17 需先用 extract 将节点移出容器、修改键后再插回。
关键事实
插入新键只分配并挂接节点,树旋转仅重连父子指针而不搬移元素对象,因此插入不会使已有元素的 iterator 和 reference 失效;erase 仅使被删节点位置失效,clear 结束全部元素生命周期。
由于元素分散在独立节点中,map / set 提供双向迭代器(bidirectional iterator),++it / --it 沿树结构查找后继与前驱。它不像 vector 那样有连续地址可做指针算术,也不支持按位置下标在常数时间内跳转到第 100 个元素。
17.3 lower_bound、upper_bound、equal_range 与 find
有序查找接口复用同一条树搜索路径,由 comparator 统一决定搜索方向与边界位置:
| 接口 | 返回结果 | 比较器判断条件 | 典型用途 |
|---|---|---|---|
find(key) | 等价键节点或 end() | !comp(k, key) && !comp(key, k) | 精确存在性查询 |
lower_bound(key) | 首个不小于 key 的节点 | !comp(node->key, key) | 区间左界 [k, ...)、定位插入点 |
upper_bound(key) | 首个严格大于 key 的节点 | comp(key, node->key) | 区间右界 (..., k] |
equal_range(key) | [lower_bound(key), upper_bound(key)) | 组合上下界条件 | 唯一键最多含 1 个元素;统一 multi 容器语义 |
#include <iostream>
#include <map>
#include <string>
void query_scores() {
std::map<int, std::string> rank {
{60, "devon"},
{80, "alice"},
{90, "carol"}
};
auto first_pass = rank.lower_bound(80); // 指向 80
auto after_pass = rank.upper_bound(80); // 指向 90
auto exact = rank.find(75); // 返回 end()
if (first_pass != rank.end()) {
std::cout << first_pass->first << ' ' << first_pass->second << '\n';
}
if (after_pass != rank.end()) {
std::cout << after_pass->first << ' ' << after_pass->second << '\n';
}
if (exact == rank.end()) {
std::cout << "75 missing\n";
}
}
下方伪代码展示了 lower_bound 如何在树路径上收缩候选节点(upper_bound 对称,将判断条件换为 comp(key, current->key)):
// 教学伪代码:展示候选节点更新规则。
Node* lower_bound(Node* root, const Key& key, Compare comp) {
Node* answer = nullptr;
Node* current = root;
while (current != nullptr) {
if (!comp(current->key, key)) {
answer = current;
current = current->left;
} else {
current = current->right;
}
}
return answer;
}
当 comp(current->key, key) 为 true 时,当前节点及其左子树全小于 key,搜索只能进入右子树;否则当前节点已是合法候选,记下位置并向左收缩以寻找更靠前的候选。对唯一键容器,若 lower_bound(key) 到达 end() 或其键与 key 不等价,find(key) 即返回 end()。
范围查询是 ordered associative container 相对哈希容器的主要接口收益,例如用两个边界直接遍历 ["alice", "mike") 区间:
#include <iostream>
#include <map>
#include <string>
void print_name_range(const std::map<std::string, int>& scores) {
auto first = scores.lower_bound("alice");
auto last = scores.lower_bound("mike");
for (auto it = first; it != last; ++it) {
std::cout << it->first << ' ' << it->second << '\n';
}
}
如果需求常包含起点扫描、区间切片或前驱/后继查询,map / set 可直接支撑;如果只按完整键做等值查询,哈希容器通常具备更低的平均查询成本,但不提供全局有序性。
17.4 insert、erase、operator[] 与 at
修改与访问接口遵循“搜索定位 → 构造或访问节点 → 修复树结构 → 返回结果”的路径。各接口在缺失键与已存在键上的行为差异如下:
| 接口 | 适用容器 | 键不存在时 | 键已存在时 | 默认构造要求 |
|---|---|---|---|---|
insert | map / set | 分配节点并插入,返回 {new_it, true} | 保留旧值,返回 {old_it, false} | 无 |
operator[] | 仅 map | 插入新节点并值初始化 mapped value | 返回已有 mapped value 引用 | mapped type 须可默认构造 |
at | 仅 map | 抛出 std::out_of_range,不改容器 | 返回已有 mapped value 引用 | 无 |
find / contains | map / set | 返回 end() / false,不改容器 | 返回节点迭代器 / true | 无 |
insert 通过返回 pair 中的布尔标志区分“新建”与“复用”,其中 set 的迭代器指向 Key,map 的迭代器指向 pair<const Key, T>:
#include <map>
#include <string>
void insert_once(std::map<std::string, int>& scores) {
auto [it, inserted] = scores.insert({"alice", 90});
if (inserted) {
it->second += 1;
}
}
按迭代器 erase 时,容器析构被删节点元素并释放或回收节点内存,可能通过后继替换、旋转和变色修复黑高,但其它节点的迭代器与引用保持有效。遍历删除必须接住 erase(it) 返回的后继位置:
#include <map>
#include <string>
void remove_inactive(std::map<std::string, int>& scores) {
for (auto it = scores.begin(); it != scores.end(); ) {
if (it->second == 0) {
it = scores.erase(it);
} else {
++it;
}
}
}
operator[] 的缺失插默认语义适合“从零累加”的计数场景(对 int 值初始化为 0,对类类型调用默认构造):
#include <map>
#include <string>
void count_word(std::map<std::string, int>& counts, const std::string& word) {
++counts[word];
}
若 mapped type 不可默认构造、或缺失键不应修改容器状态,应改用 find、contains、at、try_emplace 或 insert_or_assign。其中 at 将缺失键视为错误路径:
#include <map>
#include <stdexcept>
#include <string>
int read_score(const std::map<std::string, int>& scores,
const std::string& user) {
return scores.at(user);
}
erase(it) 会立即结束旧 it 的生命周期,因此遍历删除必须接收其返回的后继位置,不可再对旧 it 执行 ++it。
边界与误区
插入过程可能发生 allocator 分配、key/value 构造、comparator 调用或链接后修复异常。标准库通常将“分配并构造节点”与“提交进树”分离:提交前失败会销毁对象并释放节点,提交后容器须维持有效状态;若自定义 comparator 抛异常,查找与插入路径都会成为可失败路径。
17.5 allocator、iterator 稳定性与 unordered 容器对比
map / set 属于 allocator-aware container。allocator 负责分配与释放独立节点的原始存储,容器在其上构造与销毁元素,节点内另含父指针、左右指针及颜色或等价状态字段。不同于 vector 扩容时整段搬移元素,节点式结构保证插入新键从不搬移已有元素对象。
#include <map>
#include <string>
void keep_iterator(std::map<std::string, int>& scores) {
auto alice = scores.find("alice");
scores.emplace("carol", 80);
scores.emplace("devon", 70);
if (alice != scores.end()) {
alice->second += 5;
}
}
把上面容器换成 std::unordered_map 时,必须重新审查保存的位置对象类型:unordered 容器插入可能触发 rehash 并重建桶数组,使既有 iterator 失效(尽管元素的 reference 与 pointer 通常仍指向原节点对象)。两类容器的核心对比如下:
| 评估维度 | std::map / std::set | std::unordered_map / std::unordered_set |
|---|---|---|
| 顺序与范围查询 | 维持全局比较器序,支持区间与前驱/后继扫描 | 无全局序,仅支持按键等值访问 |
| 查找时间复杂度 | 最坏 $O(\log n)$,依赖平衡树高与比较器成本 | 平均 $O(1)$,最坏退化与哈希质量相关 |
| 插入期位置稳定性 | iterator 与 reference 均保持有效 | 触发 rehash 时 iterator 失效,reference 通常保留 |
| 内存与局部性 | 每节点含父/子指针与颜色位,无桶数组 | 除节点开销外另维护桶数组,两者均有指针追踪 |
#include <map>
#include <string>
#include <unordered_map>
struct UserRecord {
int score;
bool active;
};
using OrderedUsers = std::map<std::string, UserRecord>;
using HashedUsers = std::unordered_map<std::string, UserRecord>;
需要按用户名区间导出报表且长期持有位置迭代器时,OrderedUsers 更稳妥;请求路径上仅按完整用户名做点查时,HashedUsers 往往更贴合。
关键事实
读性能代码时,map / set 的主要延迟来源常不是 $O(\log n)$ 的阶数本身,而是树节点的指针追踪、缓存不连续、重型比较器调用以及高频小节点分配开销。
17.6 Comparator Correctness, Key Stability, and Container Selection
在工程读码与代码审查中,按以下五步核查 map / set 用法:
- 键与比较器:确认定位键类型与排序/唯一性字段是否一致,核查严格弱序(避免
<=等破坏等价判定的写法)。 - 键稳定性:确认无原地改键意图;改键须拆分为“删旧插新”或分阶段审查 C++17
extract/insert。 - 访问语义:核对选用
find/contains、lower_bound/upper_bound/equal_range、operator[](缺失插默认)还是at(缺失抛异常)。 - 位置生命周期:追踪长期持有的
iterator与reference是否跨越insert、erase、clear、swap、extract、merge。 - 复杂度与分配:评估比较器体积、键构造/拷贝成本及高频节点分配对延迟分布的影响。
根据访问模式选择容器:
| 核心访问需求 | 优先容器 | 关键依据 |
|---|---|---|
| 全局有序遍历、范围查询、前驱/后继 | std::map / std::set | 持续维持比较器序,插入不使迭代器失效 |
| 纯完整键等值查询且哈希可控 | std::unordered_map / std::unordered_set | 平均常数查找成本,不维护树序 |
| 允许重复键 | multimap / multiset 或 unordered multi 容器 | 原生允许等价键共存 |
| 按优先级反复取极值 | std::priority_queue 或堆算法 | 仅维护局部堆序,节点分配开销更低 |
| 连续内存与按位置下标随机访问 | std::vector / std::array | 缓存友好且支持常数时间位置跳转 |
下面片段把比较器、键值语义与选型判断集中在一处,可用于实践上述审查顺序:
#include <map>
#include <string>
struct CaseInsensitiveLess {
bool operator()(const std::string& left,
const std::string& right) const;
};
std::map<std::string, int, CaseInsensitiveLess> visits;
void touch(const std::string& name) {
++visits[name];
}
按检查顺序拆解 visits:
- 比较器与唯一键:先确认
CaseInsensitiveLess满足严格弱序;若忽略大小写等价,"Alice"与"alice"会命中同一唯一键,最终保留首次插入的原始拼写。 - 写入路径:
++visits[name]依赖operator[]在缺失键时插入节点并将计数初始化为0。 - 容器取舍:若后续需按忽略大小写的字典序导出用户,保留
std::map;若仅在请求路径上累计计数且不需排序,改用具备一致 hash 与 equality 的哈希容器更合适。
核心判断
当自定义比较器把多个原始输入判为等价时,容器只保留首次插入的键副本,后续等价 insert 或 operator[] 均复用该节点而不会替换键本身。
最小自检任务
阅读下方代码,先独立推导再对照答案要点,回答四个问题:
- 最终遍历顺序由什么决定?
- 第二次插入
{"Bob", 100}是否成功? scores["Bob"]会不会改变容器结构?- 将
scores改为std::unordered_map<std::string, int>后,saved迭代器在后续插入后还能按同样规则使用吗?
#include <iostream>
#include <map>
#include <string>
struct LengthThenLexicographical {
bool operator()(const std::string& left,
const std::string& right) const {
if (left.size() != right.size()) {
return left.size() < right.size();
}
return left < right;
}
};
int main() {
std::map<std::string, int, LengthThenLexicographical> scores;
scores.insert({"Amy", 90});
scores.insert({"Bob", 80});
scores.insert({"Chris", 70});
auto saved = scores.find("Amy");
auto result = scores.insert({"Bob", 100});
int value = scores["Bob"];
scores.insert({"Dan", 60});
for (const auto& [name, score] : scores) {
std::cout << name << ' ' << score << '\n';
}
}
本章知识点总结
- 排序与等价
map/set由同一套 comparator 同时定义键序与唯一性(!comp(a, b) && !comp(b, a)即等价),且 comparator 必须满足严格弱序。 - 节点式树结构
常见实现用自平衡树节点保存元素、父子链接与颜色状态,标准层仅承诺排序、唯一性与对数复杂度。
- 键不可变性
set元素与map的const Key在树内不可原地修改,改键须删旧插新或用 C++17extract移出后再插回。 - 有序查找边界
lower_bound、upper_bound与equal_range复用树搜索路径定位范围边界,是相对哈希容器的核心收益。 - 读写接口差异
insert遇等价键不覆盖,operator[]缺失键时插默认值(map专属),at缺失键时抛std::out_of_range且不修改容器。 - 位置稳定与开销
普通
insert保持已有元素的 iterator 和 reference 有效,erase仅失效被删节点;代价是每节点额外指针、分配调用与指针追踪局部性损失。 - 容器选型
需要全局有序、范围查询或插入期位置稳定时选
map/set;纯等值点查且哈希可控时评估unordered_map/unordered_set。