麦地

Back

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 30
cpp

1.2 三个关键词#

  1. 有序:遍历时按比较器定义的顺序输出,默认升序。
  2. 唯一:同一比较意义下等价的键只保留一个。
  3. 平衡树:内部通常采用红黑树等自平衡二叉搜索树;标准主要保证复杂度,不指定具体树种。

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);                 // 拷贝
cpp

2.1 降序集合#

set<int, greater<int>> s;
s.insert(10);
s.insert(30);
s.insert(20);
for (int x : s) cout << x << ' '; // 30 20 10
cpp

2.2 其他元素类型#

set<string> words;                 // 字典序字符串集合
set<pair<int,int>> points;        // pair 自带字典序
set<tuple<int,int,int>> states;   // tuple 自带字典序
cpp

pair 作为键时按 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);
cpp

insert(value) 返回 pair<iterator,bool>:

auto [it, inserted] = s.insert(10);
cpp
  • it:指向新元素或已存在的等价元素。
  • inserted:是否真正插入。
if (s.insert(x).second) {
    // x 是第一次出现
}
cpp

3.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(); // 1
cpp

重复插入不会覆盖原元素;set 的键本身没有额外 value 可更新。需要修改键时必须先删除旧键,再插入新键。


4. 遍历、迭代器与最值#

4.1 正向遍历:默认升序#

for (int x : s) {
    cout << x << ' ';
}
cpp

等价迭代器写法:

for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << ' ';
}
cpp

4.2 反向遍历#

for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << ' ';
}
cpp

4.3 双向迭代器,不是随机访问迭代器#

++it;
--it;
auto it2 = next(it);
auto it3 = prev(it);
cpp

不能:

// it + 5; // 错误:set 迭代器不支持随机加减
cpp

std::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);
cpp

4.5 键不可直接修改#

即使通过非 const set 的迭代器,也不能原地修改键:

// *s.begin() = 100; // 错误
cpp

修改键可能破坏树的顺序。正确方法:

int oldValue = *it;
int newValue = compute();
s.erase(it);
s.insert(newValue);
cpp

C++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
}
cpp

C++20:

if (s.contains(x)) {}
cpp

5.2 lower_bound 与 upper_bound#

在默认升序 set 中:

auto lb = s.lower_bound(x); // 第一个 >= x
auto ub = s.upper_bound(x); // 第一个 >  x
cpp

判断存在:

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()) {
    // 不存在满足边界条件的元素,不能解引用
}
cpp

6. 删除元素#

6.1 按值删除#

size_t removed = s.erase(x); // 返回 0 或 1
cpp

如果 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 时未检查会出错
cpp

6.3 删除区间#

auto l = s.lower_bound(10);
auto r = s.upper_bound(20);
s.erase(l, r); // 删除 [l,r)
cpp

6.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
}
cpp

9.2 第一个大于 x#

auto it = s.upper_bound(x);
if (it != s.end()) {
    int y = *it; // y > x
}
cpp

9.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
}
cpp

9.5 找最接近 x 的元素#

差值使用 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})) {}
cpp

pair 自带字典序,适合二维点、区间、状态去重。

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)); // 删除所有 < threshold
cpp

这类批量删除的总成本与删除元素个数和树操作有关,不能只按一次 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);
cpp

12.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; // 错误
cpp

order_of_key、find_by_order 不属于标准 std::set。可选方案:

  1. 若值域可离散化:树状数组或线段树维护计数。
  2. 自己实现平衡树或跳表。
  3. GNU 编译环境允许时使用 PBDS 扩展。

PBDS 示例(非标准 C++,依赖 g++ 环境):

find_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;
cpp

14.3 对 begin 调用 prev,对空 set 取最值#

if (!s.empty()) {
    int mn = *s.begin();
    int mx = *prev(s.end());
}
cpp

14.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. 一页速记#

最终必须牢牢记住:

  1. set 自动有序且键唯一,重复插入不会生效。
  2. 插入、查找、删除通常为 O(log n),按迭代器删除为均摊 O(1)。
  3. begin() 是最小值,rbegin() 是最大值,使用前必须判空。
  4. lower_bound(x) 在默认升序下表示第一个 >= x,返回 end() 时不能解引用。
  5. set 迭代器是双向迭代器,不能 it+k,也没有下标。
  6. 键不可原地修改;应删除旧键再插入新键。
  7. 需要重复值用 multiset,只需要存在判断且不要求顺序时考虑 unordered_set。
  8. 标准 set 不能直接查询第 k 小或排名。
Comment seems to stuck. Try to refresh?✨