C++ std::multiset容器的用法（附带实例）

多重集合（multiset）是标准模板库中的一个有序容器，允许存储重复的元素。

multiset 和 set 在结构和特性上有很多相似之处，multiset 的一个重要特点是允许元素重复。要使用多重集合，需要引入相应的头文件。

C++ multiset的基本操作

为了方便管理元素，多重集合提供了一些基本操作方法，如下表所示。

表：多重集合的基本操作
方法	作用	时间复杂度
insert(x)	将元素 x 插入多重集合	O(log n)
erase(it or val)	从多重集合中删除一个或多个元素	O(k + log n)，其中 k 为删除的元素的个数
find(x)	在多重集合中查找元素 x，返回迭代器	O(log n)
count(x)	返回 x 在多重集合中出现的次数	O(log n)
size()	返回多重集合中元素的个数	O(1)
empty()	判断多重集合是否为空	O(1)
clear()	清空多重集合中的所有元素	O(n)
begin()	返回指向多重集合中第一个元素位置的迭代器	O(1)
end()	返回指向多重集合中最后一个元素的下一个位置的迭代器	O(1)

此外，多重集合还支持其他一些高级操作，例如 lower_bound()、upper_bound() 等，这些操作的时间复杂度同样是 O(log n)。

和 set 集合一样，在使用 erase() 且传入的参数为迭代器时，需要保证迭代器合法，否则可能导致运行时错误（RE）或超时错误（TLE）。

值得注意的是，若 erase() 参数为值 x，则会删除集合中所有等于 x 的元素。如果只想删除一个，则可以使用 st.erase(st.find(x)) 这样的组合来实现，意思是先找到第一个 x 的迭代器，然后删除这个 x。

在标准模板库中还有一种集合，可以将插入和查询的时间复杂度降低到 O(1)，那就是unordered_set（无序集合），它的底层采用哈希表而非红黑树。不过，它的时间复杂度并不稳定，在特殊情况下可能退化到O(n)，因此不推荐使用。在大多数场景下，直接使用集合（set或multiset）更为合适，竞赛题目不太可能会涉及这个方面。

C++ multiset实际应用

【实例】小 e 是个充满好奇心的孩子，他在广场上嬉戏时，经历了 n 件有趣的事情。这些事情可以归为以下三类：

事件1：他捡到了一个大小为 x 的气球。
事件2：有一个大小为x的气球从小 e 的手中飞走了（这个气球之前确实在小 e 的手中）。
事件3：小 e 好奇地询问自己手里目前最大的气球有多大。

每当发生事件 3 时，如果小 e 手中有气球，我们会告诉他当前手中最大的气球有多大；如果手里空空如也，则会输出“No Balloon!”来回应他的好奇心。

输入格式：
注意本题有多组测试用例。第一行包含一个整数 T，代表测试用例的总数（1≤T≤1000）。

对于每组测试用例：

首先会有一行，仅包含一个整数 n，表示事件的数量（1≤∑n≤10^5）。
接下来的n行，每行描述一个事件。
每一行的第一个整数表示事件类型 op（op∈{1,2,3}）。

如果事件类型为 1 或 2，该行的第 2 个整数 x 表示气球的大小（1≤x≤10^9）。

输出格式：
对于事件3，输出结果。

样例如下：

解题思路：本题需要动态维护一个集合的最大值，并且要支持插入和删除操作。使用多重集合的特性（快速插入、修改、允许重复元素、自动排序），即可解决问题。

#include <bits/stdc++.h>
using namespace std;

// 定义一个函数 solve，用于处理每个测试用例
void solve() {
    int n;
    cin >> n;                       // 读取操作次数 n

    multiset<int> st;               // 创建一个多重集合容器，用于存储整数

    for (int i = 1; i <= n; ++i) {  // 循环 n 次，每次进行一次操作
        int op;
        cin >> op;                  // 读取操作类型 op

        if (op == 1) {
            // 如果操作类型为 1，则插入元素
            int x;
            cin >> x;               // 读取要插入的元素 x
            st.insert(x);           // 将 x 插入多重集合中
        } else if (op == 2) {
            // 如果操作类型为 2，则删除元素
            int x;
            cin >> x;               // 读取要删除的元素 x
            // 注意：这里要使用 st.find(x) 找到第一个等于 x 的元素，然后调用 erase 删除它
            st.erase(st.find(x));
        } else {
            // 如果操作类型为 3，则输出当前最大的元素
            if (st.size())          // 只要多重集合不为空，就可以输出
                cout << *st.rbegin() << '\n';   // 输出多重集合中的最大元素
            else                    // 反之输出 No Balloon!
                cout << "No Balloon!" << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);              // 优化输入/输出流

    int t;
    cin >> t;                       // 读取测试用例的数量
    while (t--)                     // 对每个测试用例进行处理
        solve();                    // 调用 solve 函数处理每个测试用例

    return 0;
}

C++ std::multiset容器的用法（附带实例）

C++ multiset的基本操作

C++ multiset实际应用

相关文章