C++ set

一篇搞定 set 的所有常用功能

---

一、set 是什么？

1.1 核心特性

set 是 C++ 标准库中的关联式容器，它的核心特性可以用三句话概括：

特性	说明
自动排序	元素默认按升序排列（从小到大）
元素唯一	不允许有重复的元素
快速查找	插入、删除、查找的时间复杂度都是 O(log n)

1.2 底层原理（了解即可）

set 的底层实现是红黑树（一种自平衡的二叉搜索树）。这意味着：

• 插入元素时，会自动找到合适的位置并保持有序
• 查找元素时，像二分查找一样高效
• 遍历时，得到的是有序序列

插入顺序：5, 1, 4, 2, 3，2
实际存储：1, 2, 3, 4, 5  ← 自动排序+去重

1.3 什么时候用 set？

适合用 set 的场景：

• 需要维护一个有序的集合
• 需要快速判断某个值是否存在
• 需要去重并排序
• 需要动态插入删除，且随时查询

不适合用 set 的场景：

• 只需要存数据，不需要有序 → 用 vector维克多
• 不需要有序，只需要快速查找 → 用 unordered_set哈希表
• 只需要最大/最小值 → 用 priority_queue优先队列

---

二、准备工作

2.1 头文件

#include <set>           // 只引入 set
// 或者
#include <bits/stdc++.h> // 竞赛万能头，包含所有

2.2 命名空间

using namespace std;

---

三、set 的常用操作（核心）

3.1 定义和初始化

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

int main() {
    // 1. 默认构造（升序）
    set<int> s1;
    
    // 2. 降序排列
    set<int, greater<int>> s2;
    
    // 3. 用初始化列表构造（自动排序去重）
    set<int> s3 = {5, 1, 4, 2, 3, 1};  // 实际存储：{1, 2, 3, 4, 5}
    
    // 4. 用迭代器区间构造（了解即可）
    vector<int> v = {10, 20, 30};
    set<int> s4(v.begin(), v.end());
    
    // 5. 拷贝构造
    set<int> s5(s3);
    
    return 0;
}

3.2 插入元素 insert()

set<int> s;

// 插入单个元素
s.insert(10);  //插入10
s.insert(20);  //插入20
s.insert(10);  // 插入失败，因为 10 已存在

// 批量插入
s.insert({30, 40, 50});

// 插入一段区间
vector<int> v = {60, 70};
s.insert(v.begin(), v.end());

扩展：insert 的返回值可以判断插入是否成功：

auto result = s.insert(10);
if (result.second) {
    cout << "插入成功，元素为：" << *result.first << endl;
} else {
    cout << "元素已存在，插入失败" << endl;
}

3.3 删除元素 erase()

set<int> s = {1, 2, 3, 4, 5};

// 方式1：按值删除（最常用）
s.erase(3);  // 删除元素 3

// 方式2：按迭代器删除
auto it = s.find(4);
if (it != s.end()) {
    s.erase(it);  // 删除 4
}

// 方式3：删除最小值
s.erase(s.begin());

// 方式4：删除最大值
s.erase(--s.end());

// 方式5：清空所有
s.clear();

3.4 查找元素

set<int> s = {1, 2, 3, 4, 5};

// 方法1：find()（推荐）
auto it = s.find(3);
if (it != s.end()) {
    cout << "找到了：" << *it << endl;
} else {
    cout << "不存在" << endl;
}

// 方法2：count()（更简洁）
if (s.count(3)==1) {
    cout << "元素存在" << endl;
}else{
    cout << "元素不存在" << endl;
}
// count 对 set 只返回 0 或 1，因为询问的是元素是否存在（一般疑问句）

两种方法的区别：

• find() 返回迭代器，可以进一步操作（如删除）
• count() 只返回 0/1，代码更简洁

3.5 遍历元素

set<int> s = {1, 2, 3, 4, 5};

// 方式1：迭代器（正序，从小到大）
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}
// 输出：1 2 3 4 5

// 方式2：范围 for（最简洁）
for (int x : s) {
    cout << x << " ";
}

// 方式3：反向迭代器（从大到小）
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " ";
}
// 输出：5 4 3 2 1

// 取最小元素
int min_val = *s.begin();

