麦地

Back

一、核心特性#

特性 说明
自动有序 元素按比较器排序,遍历时从小到大
允许重复 相同值可以插入多次,count(x) 返回出现次数
底层结构 平衡二叉搜索树(通常是红黑树)
无下标 不支持 s[i],只能用迭代器访问
迭代器只读 元素是键,不允许通过迭代器修改
随机访问不支持 迭代器不能 it + k,只能 ++ / --

二、与 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

三、构造与比较器#

注意:自定义比较器中不能用 <= 或 >=,必须是严格小于/大于,否则行为未定义。


四、核心接口#


五、最大陷阱: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(),行为未定义。


六、迭代器与最值#


七、前驱与后继(竞赛核心套路)#


八、复杂度表#

操作 复杂度
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();
}
cpp

2. 滑动窗口第 k 小 / 窗口中位数(multiset 版思路)#

标准 multiset 不支持 O(log n) 求第 k 小,但可以维护两个 multiset 实现动态中位数:

若确实需要频繁”求第 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);                  // 只删这一个
    }
}
cpp

4. 离散化 + 动态排名#

// 用 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) 但整体常数略大。

十二、高频错误清单#

  1. ms.erase(x) 想删一个却删了全部 → 改用 ms.erase(ms.find(x)) 并判空。
  2. find 后没判 end() 就 erase → 未定义行为。
  3. 取 *ms.begin() 前没判空 → 空容器解引用崩溃。
  4. 试图 it + k 或 ms[i] → 树容器不支持随机访问。
  5. 通过迭代器修改元素 *it = 5; → 键不允许修改,编译错误。
  6. 自定义比较器用了 <= → 必须是严格弱序。
  7. 频繁用 distance 求排名 → O(n),超时。
  8. 把 count(x) 当 bool 用时忘记它可以大于 1 → 不影响存在性判断,但统计次数时这正是用法。
  9. lower_bound 降序容器里语义反转 → greater<> 下 lower_bound 是”第一个 ≤ x”。

十三、一页速记#

五句口诀:

  1. 与 set 的唯一区别:允许重复。
  2. erase(值) 删全部,erase(迭代器) 删一个——竞赛最大的坑。
  3. 取最值、取前驱后继前先判空、判边界。
  4. 迭代器只能 ++/--,distance 是 O(n),别当排名树用。
  5. 要”动态有序 + 任意删除”选 multiset;要”第 k 小”上树状数组或 PBDS。
Comment seems to stuck. Try to refresh?✨