12. set与multiset容器：set的构造与操作、set的自动排序、set的查找与统计、multiset与set的区别
好，咱们今天来聊聊 set 和 multiset。这两个容器，说白了就是「有序集合」和「有序多重集合」。我当年刚接触 STL 时，觉得 set 不就是个数组嘛，有啥特别的？后来在项目里被坑过一次，才真正理解了它的价值。
set 的核心特点就两个：自动排序 和 元素唯一。你往里面丢数据，它自己就排好序了，重复的还会被自动扔掉。multiset 呢，允许重复，但同样自动排序。
一句话总结： set 是「排好序且不重复的集合」，multiset 是「排好序且允许重复的集合」。
12.1 set 的构造与基本操作
set 的构造方式挺灵活的。我个人习惯用默认构造，然后一个个 insert。当然，你也可以用初始化列表，或者从其他容器拷贝。
#include <iostream>
#include <set>
using namespace std;
int main() {
// 默认构造
set<int> s1;
s1.insert(5);
s1.insert(3);
s1.insert(8);
s1.insert(1);
s1.insert(3); // 重复，会被忽略
// 初始化列表构造（C++11 起）
set<int> s2 = {4, 2, 7, 2, 9};
// 拷贝构造
set<int> s3(s2);
// 遍历
for (int val : s1) {
cout << val << " "; // 输出：1 3 5 8
}
cout << endl;
return 0;
}你看，插入顺序是 5、3、8、1、3，但输出却是 1、3、5、8。这就是自动排序的效果。重复的 3 只保留了一个。
小技巧： set 的 insert 返回一个 pair<iterator, bool>，第二个 bool 表示插入是否成功。你可以用它来判断元素是否已存在。
12.2 set 的自动排序机制
set 底层用的是红黑树（一种平衡二叉搜索树）。每次插入元素，都会触发一次 O(log n) 的查找和插入操作，同时保持树平衡。
默认情况下，set 使用 std::less<T> 作为比较函数，也就是升序排列。如果你想降序，可以指定 greater<T>。
// 降序排列的 set
set<int, greater<int>> s = {3, 1, 4, 1, 5, 9};
for (int v : s) cout << v << " "; // 输出：9 5 4 3 1嗯，这里要注意：比较函数必须满足「严格弱序」条件。说白了就是：不能同时出现 a < b 和 b < a 都为 true 的情况。我曾经在自定义类型时踩过这个坑，比较函数写反了，结果 set 直接崩溃。
避坑指南： 自定义类型放入 set 时，必须重载 operator< 或者提供自定义比较函数。否则编译会报错。我曾经图省事没写，结果排查了半天才发现是这个问题。
12.3 set 的查找与统计
set 的查找效率很高，O(log n)。常用的查找方法有：
- find(key)：返回迭代器，找不到返回 end()
- count(key)：返回元素个数（set 中只能是 0 或 1）
- lower_bound(key)：返回第一个 >= key 的迭代器
- upper_bound(key)：返回第一个 > key 的迭代器
- equal_range(key)：返回 pair，包含 lower_bound 和 upper_bound
set<int> s = {10, 20, 30, 40, 50};
// 查找
auto it = s.find(30);
if (it != s.end()) {
cout << "找到了: " << *it << endl; // 30
}
// 统计
cout << "30 的个数: " << s.count(30) << endl; // 1
cout << "35 的个数: " << s.count(35) << endl; // 0
// 范围查找
auto low = s.lower_bound(25); // 指向 30
auto up = s.upper_bound(35); // 指向 40
for (auto it = low; it != up; ++it) {
cout << *it << " "; // 输出：30
}你想想看，如果要在 vector 里做同样的事，你得先排序，再二分查找，麻烦多了。set 把这些都封装好了，直接用就行。
12.4 multiset 与 set 的区别
multiset 和 set 的接口几乎一模一样。唯一的区别就是：multiset 允许重复元素。
| 特性 | set | multiset |
|---|---|---|
| 元素唯一性 | 是 | 否 |
| 自动排序 | 是 | 是 |
| insert 返回值 | pair<iterator, bool> | iterator（直接返回插入位置） |
| count(key) 返回值 | 0 或 1 | 0 到 n |
| erase(key) 行为 | 删除一个元素，返回 0 或 1 | 删除所有等于 key 的元素，返回删除个数 |
multiset<int> ms = {1, 2, 2, 3, 3, 3, 4};
cout << "2 的个数: " << ms.count(2) << endl; // 2
cout << "3 的个数: " << ms.count(3) << endl; // 3
// 删除所有等于 2 的元素
int removed = ms.erase(2);
cout << "删除了 " << removed << " 个元素" << endl; // 2
// 只删除一个等于 3 的元素
auto it = ms.find(3);
if (it != ms.end()) {
ms.erase(it);
}
cout << "剩余 3 的个数: " << ms.count(3) << endl; // 2实际场景： 我在做日志分析系统时，用 multiset 来存储所有请求的响应时间。因为同一个响应时间可能出现多次，用 multiset 天然支持重复，而且自动排序后，取中位数、百分位数都非常方便。
12.5 知识体系总览
下面这张图把 set 和 multiset 的核心知识点串起来了，方便你整体把握。
set 和 multiset 在实际项目中用得非常多。比如去重、排序、快速查找、范围查询等场景，它们都是很好的选择。我个人建议：需要唯一性就用 set，需要重复就用 multiset，别搞混了。
性能提示： set 的插入、删除、查找都是 O(log n)。如果你只需要「不重复」而不需要「排序」，可以考虑 unordered_set（哈希表实现，平均 O(1)）。但 unordered_set 不保证顺序，而且内存开销更大。
好了，set 和 multiset 的核心内容就这些。记住它们的特性，写代码时多想想「我需要排序吗？」「我需要重复吗？」，选对容器，事半功倍。