// 取最大元素
int max_val = *s.rbegin();

注意：set 的迭代器是只读的，不能通过迭代器修改元素值。

auto it = s.begin();
*it = 10;  // 会编译错误！迭代器是 const 的，无法直接修改

要修改，只能先删除再插入

3.6 大小和状态

set<int> s = {1, 2, 3};

int n = s.size();        // 返回长度：3
bool empty = s.empty();  // 返回set是否为空（布尔值，1为是，0为否）：0

if (!s.empty()) {
    cout << "set 中有 " << s.size() << " 个元素" << endl;
}

---

四、二分查找三兄弟

这是 set 最强大的功能之一

函数	功能	返回值
lower_bound(x)	第一个 ≥ x 的元素	迭代器
upper_bound(x)	第一个 > x 的元素
equal_range(x)	同时返回 lower_bound 和 upper_bound	pair

4.1 lower_bound 和 upper_bound

set<int> s = {1, 3, 5, 7, 9};

// lower_bound：找第一个 >= x 的
auto it1 = s.lower_bound(5);   // 指向 5
auto it2 = s.lower_bound(6);   // 指向 7
auto it3 = s.lower_bound(10);  // 指向 s.end()（不存在）

// upper_bound：找第一个 > x 的
auto it4 = s.upper_bound(5);   // 指向 7
auto it5 = s.upper_bound(8);   // 指向 9

4.2 经典应用场景

场景1：找第一个大于 x 的数

auto it = s.upper_bound(x);
if (it != s.end()) {
    cout << "第一个大于 " << x << " 的是：" << *it << endl;
}

场景2：找第一个大于等于 x 的数

auto it = s.lower_bound(x);
if (it != s.end()) {
    cout << "第一个大于等于 " << x << " 的是：" << *it << endl;
}

场景3：找小于 x 的最大数（前驱）

auto it = s.lower_bound(x);
if (it != s.begin()) {
    --it;
    cout << "小于 " << x << " 的最大数是：" << *it << endl;
}

场景4：判断 x 是否存在

auto it = s.lower_bound(x);
if (it != s.end() && *it == x) {
    cout << x << " 存在" << endl;
}

4.3 equal_range（了解即可）

set<int> s = {1, 3, 5, 7, 9};

auto range = s.equal_range(5);
// range.first 指向第一个 >=5（即 5）
// range.second 指向第一个 >5（即 7）

// 区间 [range.first, range.second) 内的所有元素都等于 5
// 对于 set，这个区间最多只有一个元素

---

五、自定义排序

5.1 默认排序：升序

set<int> s;              // 默认升序
set<int, less<int>> s;   // 显式写也是升序

5.2 降序排列

// 方法1：使用 greater
set<int, greater<int>> s = {1, 5, 3, 4, 2};
// 存储为：{5, 4, 3, 2, 1}

// 方法2：自定义比较器（不常用）
struct Descending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};
set<int, Descending> s2 = {1, 5, 3, 4, 2};

5.3 存储结构体

方法1：重载 < 运算符（推荐）

struct Student {
    int id;
    string name;
    
    // 按 id 升序
    bool operator<(const Student& other) const {
        return id < other.id;
    }
};

set<Student> students;
students.insert({1, "Alice"});
students.insert({3, "Bob"});
students.insert({2, "Charlie"});
// 遍历顺序：1-Alice, 2-Charlie, 3-Bob

按多个字段排序：

struct Node {
    int x, y;
    
    bool operator<(const Node& other) const {
        if (x != other.x) return x < other.x;  // 先按 x
        return y < other.y;                     // x 相同按 y
    }
};

set<Node> s;
s.insert({2, 3});
s.insert({1, 5});
s.insert({2, 1});
// 遍历顺序：{1,5}, {2,1}, {2,3}

方法2：自定义比较器

struct Student {
    int id;
    string name;
};

struct CompareById {
    bool operator()(const Student& a, const Student& b) const {
        return a.id < b.id;
    }
};

set<Student, CompareById> students;

5.4 使用 lambda 作为比较器（C++11）

auto cmp = [](int a, int b) {
    return a > b;  // 降序
};
set<int, decltype(cmp)> s(cmp);
s.insert({1, 5, 3, 4, 2});  // {5, 4, 3, 2, 1}

