multiset
std::multiset 是 C++ 标准库中的有序关联容器，与 std::set 类似，但允许存储重复的键。它基于平衡二叉搜索树实现，元素始终按键的排序规则保持有序。
当你需要一个有序集合，且同一元素可能出现多次时，multiset 是天然的选择。
头文件与基本特征
使用 multiset 时，需要包含头文件：
#include <set>
常见特征如下：
| 特征 | 说明 |
|---|---|
| 键是否允许重复 | 是，允许多个相等键 |
| 是否有序 | 是，按键的排序规则排序 |
| 底层结构 | 通常为平衡二叉搜索树 |
| 插入复杂度 | O(log n) |
| 查找复杂度 | O(log n) |
| 删除复杂度 | O(log n) 单个，区间删除视情况而定 |
| 迭代器失效 | 删除对应元素时失效，插入不失效 |
基本用法
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(2);
ms.insert(5); // 重复元素可以插入
ms.insert(8);
ms.insert(2);
for (std::multiset<int>::iterator it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << ' ';
}
// 输出：2 2 5 5 8（按升序排列）
return 0;
}
插入重复元素时，multiset 会将它们都保留。等值元素的顺序为插入顺序（C++98/03 未严格规定，实践中通常追加在已有等值元素之后）。
常用成员函数
| 函数 | 作用 |
|---|---|
insert(x) | 插入元素，返回迭代器（非 pair，和 set 不同） |
erase(x) | 删除所有等于 x 的元素，返回删除数量 |
erase(it) | 删除迭代器指向的元素 |
find(x) | 查找等于 x 的元素，返回其中一个的迭代器 |
count(x) | 返回等于 x 的元素数量 |
lower_bound(x) | 第一个不小于 x 的元素 |
upper_bound(x) | 第一个大于 x 的元素 |
equal_range(x) | 返回等值范围 [lower_bound, upper_bound) |
size() | 元素个数 |
empty() | 判断是否为空 |
clear() | 清空 |
需要注意：multiset::erase(x) 按值删除时会删除所有匹配元素，而不是只删一个。这和 set 的行为一致，但在 multiset 里影响更大。
要只删除一个等值元素，使用 erase(find(x))：
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);
// 只删除一个 5
std::multiset<int>::iterator it = ms.find(5);
if (it != ms.end()) {
ms.erase(it);
}
std::cout << ms.count(5) << '\n'; // 2
return 0;
}
查找与遍历等值范围
equal_range 用于一次获取等值范围：
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms;
ms.insert(3);
ms.insert(5);
ms.insert(5);
ms.insert(5);
ms.insert(7);
typedef std::multiset<int>::iterator Iter;
std::pair<Iter, Iter> range = ms.equal_range(5);
std::cout << "count of 5: ";
int count = 0;
for (Iter it = range.first; it != range.second; ++it) {
++count;
}
std::cout << count << '\n'; // 3
return 0;
}
lower_bound 和 upper_bound 也可以配合使用达到同样效果。
自定义排序
和 set 一样，multiset 支持自定义比较器：
#include <iostream>
#include <set>
struct Descending {
bool operator()(int a, int b) const {
return a > b;
}
};
int main() {
std::multiset<int, Descending> ms;
ms.insert(1);
ms.insert(3);
ms.insert(1);
ms.insert(2);
for (std::multiset<int, Descending>::iterator it = ms.begin(); it != ms.end(); ++it) {
std::cout << *it << ' ';
}
// 输出：3 2 1 1
return 0;
}
multiset vs set vs multimap
| 容器 | 键唯一 | 有序 | 值类型 |
|---|---|---|---|
set | 是 | 是 | 单个键值 |
multiset | 否 | 是 | 单个键值 |
map | 是 | 是 | 键值对 |
multimap | 否 | 是 | 键值对 |
选择规则很简单：只需要统计或维护有序的可重复集合时，选 multiset；需要键值映射时，选 multimap。
典型场景
- 成绩排名中存在并列名次时存储成绩。
- 事件时间线中同一时间可能发生多个事件。
- 维护一个有序的日志记录，允许相等的时间戳。
- 需要快速统计某个值出现次数，且数据需要保持有序。
使用注意
erase(x)按值删除会移除所有等值元素，需要仔细确认。count(x)在multiset中的复杂度是O(log n + k)（k 为等值元素个数），等值元素极多时注意性能。- 等值元素的迭代顺序未严格规定（C++98/03），不要依赖它们的相对顺序。
- 插入不会使迭代器失效，删除只会使被删元素的迭代器失效。
小结
std::multiset 是 set 的可重复版本，适合需要有序存储且允许重复键的场景。通过 count、equal_range、lower_bound / upper_bound 等接口，可以方便地处理等值范围。使用时要注意按值删除会清空所有匹配元素，必要时改用迭代器删除。