multiset是允许重复元素的有序关联容器，而set不允许重复；二者均基于红黑树实现、自动升序、支持O(log n)操作，但multiset特有erase(key)删除所有匹配项、equal_range()获取重复元素区间。
multiset 是什么，和 set 有什么根本区别
multiset 是 C++ 标准库中基于红黑树实现的有序关联容器，它允许重复键值（即相同元素可多次插入），而 set 不允许。两者都自动维持元素升序排列、支持 O(log n) 插入/查找/删除，但底层行为差异直接影响使用逻辑：
-
multiset的find()只返回一个匹配迭代器（不保证是第一个或最后一个） -
count()返回重复次数，equal_range()才能拿到所有相同元素的区间 - 迭代器不可修改所指元素（因为会破坏排序），但可修改其副本或用于 erase/insert
插入、遍历、删指定值的所有实例
插入和遍历和其他容器类似，但删除需特别注意“删一个”还是“删全部”：
-
insert(x)总是成功，重复值照插不误 - 遍历时用
for (const auto& v : ms)得到升序序列，含重复 - 删除单个匹配值：用
ms.erase(ms.find(x))（前提是find()不返回end()） - 删除所有匹配值：直接
ms.erase(x)（这是multiset特有的重载，set没这个） - 删除某迭代器位置：
ms.erase(it)，只删一个
std::multisetms = {1, 2, 2, 3, 3, 3}; ms.erase(3); // 全部 3 被删，剩下 {1,2,2} ms.insert(2); // 现在是 {1,2,2,2}，不是 {1,2,2,2,3}
如何安全获取所有重复元素的位置
不能依赖 find()，它只给一个；也不能用 lower_bound()/upper_bound() 自己算——容易越界或漏判。正确方式是统一用 equal_range()：
- 返回
std::pair，左闭右开区间 - 若元素不存在，两个迭代器相等，都等于
end() - 区间内所有元素严格等于目标值，且已排序（当然，它们本来就是相等的）
auto range = ms.equal_range(2);
for (auto it = range.first; it != range.second; ++it) {
std::cout << *it << " "; // 输出所有 2
}
性能与替代方案权衡：什么时候不该用 multiset
multiset 的树结构带来稳定对数复杂度，但常数较大，且不支持随机访问。以下场景要谨慎：
立即学习“C++免费学习笔记（深入）”；
- 只需计数不需要有序遍历：用
std::unordered_map更快，内存也更省 - 插入后只查总数、不遍历具体元素：
map或unordered_map+operator[]足够 - 需频繁按位置取第 k 小（如 TopK）：考虑
std::priority_queue或带索引的平衡树（如 pb_ds tree） - 元素类型重载了
operator 但语义不稳定（比如浮点比较未处理精度）：会导致插入错位或find失败
真正需要 multiset 的典型场景是：既要自动排序，又要保留重复，并且得逐个访问这些重复值（比如事件时间戳队列、带优先级的待处理任务池）。
重复元素的“存在性”和“数量”是两回事，multiset 解决的是前者+顺序，后者只是附带能力；别把它当计数器用。
