C / C++ / 系统课时
multimap 和 multiset 有何不同
multimap 和 multiset 有何不同
当一个键可能对应多条记录,普通 map 或 set 的“键唯一”就不够用了。multimap 和 multiset 都允许重复键,但前者保存键值对,后者只保存可重复的值;配合 equal_range 可以一次定位某个键的完整区间。
学习目标
- 区分
multimap、multiset与map、set的数据模型 - 使用
equal_range遍历同一键对应的全部元素 - 理解重复键容器在查询、插入和修改上的关键边界
两类容器保存的数据不同
std::multimap<Key, T> 保存的是“键 → 值”关系,同一个键可以出现多次。例如一个课程标签 cpp 可以对应多条成绩记录。std::multiset<T> 则只有元素本身,元素同时承担“值”和“键”的角色,适合保存允许重复的有序数据,如一组分数或事件优先级。
它们与单值关联容器的差别可以概括为:
| 容器 | 元素形态 | 是否允许重复键 | 常见用途 |
|---|---|---|---|
map |
key -> value |
否 | 一个键唯一对应一个值 |
multimap |
key -> value |
是 | 一个键对应多条记录 |
set |
value |
否 | 去重并保持有序 |
multiset |
value |
是 | 保留重复值并保持有序 |
multimap 不提供 operator[],因为当一个键对应多条记录时,“下标访问应该返回哪一条”没有唯一答案。
用 equal_range 取得完整范围
equal_range(key) 返回一对迭代器,表示半开区间 [first, second)。其中 first 指向第一个等于该键的元素,second 指向最后一个等值元素之后的位置;若键不存在,两者通常相等。
下面的完整程序同时演示 multimap 和 multiset:
#include <iostream>
#include <map>
#include <set>
#include <string>
int main() {
std::multimap<std::string, int> scores{
{"cpp", 90},
{"python", 80},
{"cpp", 95}
};
auto [first, last] = scores.equal_range("cpp");
for (auto it = first; it != last; ++it) {
std::cout << it->first << ": " << it->second << '\n';
}
std::multiset<int> values{3, 1, 3, 2, 3};
auto [begin3, end3] = values.equal_range(3);
std::cout << "count(3): ";
int count = 0;
for (auto it = begin3; it != end3; ++it) {
++count;
}
std::cout << count << '\n';
}预期输出:
cpp: 90
cpp: 95
count(3): 3如果只关心重复次数,可以直接使用 count(key);如果还要读取、删除或逐条处理这些元素,equal_range 更合适,因为它直接给出可遍历的区间。
插入、查找与删除时要注意什么
向 multimap 或 multiset 插入已存在的键不会覆盖旧元素,而是新增一个等值元素。按键查找时,find 只返回其中一个匹配位置,不能代表全部重复元素;需要完整集合时应使用 equal_range。
删除也有两种常见粒度。调用 erase(key) 会删除该键对应的所有元素;若只想删掉其中一条,应先取得具体迭代器,再调用 erase(iterator)。
什么时候选择 multimap 或 multiset
如果业务数据天然是“一对多”,并且希望元素始终按键排序,multimap 很合适;如果只需要保存可重复、自动排序的值,则选择 multiset。两者的查找和插入通常是对数复杂度,遍历某个键的全部 k 个匹配项时,总成本可看作 O(log n + k)。
若主要需求是按键快速定位而不要求有序,还可以考虑 unordered_multimap 或 unordered_multiset;但当你需要范围查询、稳定的排序遍历,或依赖比较顺序时,有序的多重关联容器更直接。