---

六、pair 在 set 中的应用

6.1 基本用法

set<pair<int, int>> s;

s.insert({1, 2});
s.insert({1, 3});
s.insert({2, 1});

// 默认按 first 升序，first 相同按 second 升序
// 遍历顺序：{1,2}, {1,3}, {2,1}

6.2 二分查找在 pair 上的应用（不常用）

set<pair<int, int>> s = {{1, 2}, {1, 5}, {2, 3}, {3, 1}};

// 找第一个 first >= 2 的
auto it = s.lower_bound({2, -1000000});
// 指向 {2, 3}

// 找第一个 first > 1 的
auto it2 = s.upper_bound({1, 1000000});
// 指向 {2, 3}

---

七、set 和 其他容器

特性	set	unordered_set	vector
有序	自动排序	无序	按插入顺序
元素唯一	自动去重		允许重复
查找速度	O(log n)	O(1) 平均	O(n)
插入速度			O(1) 末尾
支持 lower_bound	可以	不行	不行（需排序）
迭代器稳定性	稳定	重哈希时失效	扩容时失效

选择建议：

• 需要有序、范围查询 → 用 set
• 只需要快速查找、不关心顺序 → 用 unordered_set
• 只需要存储、按顺序访问 → 用 vector

---

八、复杂度总结

操作	时间复杂度	说明
插入	O(log n)	红黑树查找位置 + 插入
删除（按值）		查找 + 删除
删除（按迭代器）	均摊 O(1)	直接删除
查找（find/count）	O(log n)	树搜索
lower_bound
upper_bound
begin/rbegin	O(1)	直接取最值
遍历	O(n)	中序遍历
size/empty	O(1)	-

n 能扛多大？ 10^6 完全没问题，log2(10^6) ≈ 20 次比较。

---

九、迭代器失效规则（了解即可）

操作	哪些迭代器失效
插入元素	所有迭代器不失效 ?
删除元素	只有被删除的元素的迭代器失效
clear	所有迭代器失效
swap	迭代器指向的元素还在，但容器交换了

安全删除写法：

set<int> s = {1, 2, 3, 4, 5};

// 错误写法
for (auto it = s.begin(); it != s.end(); ++it) {
    if (*it == 3) s.erase(it);  // ? it 失效了，再 ++it 会出错
}

// 正确写法
for (auto it = s.begin(); it != s.end(); ) {
    if (*it == 3) {
        it = s.erase(it);  // ? erase 返回下一个迭代器
    } else {
        ++it;
    }
}

---

十、常用模板大全

模板1：去重 + 排序（最基础）

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

int main() {
    int n, x;
    set<int> s;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        s.insert(x);  // 自动去重 + 排序
    }
    
    // 输出去重后的有序序列
    for (int val : s) {
        cout << val << " ";
    }
    
    return 0;
}

模板2：动态查找前驱和后继

set<int> s = {1, 3, 5, 7, 9};

int x;
cin >> x;

// 找小于 x 的最大值（前驱）
auto pre = s.lower_bound(x);
if (pre != s.begin()) {
    --pre;
    cout << "前驱：" << *pre << endl;
}

// 找大于 x 的最小值（后继）
auto nxt = s.upper_bound(x);
if (nxt != s.end()) {
    cout << "后继：" << *nxt << endl;
}

模板3：动态维护中位数

set<int> s;
s.insert(1);
s.insert(5);
s.insert(3);
s.insert(2);
s.insert(4);

int n = s.size();
auto it = s.begin();
advance(it, n / 2);  // 将迭代器向前移动 n/2 步
cout << "中位数：" << *it << endl;

模板4：结构体 set 完整示例

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

struct Student {
    int id;
    string name;
    int score;
    
    // 按分数降序，分数相同按 id 升序
    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;
        return id < other.id;
    }
};

int main() {
    set<Student> students;
    
    students.insert({1, "Alice", 95});
    students.insert({2, "Bob", 87});
    students.insert({3, "Charlie", 95});
    students.insert({4, "David", 92});
    
    // 自动按分数降序输出
    for (const auto& stu : students) {
        cout << stu.id << " " << stu.name << " " << stu.score << endl;
    }
    /*
    输出：
    1 Alice 95
    3 Charlie 95
    4 David 92
    2 Bob 87
    */
    
    return 0;
}

