目录

什么是 std::set？

🧩 底层逻辑 

红黑树简介（set 的核心）

set 的数据如何存储在红黑树中？

 结构图

为什么选择红黑树？

核心特性

为什么 set 不支持随机访问？

set 中元素能不能修改？

🌲 基本用法 

 创建 + 插入 + 输出

 插入 + 查找 + 删除

遍历 set（正序 & 反序）

自定义排序

🧰 常用成员函数

典型应用场景

---

什么是 std::set？

📘 定义：

std::set 是 C++ 标准模板库中的一种 关联容器（Associative Container），用于存储、自动排序并唯一化数据。

它的底层实现是红黑树（self-balancing binary search tree）。

🧩 底层逻辑 

红黑树简介（set 的核心）

🔧 红黑树是一种特殊的二叉搜索树（BST），满足这些规则：

1. 每个节点不是“红色”就是“黑色”

2. 根节点是黑色

3. 所有叶子节点（nullptr）是黑色

4. 红色节点的子节点必须是黑色

5. 从任一节点到其所有叶子节点的路径中，黑色节点数相同（黑高平衡）

通过这些规则，红黑树保持平衡，避免出现像链表那样的“最坏情况” 

set 的数据如何存储在红黑树中？

你可以这样想象：

插入一组数字：4, 2, 6, 1, 3, 5, 7

形成的树结构：

        [4]
       /   \
    [2]     [6]
   /  \     / \
 [1] [3] [5] [7]

• 所有元素按从小到大排列

• 每次插入，红黑树会通过 旋转 + 颜色变换 来保证树是平衡的

• 所以插入顺序并不影响最终的遍历顺序！

 结构图

插入顺序：      3 → 1 → 4 → 2
set 结构：      [1] ← [2] ← [3] ← [4]
                （自动排序）

• 插入后会自动排序

• 重复插入会被忽略

为什么选择红黑树？

属性	红黑树	AVL
平衡性	相对弱一点	更强
插入/删除效率	更快	更慢
查找效率	稍慢一点	更快
旋转次数	较少	多
STL 应用适配性	非常好	稍差

结论：红黑树是性能和复杂度的权衡选择，适合大量查找 + 插入 + 删除操作，所以 std::set 和 std::map 都选它。

核心特性

特性	说明
元素唯一	自动去重，不能插入重复元素
自动排序	元素按小到大（默认 <）排序
查找高效	插入/查找/删除时间复杂度 O(log n)
元素只存 key	没有 key-value 对（不像 map）

为什么 set 不支持随机访问？

不像 vector 可以通过下标访问元素：vec[5]，set 不支持这种访问方式，因为：

• set 元素存在红黑树中，是通过“结构”组织的，不是数组形式

• 你不知道第 5 个元素到底在树的哪里，必须靠 中序遍历 才能“线性”看到顺序

set 中元素能不能修改？

不能直接修改！必须先删后插。

为什么？因为：

• 修改元素后，它可能不再符合红黑树的排序要求

• 比如你把节点值从 10 改成 1，就破坏了树的结构

• 所以 STL 规定：set 中的元素是 const 的

---

 

🌲 基本用法 

引入头文件

#include <set>

 创建 + 插入 + 输出

#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(2);
    s.insert(3);  // 重复，不会插入

    for (int x : s) {
        std::cout << x << " ";
    }
}

插入操作背后的动作（insert）

例如：插入 5

1. 用 BST 的方式找到插入位置（O(log n)）

2. 插入为“红色节点”

3. 若违反红黑树规则，进行 旋转 或 颜色调整

4. 最多只需要几次操作，树就恢复平衡！

 插入时的结果检查

auto result = s.insert(42);
if (result.second == false) {
    std::cout << "42 already exists!\n";
}

• insert() 返回一个 pair<iterator, bool>

• bool 表示是否插入成功

• 你可以用这个检查去重逻辑

 插入 + 查找 + 删除

std::set<std::string> names;

names.insert("Tom");
names.insert("Alice");

if (names.count("Tom")) {
    std::cout << "Tom is here.\n";
}

names.erase("Alice");  // 删除 Alice

查找操作（find） 

红黑树利用二叉搜索特性：

• 如果 x < 当前节点：向左找

• 如果 x > 当前节点：向右找

• 如果 x == 当前节点：找到！

时间复杂度：O(log n)，和 BST 相同，但更稳定

遍历 set（正序 & 反序）

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

for (int x : s)  // 正序
    std::cout << x << " ";

for (auto it = s.rbegin(); it != s.rend(); ++it)  // 反序
    std::cout << *it << " ";

自定义排序

默认是从小到大排序。如果你想从大到小，可以使用比较器：

std::set<int, std::greater<int>> s;

也可以写自己的比较函数（用于排序对象类型）。 

---

 

🧰 常用成员函数

函数	功能说明
insert(val)	插入元素（自动排序 + 去重）
find(val)	查找是否存在某元素，返回迭代器
count(val)	返回是否存在（0 或 1）
erase(val)	删除指定元素
clear()	清空 set
size()	元素个数
empty()	是否为空
begin(), end()	迭代器遍历支持

典型应用场景

场景	说明
数据去重	插入 set 自动去掉重复元素
有序输出	自动从小到大输出
实现集合交集、并集	配合 set_intersection() 等算法
高频查找	O(log n) 查找，比 vector 快