1. 核心概念:有序且唯一#
1.1 基本定义#
#include <set>
std::set<int> s;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
set<int> s;cpp默认按升序保存互不相同的元素:
s.insert(30);
s.insert(10);
s.insert(20);
s.insert(10); // 重复插入不会增加元素
for (int x : s) cout << x << ' '; // 10 20 30cpp1.2 三个关键词#
- 有序:遍历时按比较器定义的顺序输出,默认升序。
- 唯一:同一比较意义下等价的键只保留一个。
- 平衡树:内部通常采用红黑树等自平衡二叉搜索树;标准主要保证复杂度,不指定具体树种。
1.3 set 不是数组#
// s[0]; // 错误:没有随机访问
// s.push_back(x); // 错误:不是顺序容器
// s.front(); // 错误cpp想取得最小值、最大值,应通过迭代器。
2. 创建与初始化#
set<int> a; // 空集合
set<int> b = {3, 1, 2}; // 有序保存 1 2 3
vector<int> v = {5, 1, 5, 3};
set<int> c(v.begin(), v.end()); // 用区间构造,自动去重并排序
set<int> d(c); // 拷贝cpp2.1 降序集合#
set<int, greater<int>> s;
s.insert(10);
s.insert(30);
s.insert(20);
for (int x : s) cout << x << ' '; // 30 20 10cpp2.2 其他元素类型#
set<string> words; // 字典序字符串集合
set<pair<int,int>> points; // pair 自带字典序
set<tuple<int,int,int>> states; // tuple 自带字典序cpppair 作为键时按 first、second 的顺序比较;tuple 按各分量字典序比较。
2.3 自定义比较器#
struct Cmp {
bool operator()(const string &a, const string &b) const {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
}
};
set<string, Cmp> words;cpp比较器必须满足严格弱序,通常使用 < 或 >,不要用可能溢出的减法。
2.4 等价性不等于 operator==#
set 判断两个键是否“相同”,依据的是比较器等价:
!comp(a, b) && !comp(b, a)cpp例如忽略大小写的比较器可能把 "ABC" 与 "abc" 视为同一键,即使字符串并不相等。插入、查找和删除都会遵循同一个比较器语义。
3. 插入元素#
3.1 insert#
s.insert(10);cppinsert(value) 返回 pair<iterator,bool>:
auto [it, inserted] = s.insert(10);cppit:指向新元素或已存在的等价元素。inserted:是否真正插入。
if (s.insert(x).second) {
// x 是第一次出现
}cpp3.2 emplace#
set<pair<int,int>> points;
points.insert({1, 2});
points.emplace(3, 4);cpp对 int 等基本类型,insert 和 emplace 通常没有性能区别。
3.3 重复值#
s.insert(10);
s.insert(10);
cout << s.size(); // 1cpp重复插入不会覆盖原元素;set 的键本身没有额外 value 可更新。需要修改键时必须先删除旧键,再插入新键。
4. 遍历、迭代器与最值#
4.1 正向遍历:默认升序#
for (int x : s) {
cout << x << ' ';
}cpp等价迭代器写法:
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << ' ';
}cpp4.2 反向遍历#
for (auto it = s.rbegin(); it != s.rend(); ++it) {
cout << *it << ' ';
}cpp4.3 双向迭代器,不是随机访问迭代器#
++it;
--it;
auto it2 = next(it);
auto it3 = prev(it);cpp不能:
// it + 5; // 错误:set 迭代器不支持随机加减cppstd::distance(s.begin(), it) 对双向迭代器是线性时间 O(n),不能直接当成对数时间的排名查询。
4.4 最小值与最大值#
if (!s.empty()) {
int mn = *s.begin();
int mx = *s.rbegin();
}cpp或使用:
auto mxIt = prev(s.end());cpp删除最小值:
s.erase(s.begin()); // 前提:非空cpp删除最大值:
auto it = prev(s.end());
s.erase(it);cpp4.5 键不可直接修改#
即使通过非 const set 的迭代器,也不能原地修改键:
// *s.begin() = 100; // 错误cpp修改键可能破坏树的顺序。正确方法:
int oldValue = *it;
int newValue = compute();
s.erase(it);
s.insert(newValue);cppC++17 也可使用 extract 取出节点后修改 value 再插回,但竞赛中删除再插入更直观。
5. 查找与二分边界#
5.1 find、count、contains#
auto it = s.find(x);
if (it != s.end()) {
// 找到
}
if (s.count(x)) {
// 存在;set 中 count 只可能是 0 或 1
}cppC++20:
if (s.contains(x)) {}cpp5.2 lower_bound 与 upper_bound#
在默认升序 set 中:
auto lb = s.lower_bound(x); // 第一个 >= x
auto ub = s.upper_bound(x); // 第一个 > xcpp判断存在:
if (lb != s.end() && *lb == x) {}cpp统计有序集合中 x 的个数通常无需 equal_range,因为 set 至多为 1。
5.3 equal_range#
auto [l, r] = s.equal_range(x); // 等价于 [lower_bound, upper_bound)cpp若 x 存在,l 指向 x,r 指向 x 的后继;若不存在,两者指向同一插入边界。
5.4 自定义顺序下的边界含义#
lower_bound / upper_bound 按照 set 的比较器顺序定义,不机械等同于数值上的 >= / >。例如 set<int,greater<int>> 是降序集合,边界应结合降序规则理解。竞赛中若容易混淆,可显式使用自定义 find/迭代逻辑或小样例验证。
5.5 使用前必须检查 end#
auto it = s.lower_bound(x);
if (it == s.end()) {
// 不存在满足边界条件的元素,不能解引用
}cpp6. 删除元素#
6.1 按值删除#
size_t removed = s.erase(x); // 返回 0 或 1cpp如果 x 不存在,按值 erase 不会产生错误,只是返回 0。
6.2 按迭代器删除#
auto it = s.find(x);
if (it != s.end()) {
it = s.erase(it); // 返回后继迭代器
}cpp不要直接:
// s.erase(s.find(x)); // find 返回 end 时未检查会出错cpp6.3 删除区间#
auto l = s.lower_bound(10);
auto r = s.upper_bound(20);
s.erase(l, r); // 删除 [l,r)cpp6.4 遍历时删除#
for (auto it = s.begin(); it != s.end();) {
if (*it % 2 == 0) it = s.erase(it);
else ++it;
}cpp传统兼容写法也常见:
if (condition) s.erase(it++);
else ++it;cpp但使用 erase 返回值的写法更直观。
6.5 清空#
s.clear();cpp清空所有元素,时间复杂度 O(n)。
7. 复杂度与迭代器失效#
7.1 常用复杂度#
设集合大小为 n:
| 操作 | 时间复杂度 |
|---|---|
insert / emplace |
O(log n) |
find / count |
O(log n) |
lower_bound / upper_bound |
O(log n) |
按值 erase |
O(log n) |
按迭代器 erase |
均摊 O(1) |
begin() / rbegin() 取最值 |
O(1) |
迭代器 ++/-- |
O(1) |
| 顺序遍历 | O(n) |
clear() |
O(n) |
| 拷贝 set | O(n) |
swap |
通常 O(1) |
实际树调整还包含旋转、指针操作和节点内存开销,因此常数一般大于 vector 排序、unordered_set 的平均哈希查找等方案。
7.2 迭代器失效规则#
- 插入不会使其他迭代器或引用失效。
- 删除只会使指向被删元素的迭代器和引用失效。
clear使所有迭代器失效。- swap 后迭代器通常仍指向原来的元素节点,但该节点逻辑上属于另一个容器,不要混淆容器归属。
这与 vector 扩容导致大量失效不同,是 set 的一个重要优势。
7.3 内存特点#
每个元素通常对应一个树节点,包含指针、平衡信息及元素本身。相比连续数组:
- 内存开销更大。
- 缓存局部性较差。
- 但动态有序插入删除更稳定。
8. 应用一:去重并保持有序#
vector<int> a = {4, 1, 3, 1, 4};
set<int> s(a.begin(), a.end());
vector<int> uniqueSorted(s.begin(), s.end());cpp结果:1 3 4。
总时间通常为 O(n log n)。
如果只需要静态数组去重:
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());cpp通常比 set 更快、内存更少。set 的优势在于动态插入删除时始终保持有序。
9. 应用二:前驱、后继与最近值#
9.1 第一个大于等于 x#
auto it = s.lower_bound(x);
if (it != s.end()) {
int y = *it; // y >= x
}cpp9.2 第一个大于 x#
auto it = s.upper_bound(x);
if (it != s.end()) {
int y = *it; // y > x
}cpp9.3 严格小于 x 的最大值#
auto it = s.lower_bound(x); // 第一个 >= x
if (it != s.begin()) {
--it;
int y = *it; // y < x
}cpp注意不是简单调用 prev(s.lower_bound(x)) 而不检查 begin。
9.4 小于等于 x 的最大值#
auto it = s.upper_bound(x); // 第一个 > x
if (it != s.begin()) {
--it;
int y = *it; // y <= x
}cpp9.5 找最接近 x 的元素#
int closestValue(const set<int> &s, int x) {
// 调用前提:s 非空
long long best = LLONG_MAX;
int ans = *s.begin();
auto check = [&](set<int>::const_iterator it) {
if (it == s.end()) return;
long long diff = llabs((long long)*it - x);
if (diff < best) {
best = diff;
ans = *it;
}
};
auto it = s.lower_bound(x);
check(it); // 第一个 >= x
if (it != s.begin()) check(prev(it)); // 最大 < x
return ans;
}cpp差值使用 long long,避免整数减法溢出或 abs(INT_MIN) 问题。若差值相同时需要更小/更大元素,应显式增加规则。
10. 应用三:动态维护最值与可用资源#
10.1 取并删除当前最小值#
if (!s.empty()) {
int mn = *s.begin();
s.erase(s.begin());
}cpp相比 priority_queue:
- priority_queue 只能方便取堆顶。
- set 可以同时取得最小、最大、前驱、后继,并任意删除已知元素。
10.2 可用编号池#
set<int> freeId;
for (int i = 1; i <= n; ++i) freeId.insert(i);
int id = *freeId.begin(); // 分配最小可用编号
freeId.erase(freeId.begin());
freeId.insert(id); // 回收编号cpp每次操作 O(log n)。
10.3 维护互不相同的坐标或边#
set<pair<int,int>> points;
points.insert({x, y});
if (points.count({x, y})) {}cpppair 自带字典序,适合二维点、区间、状态去重。
10.4 维护不重叠区间#
常见做法是用 set<pair<int,int>> 保存 {left,right},通过 upper_bound 找到可能覆盖或相邻的区间,再检查合并。此类代码必须仔细处理端点开闭、重叠和相邻关系,不能只看一个边界。
11. 应用四:遍历中按条件删除与维护集合#
维护一个有序集合,删除不满足条件的值:
for (auto it = s.begin(); it != s.end();) {
if (*it < threshold) it = s.erase(it);
else ++it;
}cpp删除某些前缀时可以直接:
s.erase(s.begin(), s.lower_bound(threshold)); // 删除所有 < thresholdcpp这类批量删除的总成本与删除元素个数和树操作有关,不能只按一次 lower_bound 的时间估算整体。
12. set 与其他容器的选择#
| 需求 | 推荐容器 |
|---|---|
| 动态唯一值,保持有序,需要前驱/后继 | set |
| 动态重复值,保持有序 | multiset |
| 只需快速判断存在,不要求顺序 | unordered_set 通常平均更快 |
| 静态数组去重排序 | vector + sort + unique |
| 只关心当前最大/最小,无需任意边界查询 | priority_queue |
| 需要按下标取第 k 小或查询排名 | 标准 set 不支持,考虑树状数组、平衡树或 PBDS |
| 需要 key 到 value 映射 | map/unordered_map |
12.1 与 multiset 的关键区别#
- set:同一等价键只能有一个;按值 erase 删除该键。
- multiset:允许重复;
count可为多个;按值 erase 会删除所有等价元素。
multiset 删除一个值应使用迭代器:
auto it = ms.find(x);
if (it != ms.end()) ms.erase(it);cpp12.2 与 unordered_set 的关键区别#
- set:有序,操作通常稳定
O(log n),支持 lower/upper。 - unordered_set:无序,哈希查找平均
O(1),最坏可退化,不支持前驱后继。
12.3 与 priority_queue 的关键区别#
priority_queue 只能高效访问堆顶;set 能访问最小、最大和任意有序边界,但单元素操作常数通常更高。
13. 第 k 小与排名:标准 set 不能直接做#
标准 set 的迭代器不支持随机跳转:
// s.begin() + k; // 错误cpporder_of_key、find_by_order 不属于标准 std::set。可选方案:
- 若值域可离散化:树状数组或线段树维护计数。
- 自己实现平衡树或跳表。
- GNU 编译环境允许时使用 PBDS 扩展。
PBDS 示例(非标准 C++,依赖 g++ 环境):
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update
>;
ordered_set os;
os.insert(10);
os.insert(20);
int rank0 = os.order_of_key(15); // 小于 15 的元素个数
auto it = os.find_by_order(0); // 第 0 小元素cppfind_by_order(k) 使用 0-based 下标;必须先确认 k 合法再解引用。比赛环境不支持 PBDS 时,应改用自己实现的平衡树或树状数组。
14. 高频错误与避坑清单#
14.1 误以为 set 有下标#
set 是树形有序容器,不支持 s[i]。需要下标就用排序后的 vector 或支持排名查询的数据结构。
14.2 直接解引用 lower_bound 返回的 end#
auto it = s.lower_bound(x);
if (it != s.end()) cout << *it;cpp14.3 对 begin 调用 prev,对空 set 取最值#
if (!s.empty()) {
int mn = *s.begin();
int mx = *prev(s.end());
}cpp14.4 试图修改迭代器指向的键#
键是集合排序结构的一部分,不能原地修改。删除旧键再插入新键。
14.5 忘记重复插入不会生效#
insert 不会覆盖已有等价键。要更新映射值应使用 map;要允许重复应使用 multiset。
14.6 混淆 multiset 按值 erase#
multiset 的 erase(value) 删除所有等价元素;set 虽然只有一个,也不应在未确认需求时混用两者代码。
14.7 自定义比较器不满足严格弱序#
不能用 <=、>= 或可能溢出的减法。否则树结构可能出现未定义或混乱行为。
14.8 把 distance 当排名查询#
对双向迭代器,distance(begin,it) 是 O(n)。需要 O(log n) 排名时使用专门数据结构。
14.9 只判断存在却使用 set#
如果不需要顺序、前驱、后继或最值,unordered_set、排序数组二分或布尔数组可能更快。
15. 一页速记#
#include <set>
set<int> s; // 默认升序、唯一
set<int, greater<int>> desc; // 降序
set<pair<int,int>> points; // pair 字典序
s.insert(x); // O(log n),重复无效
auto [it, inserted] = s.insert(x);
s.emplace(x);
s.count(x); // 0 或 1
auto it2 = s.find(x); // 找不到返回 end()
auto lb = s.lower_bound(x); // 默认升序:第一个 >= x
auto ub = s.upper_bound(x); // 默认升序:第一个 > x
if (lb != s.end() && *lb == x) {} // 存在
if (lb != s.end()) { /* 后继 */ }
if (lb != s.begin()) { --lb; /* 严格前驱 */ }
if (!s.empty()) {
int mn = *s.begin();
int mx = *s.rbegin();
s.erase(s.begin()); // 删除最小值
s.erase(prev(s.end())); // 删除最大值
}
s.erase(x); // 返回 0/1
auto it3 = s.find(x);
if (it3 != s.end()) s.erase(it3); // 删除一个元素
for (int x : s) {} // 按比较器顺序遍历
for (auto it = s.rbegin(); it != s.rend(); ++it) {} // 反向
for (auto it = s.begin(); it != s.end();) {
if (condition(*it)) it = s.erase(it);
else ++it;
}
s.size(); s.empty(); s.clear();
// 有序去重
set<int> uniqueSet(a.begin(), a.end());
vector<int> b(uniqueSet.begin(), uniqueSet.end());cpp最终必须牢牢记住:
- set 自动有序且键唯一,重复插入不会生效。
- 插入、查找、删除通常为
O(log n),按迭代器删除为均摊O(1)。 begin()是最小值,rbegin()是最大值,使用前必须判空。lower_bound(x)在默认升序下表示第一个>= x,返回end()时不能解引用。- set 迭代器是双向迭代器,不能
it+k,也没有下标。 - 键不可原地修改;应删除旧键再插入新键。
- 需要重复值用 multiset,只需要存在判断且不要求顺序时考虑 unordered_set。
- 标准 set 不能直接查询第 k 小或排名。