模板5：区间查询（统计 [L, R] 内的元素个数）

set<int> s = {1, 3, 5, 7, 9, 11, 13};

int L = 3, R = 10;

// 统计 [L, R] 内的元素个数
auto itL = s.lower_bound(L);
auto itR = s.upper_bound(R);
int cnt = distance(itL, itR);

cout << "在 [" << L << ", " << R << "] 内的元素有 " << cnt << " 个" << endl;
// 输出：4（元素 3, 5, 7, 9）

模板6：完整竞赛模板（背下来直接套）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    set<int> s;
    int n, op, x;
    
    cin >> n;
    while (n--) {
        cin >> op >> x;
        
        switch (op) {
            case 1:  // 插入
                s.insert(x);
                break;
                
            case 2:  // 删除
                s.erase(x);
                break;
                
            case 3:  // 查询是否存在
                cout << (s.count(x) ? "YES" : "NO") << endl;
                break;
                
            case 4:  // 查询第一个 >= x 的数
                auto it = s.lower_bound(x);
                if (it != s.end()) cout << *it << endl;
                else cout << "-1" << endl;
                break;
                
            case 5:  // 查询第一个 > x 的数
                auto it = s.upper_bound(x);
                if (it != s.end()) cout << *it << endl;
                else cout << "-1" << endl;
                break;
        }
    }
    
    return 0;
}

---

十一、常见陷阱与避坑指南

陷阱1：试图修改 set 中的元素

set<int> s = {1, 2, 3};
auto it = s.begin();
*it = 10;  // ? 编译错误！迭代器是 const 的

解决方法：删除旧值，插入新值。

int old_val = *it;
s.erase(it);
s.insert(10);

陷阱2：自定义比较器只比较部分字段

struct Student {
    int id;
    string name;
};

struct Cmp {
    bool operator()(const Student& a, const Student& b) const {
        return a.id < b.id;  // 只比较 id
    }
};

set<Student, Cmp> s;
s.insert({1, "Alice"});
s.insert({1, "Bob"});  // ? 插入失败！id 相同视为相等

记住：set 的"相等"由比较器定义。如果 !comp(a,b) && !comp(b,a)，则认为 a 和 b 相等。

陷阱3：迭代器失效后继续使用

auto it = s.find(3);
s.erase(it);      // 删除后 it 失效
cout << *it;      // ? 未定义行为！

正确做法：

auto it = s.find(3);
it = s.erase(it);  // ? erase 返回下一个迭代器
cout << *it;       // 安全

---

十二、记忆口诀

set 自动去重排序好，红黑树保证 log n 效率高。

insert 增，erase 删，find count 来查找。

begin 最小 rbegin 最大，lower_bound 找下界 upper_bound 找上界。

迭代器只读不能改，删除只失效被删那个。

结构体用 set 重载小于号，记住规则错误少。

---

十三、快速参考表

最常用操作（背下来）

操作	代码
定义	set<int> s;
插入	s.insert(x);
删除	s.erase(x);
查找	s.find(x);
判断存在	s.count(x);
大小	s.size();
判空	s.empty();
清空	s.clear();
最小值	*s.begin();
最大值	*s.rbegin();
下界	s.lower_bound(x);
上界	s.upper_bound(x);

完整代码示例

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

int main() {
    // 定义
    set<int> s;
    
    // 插入
    s.insert(3);
    s.insert(1);
    s.insert(5);
    s.insert(3);  // 插入失败（已存在）
    
    // 查找
    if (s.count(3)) cout << "3 存在" << endl;
    
    // 删除
    s.erase(3);
    
    // 遍历（自动升序）
    for (int x : s) {
        cout << x << " ";
    }
    cout << endl;  // 输出：1 5
    
    // lower_bound
    auto it = s.lower_bound(2);  // 第一个 >=2 的，指向 5
    if (it != s.end()) {
        cout << "第一个 >=2 的是：" << *it << endl;
    }
    
    return 0;
}

---

完结！