一、核心特性#
| 特性 | 说明 |
|---|---|
| 自动有序 | 元素按比较器排序,遍历时从小到大 |
| 允许重复 | 相同值可以插入多次,count(x) 返回出现次数 |
| 底层结构 | 平衡二叉搜索树(通常是红黑树) |
| 无下标 | 不支持 s[i],只能用迭代器访问 |
| 迭代器只读 | 元素是键,不允许通过迭代器修改 |
| 随机访问不支持 | 迭代器不能 it + k,只能 ++ / -- |
#include <set>
#include <iostream>
using namespace std;
int main() {
multiset<int> ms;
ms.insert(4);
ms.insert(2);
ms.insert(4);
ms.insert(4);
ms.insert(7);
// 遍历时有序且保留重复:2 4 4 4 7
for (int x : ms) cout << x << ' ';
cout << ms.count(4); // 3,统计出现次数
}cpp二、与 set 的关键区别#
| 操作 | set |
multiset |
|---|---|---|
| 插入重复值 | 被忽略,size 不变 |
成功插入,size 增加 |
insert 返回值 |
pair<iterator, bool> |
仅 iterator(总会成功) |
count(x) |
只有 0 或 1 | 0 到 n,即出现次数 |
erase(x) |
删除唯一的 x | 删除所有等于 x 的元素 |
| 用途 | 存在性 + 有序 | 多重集合 + 有序 |
insert 返回值差异示例:
set<int> s;
auto [it, ok] = s.insert(5); // ok 表示是否新插入
multiset<int> ms;
auto it2 = ms.insert(5); // 总是成功,直接返回迭代器cpp三、构造与比较器#
multiset<int> a; // 默认升序
multiset<int, greater<int>> b; // 降序
multiset<int> c(v.begin(), v.end()); // 用区间初始化
// pair 默认字典序
multiset<pair<int,int>> ms;
ms.insert({1, 5});
ms.insert({1, 3});
ms.insert({2, 0});
// 顺序:{1,3}, {1,5}, {2,0}
// 自定义比较器:必须满足严格弱序
struct Cmp {
bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
if (a.first != b.first) return a.first > b.first; // first 降序
return a.second < b.second; // second 升序
}
};
multiset<pair<int,int>, Cmp> cms;cpp注意:自定义比较器中不能用 <= 或 >=,必须是严格小于/大于,否则行为未定义。
四、核心接口#
multiset<int> ms;
// 插入:O(log n),总是成功
ms.insert(5);
ms.emplace(7);
// 查找:O(log n)
auto it = ms.find(5); // 指向某一个 5,找不到返回 end()
if (ms.count(5)) { /* 存在 */ } // count 返回出现次数
if (ms.contains(5)) { /* C++20 */ }
// 边界查找:O(log n)
auto lo = ms.lower_bound(5); // 第一个 >= 5
auto hi = ms.upper_bound(5); // 第一个 > 5
auto [l, r] = ms.equal_range(5); // [lo, hi) 区间,覆盖所有 5
// 统计某个值的个数:等价于 count(5)
int cnt = distance(ms.lower_bound(5), ms.upper_bound(5));
// 删除
ms.erase(5); // 删除所有 5,O(k + log n),k 为删除个数
ms.erase(ms.find(5)); // 只删除一个 5(迭代器版本),均摊 O(1) 调整 + 查找 O(log n)
ms.erase(ms.begin()); // 删除最小值
// 其他
ms.size();
ms.empty();
ms.clear();cpp五、最大陷阱:erase 的两种语义#
这是 multiset 竞赛中的最高频错误:
multiset<int> ms = {1, 2, 2, 4, 4, 4, 7};
ms.erase(4); // 删全部 → {1, 2, 2, 7}
// vs
ms.erase(ms.find(4)); // 只删一个 → {1, 2, 2, 4, 4, 7}cpp竞赛中”删除一个元素”的标准写法:
auto it = ms.find(x);
if (it != ms.end()) ms.erase(it); // 安全地只删一个cpp或者用 lower_bound(效果相同):
auto it = ms.lower_bound(x);
if (it != ms.end() && *it == x) ms.erase(it);cpp错误示范:直接 ms.erase(ms.find(x)) 而不判空,若 x 不存在会传入 end(),行为未定义。
六、迭代器与最值#
multiset<int> ms = {3, 1, 4, 1, 5, 9, 2, 6};
// 最值:使用前先判空!
if (!ms.empty()) {
int mn = *ms.begin(); // 最小值
int mx = *ms.rbegin(); // 最大值
}
// 正向遍历:1 1 2 3 4 5 6 9
for (int x : ms) cout << x << ' ';
// 反向遍历:9 6 5 4 3 2 1 1
for (auto it = ms.rbegin(); it != ms.rend(); ++it) cout << *it << ' ';
// 迭代器只能 ++/--,不能 +k
auto it = ms.begin();
advance(it, 3); // O(k) 移动,若必须这么做cpp七、前驱与后继(竞赛核心套路)#
multiset<int> ms = {1, 3, 5, 7, 9};
// 第一个 >= x 的元素
auto it = ms.lower_bound(4); // 指向 5
// 第一个 > x 的元素
auto it2 = ms.upper_bound(5); // 指向 7
// 严格前驱:最后一个小于 x 的元素
int x = 7;
auto it3 = ms.lower_bound(x); // 第一个 >= 7
if (it3 != ms.begin()) {
--it3; // 指向 5
}
// 与 x 最接近的值
int query = 6;
int best = -1;
auto it4 = ms.lower_bound(query);
if (it4 != ms.end()) best = *it4; // 候选:>= query 的最小值
if (it4 != ms.begin()) {
auto pre = prev(it4);
if (best == -1 || abs(*pre - query) < abs(best - query))
best = *pre;
}
// best = 5 或 7 中更接近 6 的那个 → 5 或 7(距离相同,这里优先取 7,可自行调整规则)cpp八、复杂度表#
| 操作 | 复杂度 |
|---|---|
insert / emplace |
O(log n) |
find / count / lower_bound / upper_bound |
O(log n) |
erase(迭代器) |
均摊 O(1) |
erase(值) |
O(log n + k),k 为删除的元素个数 |
begin / rbegin 取最值 |
O(1) |
| 遍历全部 | O(n) |
九、竞赛应用模板#
1. 动态维护多重集合的最值#
multiset<int> ms;
// 加入元素
ms.insert(x);
// 删除一个元素
auto it = ms.find(x);
if (it != ms.end()) ms.erase(it);
// 查询当前最值
if (!ms.empty()) {
cout << *ms.begin() << ' ' << *ms.rbegin();
}cpp2. 滑动窗口第 k 小 / 窗口中位数(multiset 版思路)#
标准 multiset 不支持 O(log n) 求第 k 小,但可以维护两个 multiset 实现动态中位数:
// 双 multiset 维护动态中位数
multiset<int> lo, hi; // lo 存较小一半(大根堆语义,取 *lo.rbegin()),hi 存较大一半
void add(int x) {
if (lo.empty() || x <= *lo.rbegin()) lo.insert(x);
else hi.insert(x);
// 平衡
if (lo.size() > hi.size() + 1) {
hi.insert(*lo.rbegin());
lo.erase(prev(lo.end()));
}
if (hi.size() > lo.size()) {
lo.insert(*hi.begin());
hi.erase(hi.begin());
}
}
void remove(int x) {
auto it = lo.find(x);
if (it != lo.end()) lo.erase(it);
else {
auto it2 = hi.find(x);
if (it2 != hi.end()) hi.erase(it2);
}
// 重新平衡(同 add 中的平衡逻辑)
}
double median() {
if (lo.size() == hi.size()) return (*lo.rbegin() + *hi.begin()) / 2.0;
return *lo.rbegin();
}cpp若确实需要频繁”求第 k 小”,竞赛中更常用:
- 树状数组 / 线段树(值域离散化后)
- GNU PBDS
tree<..., tree_order_statistics_node_update>
3. 贪心:匹配问题(经典”票务/书籍价格”模型)#
给若干物品价格和若干顾客出价,每位顾客买不超过其出价的最贵物品。
multiset<int> prices; // 物品价格
for (int i = 0; i < m; i++) {
int offer;
cin >> offer;
auto it = prices.upper_bound(offer); // 第一个 > offer
if (it == prices.begin()) {
cout << -1 << '\n'; // 没有 <= offer 的
} else {
--it; // 最后一个 <= offer
cout << *it << '\n';
prices.erase(it); // 只删这一个
}
}cpp4. 离散化 + 动态排名#
// 用 multiset 配合离散化解决逆序对/排名查询
multiset<int> ms;
// 查询比 x 小的元素个数(O(log n + 距离),距离可能退化)
int rank_of(int x) {
return distance(ms.begin(), ms.lower_bound(x)); // 注意:distance 是 O(n)!
}cpp警告:distance(begin(), it) 对树容器是 O(n),频繁查询排名请改用 PBDS 或树状数组。
十、迭代器失效规则#
| 操作 | 影响 |
|---|---|
insert |
不失效任何迭代器 |
erase(迭代器) |
只有被删的迭代器失效 |
erase(值) |
所有指向被删值的迭代器失效 |
clear / 析构 |
全部失效 |
| 无 rehash | 与 unordered 系列不同,没有扩容失效问题 |
遍历时安全删除:
for (auto it = ms.begin(); it != ms.end();) {
if (*it % 2 == 0) it = ms.erase(it); // erase 返回下一个有效迭代器
else ++it;
}cpp十一、容器选型#
| 需求 | 选择 |
|---|---|
| 有序 + 去重 | set |
| 有序 + 允许重复 | multiset |
| 只要存在性,不要有序 | unordered_set |
| 多重 + 只要存在性 | unordered_multiset 或 unordered_map<T,int> 计数 |
| 只要全局最值,不要前驱后继 | priority_queue(但删除任意元素不方便) |
| 值域小、要第 k 小 | 树状数组 / 线段树 |
| 需要排名和第 k 小 | PBDS tree |
multiset vs priority_queue 的关键差异:
priority_queue只能取堆顶、删堆顶;multiset可以删除任意值、查询前驱后继,代价是取最值同样是O(1)但整体常数略大。
十二、高频错误清单#
ms.erase(x)想删一个却删了全部 → 改用ms.erase(ms.find(x))并判空。find后没判end()就erase→ 未定义行为。- 取
*ms.begin()前没判空 → 空容器解引用崩溃。 - 试图
it + k或ms[i]→ 树容器不支持随机访问。 - 通过迭代器修改元素
*it = 5;→ 键不允许修改,编译错误。 - 自定义比较器用了
<=→ 必须是严格弱序。 - 频繁用
distance求排名 →O(n),超时。 - 把
count(x)当 bool 用时忘记它可以大于 1 → 不影响存在性判断,但统计次数时这正是用法。 lower_bound降序容器里语义反转 →greater<>下lower_bound是”第一个 ≤ x”。
十三、一页速记#
multiset<int> ms;
// 增
ms.insert(x); // O(log n),总会成功
// 删
ms.erase(ms.find(x)); // 删一个(先判 find != end)
ms.erase(x); // 删全部 x
// 查
ms.count(x); // 出现次数
auto it = ms.lower_bound(x); // 第一个 >= x(升序)
auto it = ms.upper_bound(x); // 第一个 > x(升序)
// 最值(先判空)
*ms.begin(); // 最小
*ms.rbegin(); // 最大
// 前驱
auto it = ms.lower_bound(x);
if (it != ms.begin()) { --it; /* *it < x */ }
// 遍历删除
for (auto it = ms.begin(); it != ms.end(); )
it = 需要删除 ? ms.erase(it) : next(it);cpp五句口诀:
- 与
set的唯一区别:允许重复。 erase(值)删全部,erase(迭代器)删一个——竞赛最大的坑。- 取最值、取前驱后继前先判空、判边界。
- 迭代器只能
++/--,distance是O(n),别当排名树用。 - 要”动态有序 + 任意删除”选
multiset;要”第 k 小”上树状数组或 PBDS。