C++中的set是标准库提供的关联式容器，核心特性是自动去重和排序，这两个特性都和其底层实现紧密相关。set中的元素是唯一的，插入重复值不会生效，同时所有元素会按照指定的规则自动排好序，默认是升序排列。
set基本用法
头文件引入与声明
使用set需要先引入头文件<set>，声明set对象的语法如下：
#include <set> #include <iostream> using namespace std; // 声明一个存储int类型元素的set，默认升序 set<int> intSet; // 声明一个存储string类型元素的set，默认按字典序升序 set<string> strSet;
常用操作
set的常用操作包括插入、删除、查找、遍历等，下面是具体的代码示例：
#include <set>
#include <iostream>
using namespace std;
int main() {
set<int> s;
// 插入元素，重复元素会被自动忽略
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(2); // 重复插入，不会生效
s.insert(5);
// 遍历set，输出结果会是1 2 3 5，自动排序
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
cout << endl; // 输出换行
// 查找元素，find返回迭代器，找不到返回end()
auto findIt = s.find(3);
if (findIt != s.end()) {
cout << "找到元素3" << endl;
}
// 删除元素
s.erase(2); // 按值删除
// 也可以按迭代器删除
// auto delIt = s.find(5);
// if (delIt != s.end()) s.erase(delIt);
// 查看set大小
cout << "当前set大小：" << s.size() << endl;
// 判断是否为空
cout << "set是否为空：" << (s.empty() ? "是" : "否") << endl;
return 0;
}
自定义排序规则
set默认使用<运算符排序，如果需要自定义排序规则，可以在声明时传入比较函数或者函数对象，比如实现降序排序：
#include <set>
#include <iostream>
using namespace std;
// 自定义降序比较函数
struct CompareDesc {
bool operator()(int a, int b) const {
return a > b; // 大的元素排在前面
}
};
int main() {
set<int, CompareDesc> descSet;
descSet.insert(3);
descSet.insert(1);
descSet.insert(2);
// 遍历输出，结果是3 2 1
for (int num : descSet) {
cout << num << " ";
}
cout << endl;
return 0;
}
set底层原理
set的底层实现是红黑树，这是一种自平衡的二叉搜索树，具有以下特性：
- 每个节点要么是红色，要么是黑色
- 根节点是黑色
- 所有叶子节点（空节点）是黑色
- 如果一个节点是红色，那么它的两个子节点都是黑色
- 从任意一个节点到其所有后代叶子节点的路径上，包含相同数量的黑色节点
这些特性保证了红黑树的高度始终保持在O(log n)级别，因此set的插入、删除、查找操作的时间复杂度都是O(log n)。
去重原理
红黑树本身是二叉搜索树，存储元素时会按照比较规则判断元素是否已经存在。当插入一个新元素时，set会先从根节点开始遍历红黑树，通过自定义的比较规则（默认是<）判断当前元素和待插入元素的大小关系：
- 如果当前元素等于待插入元素，说明元素已存在，插入操作直接终止，不会新增节点，这就是set去重的底层逻辑
- 如果待插入元素更小，就往左子树遍历，否则往右子树遍历，直到找到合适的插入位置
排序原理
红黑树作为二叉搜索树，本身就有左子树节点值小于根节点、右子树节点值大于根节点的特性。当我们对set进行中序遍历时，会按照从小到大的顺序访问所有节点，因此set的元素天然就是有序的。如果自定义了比较规则，那么排序顺序也会按照自定义规则来，本质还是比较规则决定了元素在红黑树中的位置。
红黑树平衡调整
插入或者删除节点后，红黑树的平衡可能被破坏，此时会通过旋转（左旋、右旋）和节点颜色调整来重新满足红黑树的特性，保证树的高度不会过高，从而维持操作的时间复杂度稳定。这部分调整是底层自动完成的，使用者不需要手动干预。
使用注意事项
使用set时需要注意几个问题：
- set中的元素是常量，不能通过迭代器修改元素的值，否则会破坏红黑树的有序性，如果需要修改只能先删除旧元素再插入新元素
- set的插入、删除、查找效率都是O(log n)，如果需要更快的查找效率且不需要排序，可以考虑unordered_set，其底层是哈希表，平均查找复杂度是O(1)
- 自定义排序规则时，比较函数必须满足严格弱序，否则会导致未定义行为，比如不能写成<=，必须是严格的小于关系