Skip to main content

Chapter 18: Multimap and Multiset

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

std::multimap 与 std::multiset 保留了有序关联容器的红黑树节点结构(按 key 排序、双向迭代、对数级定位与稳定节点引用),但放开了唯一性约束,让比较器等价的多个 key 作为独立节点共存并通过范围接口成组访问。工程选型的核心在于界定节点式有序多值存储与 map<Key, vector<T>>、unordered multi 容器之间的语义与内存边界。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

下面的倒排索引 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 的元素值本身就是 key,适合可重复的有序集合。

18.1 duplicate key 与 equivalent keys​

ordered associative container 的重复键并不由 operator== 决定,而是由比较器 Compare(默认 std::less<Key>)定义的等价关系判定:当 !comp(a, b) && !comp(b, a) 成立时,a 与 b 落入同一等价组。

std::multimap<std::string, int> postings;
postings.emplace("cache", 3);
postings.emplace("api", 1);
postings.emplace("cache", 8);
postings.emplace("cache", 13);

上例在容器中生成 4 个真实独立节点,既不会覆盖已有值,也不会压缩成 vector<int>。围绕等价组,有三条核心不变量:

  • 有序与统计:外层按 key 非降序排列("api" 先于 "cache"),size() 为 4,count("cache") 为 3。
  • 组内插入序(C++11 起):等价 key 组内部稳定保持插入顺序,遍历 postings.equal_range("cache") 将按 3, 8, 13 输出。
  • 节点 key 只读约束:multimap 元素类型为 std::pair<const Key, T>,允许修改 mapped value;multiset 元素即 Key,迭代器具有 const 语义,防止原地改键破坏红黑树排序不变量。

multiset 遵循完全一致的等价规则。例如 std::multiset<int>{12, 7, 12, 20, 7} 的完整有序序列为 7, 7, 12, 12, 20,其中两个 7 与两个 12 各自独立——按单个迭代器删除只移除一个节点,按 key 删除则会移除整个等价组。

边界与误区

注意

当业务“相等”与排序等价不一致时,multi 容器仍严格按 Compare 组织节点。若比较器忽略了某些判重字段,容器就会把不同业务记录合并到同一等价组中,必须由比较器本身或外层结构补足规则。

18.2 equal_range 与重复键分组路径​

equal_range(key) 是访问重复键组的核心入口,返回半开区间 [first, last),其中 first 等价于 lower_bound(key)(首个不小于 key 的节点),last 等价于 upper_bound(key)(首个大于 key 的节点)。find(key) 仅返回一个匹配位置、count(key) 只给出数量,只有 equal_range(key) 同时提供完整分组的起止边界。

auto [first, last] = postings.equal_range("cache");

for (auto it = first; it != last; ++it) {
// it->first 与 "cache" 在 Compare 意义下等价
// it->second 是该 key 对应的独立 mapped value
}

等价组能直接以单区间表达,源于红黑树的存储形状与比较器性质:

  • 中序连续性:所有节点存于同一棵平衡树中,小于 key 的节点在左、大于 key 的在右,互相等价的节点在中序序列中天然连续,不会被其他 key 夹断。
  • 两段式成本:定位 [first, last) 边界取决于树高,复杂度为 O(log N);完整消费分组还需遍历 K 个等价节点,总成本为定位成本加分组长度。当单个 key 聚集十万个值时,瓶颈在分组遍历而非树定位。

multiset 同样通过 equal_range 统计或遍历特定值样本,区间长度与 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

当只需要删除等价组内满足特定条件的节点(如只删 "cache" -> 8 而保留 3 和 13)时,应沿 equal_range 区间迭代,并用 erase(iterator) 的返回值推进迭代器:

auto [first, last] = postings.equal_range("cache");
for (auto it = first; it != last; ) {
if (it->second == 8) {
it = postings.erase(it);
} else {
++it;
}
}

核心判断

删除整组等价 key 直接用 erase(key);按条件过滤组内节点必须用 equal_range 配合 it = container.erase(it)。由于节点式有序容器独立分配每个节点,被删节点的迭代器与引用失效,其余节点保持有效。

18.3 插入策略与查找策略​

向 multi 容器插入等价 key 时,容器不执行阻断重复的唯一性检查,因此 emplace 与 insert 直接返回指向新节点的 iterator(而非 std::map 的 std::pair<iterator, bool>):

auto it1 = postings.emplace("cache", 21);
auto it2 = postings.emplace("cache", 34);

下图展示节点插入路径。标准只要求最终遍历顺序符合 Compare 并在等价组内保持插入顺序(C++11 起),图中的“等价区间附近”属常见实现策略;multimap 的 mapped value 始终不参与 key 排序。

针对不同读取目标,multi 容器的查找接口分工明确:

接口返回结果适用场景边界局限
contains(key) (C++20)bool仅判断 key 是否存在不返回节点位置与数量
find(key)iterator只需取一个匹配样本无右边界,无法遍历完整分组
equal_range(key)pair<iterator, iterator>完整分组读取、统计与条件删除需同时付出 O(log N) 定位与 O(K) 组遍历
lower_bound / upper_bounditerator区间切分或自定义范围起止点单次仅给出单侧边界
if (postings.contains("cache")) { // C++20
auto one = postings.find("cache"); // 一个等价元素
auto group = postings.equal_range("cache");
}

