STL之multiset 常见API介绍

有序（自动升序）、可重复的set

底层是红黑树，查找、插入、删除复杂度均为O(log n)

1 定义

#include <set> // multiset 包含在 set 头文件中 using namespace std; // 1. 默认升序 multiset multiset<int> ms; // 2. 自定义降序 multiset multiset<int, greater<int>> ms_desc; // 3. 初始化方式 multiset<int> ms1 = {1, 3, 3, 5}; // 列表初始化 multiset<int> ms2(ms1); // 拷贝初始化

2 插入

multiset<int> ms; ms.insert(3); // 插入 3 ms.insert(3); // 再次插入 3，允许重复 ms.emplace(5); // 直接构造 5，效率优于 insert // 插入区间 vector<int> v = {1, 2}; ms.insert(v.begin(), v.end()); // 最终容器：1,2,3,3,5

3 删除

multiset<int> ms = {1,3,3,5}; ms.erase(3); // 删除所有 3 → 容器：1,5 ms.erase(ms.begin()); // 删除第一个元素 → 容器：5，通过迭代器删除 ms.clear(); // 清空容器

4 查找

multiset<int> ms = {1,3,3,5}; // 查找 auto it = ms.find(3); // 指向第一个 3 // 统计 int num = ms.count(3); // 结果：2 // 区间查找 auto left = ms.lower_bound(3); // 指向第一个 3 auto right = ms.upper_bound(3); // 指向 5 // 遍历所有 3 for(auto i = left; i != right; ++i) cout << *i << " "; // equal_range 简化写法 auto range = ms.equal_range(3); for(auto i = range.first; i != range.second; ++i) cout << *i << " ";

其中，我重点介绍下lower_bound和upper_bound

这两个API都是二分查找，找不到都返回ms.end()

若ms.upper_bound(-1) 返回ms.begin()

5 其他常见操作

multiset<int> ms = {1,3,3}; cout << ms.size(); // 3 cout << ms.empty(); // 0（false）