Chapter 18: Multimap and Multiset
std::multimap 和 std::multiset 解决的是有序关联容器里的重复键问题。std::map 和 std::set 把 key 当成唯一身份，插入等价 key 时会合并到已有位置或拒绝新元素；multi 容器把等价 key 当成一组节点，每个节点仍然是独立元素。
本章的主线材料是一段倒排索引：一个单词可以出现在多个文档位置，所以键相同并不代表元素相同。读完本章后，读者应能判断一个重复键需求适合 multimap、multiset、map<Key, vector<T>> 还是后续的 unordered multi 容器，并能沿着 equal_range、插入返回值、迭代顺序和删除语义解释这类判断。
multi 容器仍属于 ordered associative containers。它们保留红黑树这类有序节点结构带来的按 key 排序、双向迭代、对数级定位和稳定节点引用；变化集中在唯一性约束上：容器允许多个 key 在比较器意义下等价，并让调用者通过范围接口处理这一组元素。
下面的代码贯穿本章。postings 记录单词出现的位置，latencies 记录可重复的延迟值。两者的共同点是：一个排序位置上可以聚集多个等价 key。
#include <map>
#include <set>
#include <string>
#include <iostream>
int main() {
std::multimap<std::string, int> postings;
postings.emplace("cache", 3);
postings.emplace("api", 1);
postings.emplace("cache", 8);
postings.emplace("cache", 13);
auto [first, last] = postings.equal_range("cache");
for (auto it = first; it != last; ++it) {
std::cout << it->first << " -> " << it->second << '\n';
}
std::multiset<int> latencies{12, 7, 12, 20, 7};
std::cout << "latency 12 count = " << latencies.count(12) << '\n';
}
postings 的 key 是单词，mapped value 是位置；latencies 的 value 自身就是 key。理解这一区别后，multimap 和 multiset 的接口差异会变得稳定：前者用于一键多值，后者用于可重复的有序元素集合。
18.1 duplicate key 与 equivalent keys
duplicate key 在 multi 容器中指多个元素的 key 在比较器意义下等价。这里的“等价”由 Compare 决定，常见默认比较器是 std::less<Key>。对两个 key a 和 b，当 !comp(a, b) && !comp(b, a) 成立时，标准关联容器把它们放入同一个等价类。
这个定义把 multi 容器的重复语义绑定到排序规则上。operator== 可以参与业务判断，但 ordered associative container 的 key 等价性来自比较器。只要比较器认为两个 key 互不小于对方，它们在 multimap 或 multiset 中就属于同一个重复键组。
用贯穿材料观察这一点，"cache" 的三个位置会被组织成一个等价组。树仍然按字符串顺序排列，所以 "api" 先于 "cache"；进入 "cache" 这一组之后，三个节点都保留自己的 mapped value。
std::multimap<std::string, int> postings;
postings.emplace("cache", 3);
postings.emplace("api", 1);
postings.emplace("cache", 8);
postings.emplace("cache", 13);
这段代码产生四个节点。"cache" 没有覆盖已有值，也没有把三个位置压缩成一个 vector<int>；容器中真实存在三个 key 等价的节点。size() 返回 4，count("cache") 返回 3，遍历容器时仍按 key 的非降序输出。
multimap 的元素类型是 std::pair<const Key, T>，key 部分保持只读，mapped value 可以按节点修改。multiset 的元素类型就是 Key，迭代器通常表现为指向 const value 的迭代器，因为修改元素值会改变树的排序位置。这个约束来自有序树的不变量：节点一旦在树中定位，key 的比较结果必须保持稳定。
C++11 起，标准明确等价 key 的元素顺序保持插入顺序。对 postings 来说，遍历 equal_range("cache") 时会按 3, 8, 13 这个插入顺序看到 mapped value。这个保证服务的是等价组内部的稳定遍历，不改变外层的 key 排序规则。
multiset 也遵循相同的等价规则。std::multiset<int>{12, 7, 12, 20, 7} 的完整有序序列是 7, 7, 12, 12, 20。其中两个 7 属于一个等价组，两个 12 属于另一个等价组。每个重复值都是独立元素，所以删除一个迭代器位置和按 key 删除全部等价元素会产生不同结果。
本节的判断顺序是：先确定 key 的比较器，再用比较器定义等价关系，然后判断业务中的“重复”是否对应这个等价关系。业务相等与排序等价不一致时，multi 容器会按照排序等价组织节点，业务层需要额外字段或外层结构补足规则。
18.2 equal_range 与重复键分组路径
equal_range(key) 是读取重复键组的核心入口。它返回一个半开区间 [first, last)，其中 first 等价于 lower_bound(key)，last 等价于 upper_bound(key)。这个区间覆盖所有 key 与参数等价的节点。
对 postings.equal_range("cache")，定位过程可以拆成两个边界。左边界寻找第一个不小于 "cache" 的位置，右边界寻找第一个大于 "cache" 的位置。两者之间的节点就是 "cache" 的完整分组。
auto [first, last] = postings.equal_range("cache");
for (auto it = first; it != last; ++it) {
// it->first 一定与 "cache" 在 Compare 意义下等价
// it->second 是这个 key 对应的一个独立 mapped value
}
这个区间接口比 find 更适合 multi 容器。find(key) 只能给出一个等价元素的位置，调用者仍然缺少分组边界；count(key) 能给出数量，但不能直接给出每个节点。equal_range 同时给出起点和终点，可以安全地遍历、复制、统计或按条件删除分组中的元素。
有序树中的重复键分组不是额外数组。常见实现形状是在同一棵红黑树中保存所有节点，等价 key 在中序遍历结果里形成连续区间。这个连续性来自比较器：比 key 小的节点一定在左侧，比 key 大的节点一定在右侧，互相等价的节点不会被其他 key 夹断。
equal_range 的定位成本来自树高，通常按 O(log N) 理解；遍历返回区间还要访问 K 个等价节点，所以完整消费分组的成本是定位成本加上分组长度。这个拆分比单独背复杂度更有工程意义：当某个 key 对应十万个值时，树定位很快，真正的成本集中在分组遍历与后续处理。
multiset 的 equal_range 处理的是重复元素值。下面的代码统计所有延迟等于 12 的样本，并展示了区间长度与 count 的关系。
std::multiset<int> latencies{12, 7, 12, 20, 7};
auto [begin12, end12] = latencies.equal_range(12);
int total = 0;
for (auto it = begin12; it != end12; ++it) {
++total;
}
std::cout << total << '\n'; // 2
std::cout << latencies.count(12); // 2
范围接口还决定删除写法。需要删除一组 key 时，可以直接调用 erase(key)；需要只删除组内某些节点时，应先拿到 equal_range，再按迭代器逐个处理。后一种写法能保留同 key 下其他业务值，例如只移除 "cache" -> 8，保留 "cache" -> 3 和 "cache" -> 13。
auto [first, last] = postings.equal_range("cache");
for (auto it = first; it != last; ) {
if (it->second == 8) {
it = postings.erase(it);
} else {
++it;
}
}
这段代码利用了节点式有序容器的局部删除语义。erase(iterator) 删除当前节点并返回下一个位置，循环可以继续留在同一个等价组附近。被删除节点的迭代器失效，其他节点的迭代器和引用保持可用，这一点来自有序关联容器的节点式存储形状。
18.3 插入策略与查找策略
multi 容器的插入策略可以概括为：定位排序位置，构造新节点，链接到树中，必要时执行红黑树修复，然后返回新节点迭代器。插入等价 key 时，容器不会执行唯一性检查来阻止新节点进入容器。
auto it1 = postings.emplace("cache", 21);
auto it2 = postings.emplace("cache", 34);
it1 和 it2 都指向新插入的节点。与 std::map::emplace 常见返回值 std::pair<iterator, bool> 相比，std::multimap::emplace 返回 iterator，因为重复 key 进入容器是成功路径的一部分，接口不需要用 bool 表示“已经存在”。
插入路径可以用下图整理。图中的“等价区间附近”是实现策略层面的描述；标准语义要求最终遍历顺序满足比较器，并在 C++11 起保持等价元素的插入顺序。
这条路径说明了两个工程结论。第一，multi 容器的每个元素都有独立节点，mapped value 不参与 multimap 的 key 排序。第二，等价 key 分组是排序结果中的连续区间，插入新节点后仍要维护整棵树的平衡条件。
查找策略要按目标区分。需要判断是否存在某个 key 时，contains(key) 在 C++20 起表达最清楚；需要拿到一个元素时用 find(key)；需要处理完整分组时用 equal_range(key)；需要做区间切分或自定义边界时用 lower_bound(key) 与 upper_bound(key)。
if (postings.contains("cache")) { // C++20
auto one = postings.find("cache"); // 一个等价元素
auto group = postings.equal_range("cache");
}
find 的结果适合“存在即可”的路径，例如检查倒排索引里某个词是否出现过。它不适合表达“一键多值”的完整读取，因为它没有给出右边界。multi 容器中遇到完整业务记录读取、批量删除、批量导出和分组聚合时，应优先使用 equal_range。
emplace_hint 可以把调用者已知的位置作为插入提示。提示正确时，常见实现可以减少比较次数；提示错误时，容器仍然要回到普通定位路径以维持有序树不变量。对重复 key 的批量插入，常见写法是把上一次插入返回的 iterator 作为下一次 hint，让等价组连续追加。
auto hint = postings.end();
for (int pos : {55, 89, 144}) {
hint = postings.emplace_hint(hint, "cache", pos);
}
这段代码的业务含义是连续追加同一个 key 的多个位置。它不改变复杂度承诺的语义边界：容器仍然负责维护全局有序；hint 只是给实现一个更接近目标位置的起点。
异常安全也沿着节点插入路径理解。插入需要分配节点、构造 value_type、链接节点和修复树结构。常见实现会先完成节点构造，之后再提交到树结构；如果分配或构造失败，原容器保持原有节点集合。插入成功后，新节点独立拥有自己的元素存储，后续删除该节点时由容器通过 allocator 销毁和释放。
18.4 与 map / set 的区别
multimap 与 map 的根本差异是 key 是否唯一。map<Key, T> 把 key 映射到一个 mapped value，接口围绕单点访问设计；multimap<Key, T> 把 key 映射到一组节点，接口围绕范围访问设计。这个差异会传导到插入返回值、访问接口、删除语义和业务建模。
| 维度 | map / set | multimap / multiset |
|---|---|---|
| key 约束 | 每个等价 key 最多一个元素 | 每个等价 key 可以对应多个元素 |
| 插入结果 | 通常需要表达是否插入成功 | 返回新节点位置，重复 key 是正常插入 |
| 查找重点 | 单个元素位置 | 等价 key 的半开区间 |
| 删除 key | 删除 0 或 1 个元素 | 删除该 key 的整个等价组 |
| 典型读取 | find、at、operator[] 等单点语义 | equal_range 后遍历分组 |
| 复杂度基础 | 有序树定位，通常对数级 | 有序树定位加分组长度 |
multimap 没有 operator[] 和 at 这种按 key 取单个 mapped value 的接口。原因很直接：一个 key 可能对应多个 mapped value，容器层无法替业务决定应该返回哪一个。调用者需要先用 equal_range 拿到组，再根据业务规则选择全部、第一个、最后一个或满足谓词的某个节点。
下面的例子展示同一个输入在 map 与 multimap 中的不同语义。
std::map<std::string, int> unique_posting;
unique_posting.emplace("cache", 3);
unique_posting.emplace("cache", 8); // key 已存在，插入不会新增第二个节点
std::multimap<std::string, int> multi_posting;
multi_posting.emplace("cache", 3);
multi_posting.emplace("cache", 8); // 新增第二个等价 key 节点
unique_posting 更适合“每个单词保存一个计数”这种唯一映射；multi_posting 更适合“每个单词保存多个出现位置”。当业务说“一个 key 对应多个 value”时，仍要进一步判断多值是容器节点还是 value 内部结构。如果经常按 key 批量替换、排序 value、去重 value 或整体序列化，map<Key, vector<T>> 可能更直接。
set 与 multiset 的差异也来自唯一性。set<Key> 表达有序去重集合，重复插入同一个等价 key 后容器大小不变；multiset<Key> 表达有序多重集合，重复值会增加元素数量。multiset 常用于频率统计、可重复排序样本、滑动窗口中的有序计数等场景。
std::set<int> unique_values{7, 7, 12}; // 结果包含 7 和 12
std::multiset<int> counted_values{7, 7, 12}; // 结果包含两个 7 和一个 12
两类容器的实现形状高度相似。常见实现都使用节点式平衡树，allocator 负责节点存储，iterator 通常是双向迭代器。插入新节点一般不会让已有元素的 iterator 和 reference 失效；删除某个节点会让指向该节点的 iterator 和 reference 失效。选型时不要把 multi 与 unique 的差异误判为内存布局差异，真正的差异在唯一性约束和接口语义。
与后续 unordered multi 容器相比，ordered multi 容器提供按 key 有序遍历、lower_bound、upper_bound 和范围切分。unordered multi 容器以哈希桶定位为主，适合平均常数级查找，但不提供全局 key 顺序。需要按字典序导出索引、按数值范围截取重复元素或稳定进行有序遍历时，ordered multi 容器更贴合问题结构。
本节的选型顺序是：先看 key 是否唯一，再看是否需要按 key 有序遍历，再看组内值是否需要单独排序或整体替换，最后看节点分配和分组长度是否符合性能预算。唯一 key 选择 map / set；重复 key 且需要有序范围选择 multimap / multiset；重复 key 但主要需求是哈希查找时进入后续 unordered multi 容器；重复 key 且强依赖组内批处理时考虑 map<Key, vector<T>>。
18.5 工程使用场景
multimap 最适合表达“键有序、键可重复、每条记录独立存在”的关系。倒排索引是典型例子：词项作为 key，文档位置或文档 id 作为 mapped value；同一个词项有多个位置，遍历时还希望按词项顺序导出或做范围扫描。
std::multimap<std::string, int> inverted_index;
inverted_index.emplace("allocator", 10);
inverted_index.emplace("allocator", 42);
inverted_index.emplace("iterator", 5);
for (auto [it, end] = inverted_index.equal_range("allocator"); it != end; ++it) {
std::cout << "position = " << it->second << '\n';
}
这个结构的优势是插入简单、节点独立、按 key 遍历稳定。它的成本也很明确：每个位置都需要一个树节点，内存分配次数和指针跳转较多；同一个 key 的大量 value 需要线性遍历。数据量很大且 value 经常批量处理时，可以把 key 映射到连续数组，把分组内部的数据放进 vector。
multimap 也适合构造二级索引。例如订单系统中，一个用户 id 对应多个订单 id；日志系统中，一个模块名对应多条事件 id；编译器或静态分析工具中，一个符号名对应多个源码位置。共同条件是：记录需要独立插入和删除，同时调用者需要按 key 有序查看。
multiset 的典型场景是可重复排序样本。它保留每个样本的数量，又能随时取最小值、最大值、lower_bound 位置或某个值的出现次数。滑动窗口中维护延迟样本、多任务调度中维护可重复优先级、库存系统中维护可重复价格档位，都可以用 multiset 表达。
std::multiset<int> window;
window.insert(20);
window.insert(12);
window.insert(20);
int min_latency = *window.begin();
auto count20 = window.count(20);
需要注意的是，multiset 只保存 key 本身。若业务记录除了排序 key 之外还有 id、时间戳或状态字段，可以把复合结构作为 key，并设计严格弱序比较器；也可以使用 multimap<Key, RecordId>，让 key 负责排序，mapped value 保存记录身份。比较器一旦忽略某些字段，这些字段就不会参与树中的定位和分组边界。
工程上常见的分歧是 multimap<Key, T> 与 map<Key, vector<T>>。前者让每个 value 作为独立节点进入树，单条插入和单条删除自然；后者让同 key 的 value 连续存储，批量遍历和组内压缩更友好。判断时可以沿着四个问题走：是否经常单条删除，是否需要组内连续内存，是否需要按 key 范围遍历，是否需要控制组内排序。
| 需求形状 | 更常见选择 | 主要依据 |
|---|---|---|
| 一条记录一条记录增删，按 key 有序遍历 | multimap<Key, T> | 节点独立，范围接口直接覆盖重复 key |
| 同 key 下 value 经常批量读取或压缩 | map<Key, vector<T>> | 组内连续存储，批量处理成本更可控 |
| 只关心重复元素计数和有序位置 | multiset<Key> | value 本身就是 key，接口直接表达计数和顺序 |
| 平均查找优先，全局顺序需求很弱 | unordered multi 容器 | 哈希定位优先，后续章节展开桶内分组 |
这组判断还要结合异常安全和迭代器稳定性。multimap 与 multiset 插入新节点时，一般不会移动已有元素；删除一个节点时，其他节点保持原位置语义。map<Key, vector<T>> 中的 vector 扩容可能移动组内元素，使指向 value 的指针、引用和迭代器失效。若外部长期持有组内 value 的位置对象，节点式 multi 容器更容易维持稳定边界。
最终的工程结论可以压缩成一个顺序：先确认重复 key 是真实数据模型，再确认是否需要按 key 有序范围访问，然后估算最大分组长度，最后比较节点式独立性与连续数组批处理成本。multimap 和 multiset 的价值不在 API 数量，而在它们把“重复键组”建模成有序树中的连续区间。
最小自检任务
阅读下面代码，判断每个问题的结果和原因。
#include <map>
#include <string>
std::multimap<std::string, int> index;
index.emplace("log", 10);
index.emplace("api", 4);
index.emplace("log", 2);
index.emplace("log", 7);
auto one = index.find("log");
auto group = index.equal_range("log");
auto removed = index.erase("log");
问题：
index在调用erase("log")之前有多少个节点？"log"对应多少个节点？group表达的区间覆盖哪些元素？这些元素在默认比较器下为什么连续？removed的值是多少？调用后容器还剩哪些 key？- 如果业务要求同一个 key 下的 mapped value 按数值升序输出，当前
std::multimap<std::string, int>是否自动提供这个组内数值顺序？应如何调整数据结构？
答案要点
index 在删除前有 4 个节点，其中 "log" 对应 3 个节点。std::multimap 允许多个 key 在 Compare 意义下等价，每次 emplace 都会新增独立节点；"api" 和三个 "log" 节点共同构成容器的元素集合。
group 是 equal_range("log") 返回的半开区间，覆盖三个 key 与 "log" 等价的节点。默认 std::less<std::string> 下，"api" 小于 "log"，所有 "log" 节点互相等价，所以中序遍历结果中 "log" 这一组形成连续区间。C++11 起，等价 key 的组内顺序保持插入顺序，因此 mapped value 的遍历顺序对应 10, 2, 7。
removed 的值是 3，因为 erase(key) 删除所有与参数 key 等价的元素。调用之后容器中还剩 "api" -> 4 这一条记录。被删除节点对应的 iterator 和 reference 失效，其他节点保持可用。
当前 std::multimap<std::string, int> 不自动按 mapped value 排序，因为 multimap 的比较器只比较 key。若组内 value 需要数值升序，可以使用 map<std::string, std::vector<int>> 并在组内排序，也可以把排序维度编码进复合 key，例如用 std::set<std::pair<std::string, int>> 表达 (word, position) 的整体顺序。选择哪一种取决于是否需要独立节点、组内连续存储和按 key 范围遍历。
本章知识点总结
- 重复键：multi 容器允许多个元素的 key 在比较器意义下等价。
- 等价关系：ordered associative container 使用
!comp(a, b) && !comp(b, a)判断 key 等价。 - 独立节点：
multimap中同 key 的多个 mapped value 是多个节点。 - 组内顺序：C++11 起等价 key 的元素保持插入顺序。
- 范围读取：
equal_range返回覆盖等价 key 组的半开区间。 - 边界定位：
lower_bound给出左边界，upper_bound给出右边界。 - 插入返回：multi 容器插入重复 key 后返回新节点 iterator。
- 查找选择：完整分组读取优先使用
equal_range。 - 删除语义：
erase(key)删除整个等价 key 组。 - 接口差异：
multimap围绕范围访问设计，map围绕单点访问设计。 - 节点稳定：有序节点容器插入通常保持已有元素位置对象可用。
- 选型顺序：先看重复 key，再看有序范围，再看分组长度和内存形状。
- 组内排序：mapped value 不参与
multimap的 key 比较和分组边界。 - 工程场景：倒排索引、二级索引和可重复排序样本适合用 multi 容器表达。