批量追加同 key 节点时,可用 emplace_hint 把上一次返回的迭代器作为提示传入。提示命中时可减少比较次数;即使提示错误,容器仍会退回常规树定位以维护全局有序不变量:

auto hint = postings.end();
for (int pos : {55, 89, 144}) {
hint = postings.emplace_hint(hint, "cache", pos);
}

关键事实

节点分配与异常安全:插入时实现通常先分配节点并构造 value_type,成功后再将其链接入树并修复平衡。若分配或构造失败,原容器节点集合保持不变;链接后的节点生命周期由容器通过 allocator 统一销毁与释放。

18.4 与 map / set 的区别​

multimap / multiset 与 map / set 的唯一本质分歧在于 key 是否唯一,由此传导至全部接口设计:

维度map / setmultimap / multiset
key 约束每个等价 key 最多一个元素每个等价 key 可以对应多个元素
插入结果通常需 pair<iterator, bool> 表达是否插入成功直接返回新节点 iterator,重复 key 属正常路径
查找重点单个元素位置等价 key 的半开区间
删除 key删除 0 或 1 个元素删除该 key 的整个等价组
典型读取find、at、operator[] 等单点语义equal_range 后遍历分组
复杂度基础有序树定位,通常对数级有序树定位加分组长度

正因为一个 key 可能对应多个节点,容器无法替业务决定返回哪一个,所以 multimap 不提供 operator[] 和 at。对比同输入下的行为差异:

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 节点

同理,std::set<int> 表达有序去重集合,而 std::multiset<int> 表达可重复的多重集合(适合频率统计、有序样本与滑动窗口):

std::set<int> unique_values{7, 7, 12}; // 包含 7, 12
std::multiset<int> counted_values{7, 7, 12}; // 包含 7, 7, 12

边界与误区

注意

不要把 multi 与 unique 容器的差异误判为内存布局差异。二者底层同样采用节点式平衡树、allocator 分配节点与双向迭代器:插入新节点均不会使已有元素的迭代器和引用失效,删除仅使被删节点自身失效。

相比后续的 unordered multi 容器(基于哈希桶平均常数级查找、无全局 key 序),ordered multi 容器的价值在于提供按 key 有序遍历、lower_bound/upper_bound 与范围切分。选型可按以下判断链收敛:

  1. key 唯一:选 map / set。
  2. key 重复且需按 key 有序遍历或范围切分:选 multimap / multiset。
  3. key 重复且需组内整体排序、去重、批处理或序列化:考虑 map<Key, vector<T>>。
  4. key 重复且仅重哈希查找、无需全局序:进入后续 unordered multi 容器。

18.5 工程使用场景​

multimap 适合“键有序、键可重复、记录独立增删”的模型,典型应用包括倒排索引(词项到文档位置)与二级索引(用户 id 到订单 id、模块名到事件 id、符号名到源码位置):

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 仍需线性遍历。

multiset 适合维护可重复的有序样本(如滑动窗口延迟、多任务可重复优先级、商品价格档位),可随时读取极值、lower_bound 位置或特定值的出现次数:

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 本身。若业务记录还带有 id、时间戳或状态字段,可封装复合结构并编写严格弱序比较器,或改用 multimap<Key, RecordId> 分离排序键与记录身份。注意:比较器忽略的字段不参与树定位与等价组边界。

工程上最常在 multimap<Key, T> 与 map<Key, vector<T>> 之间权衡,可按是否频繁单条删改、是否需要组内连续内存、是否按 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 扩容时会使组内元素的指针、引用与迭代器全部失效。若外部长期持有元素位置对象,应优先选节点式 multi 容器。

最小自检任务​

动手自检先独立判断

阅读下面代码,判断每个问题的结果和原因。

#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");

问题:

  1. index 在调用 erase("log") 之前有多少个节点?"log" 对应多少个节点?
  2. group 表达的区间覆盖哪些元素?这些元素在默认比较器下为什么连续?
  3. removed 的值是多少?调用后容器还剩哪些 key?
  4. 如果业务要求同一个 key 下的 mapped value 按数值升序输出,当前 std::multimap<std::string, int> 是否自动提供这个组内数值顺序?应如何调整数据结构?

本章知识点总结​

  • 等价判重

    ordered multi 容器以比较器的 !comp(a, b) && !comp(b, a) 判定 key 等价,允许同键多节点共存且节点 key 只读。

  • 组内保序

    C++11 起等价 key 组内部保持插入顺序,multimap 的 mapped value 不参与 key 比较与分组边界。

  • 范围访问

    equal_range(key) 返回 [lower_bound, upper_bound) 连续半开区间,是读取、统计和条件删改重复键组的首选入口。

  • 插入与查找

    emplace 直接返回新节点迭代器;判存在用 contains,取单节点用 find,读完整分组用 equal_range。

  • 删除语义

    erase(key) 移除整组等价节点并返回数量;局部过滤应按 it = container.erase(it) 推进,未删节点的迭代器与引用稳定。

  • 接口与布局

    multi 与 unique 容器同为节点式平衡树,仅因唯一性约束差异使 multimap 省去 operator[] 与 at 并围绕范围访问设计。

  • 工程选型

    独立增删且需按 key 有序选 multimap/multiset;高频组内批处理选 map<Key, vector<T>>;弱序重查找选 unordered multi。