set通过红黑树实现自动排序与去重，插入、删除、查找时间复杂度为O(log n)，基于比较函数判断唯一性而非等于操作，支持自定义排序规则，适用于需有序无重复数据的场景。
在C++中，set 是一个非常实用的关联容器，位于 #include
set 基本特性
set 的底层通常由红黑树（一种自平衡二叉搜索树）实现，因此具备以下特点：
- 元素自动排序：插入后按升序排列（默认）
- 不允许重复元素：相同值只能存在一份
- 插入、删除、查找的时间复杂度为 O(log n)
- 不支持通过下标访问，需使用迭代器遍历
基本用法示例如下：
#include#include using namespace std; int main() { set s; s.insert(5); s.insert(2); s.insert(8); s.insert(2); // 重复插入无效 for (int x : s) { cout << x << " "; // 输出：2 5 8 } return 0; }
set 去重原理
set 能够去重，关键在于其插入逻辑。每次调用 insert() 时，set 会先通过比较函数查找是否存在相同值的节点。由于底层是二叉搜索树结构，查找过程基于“键值比较”。
立即学习“C++免费学习笔记（深入）”；
对于基本类型（如 int、double），set 使用默认的小于运算符 判断是否相等。两个元素 a 和 b 被认为“相等”，当且仅当：
!(a这意味着只要 a 不小于 b，同时 b 也不小于 a，就视为相同元素，插入失败。这种机制避免了对 == 操作符的依赖，而是基于排序关系判断唯一性。
因此，即使你插入两个“数值相同”的元素，set 也会根据比较规则识别为重复项，从而实现去重。
自定义排序规则
默认情况下，set 按升序排列。若想改变排序方式，比如降序或按自定义逻辑排序，可以通过提供比较函数或仿函数来实现。
以降序为例：
struct greater_cmp {
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
set s;
// 或使用标准库提供的 greater
// set> s;
s.insert(5);
s.insert(2);
s.insert(8);
for (int x : s) {
cout << x << " "; // 输出：8 5 2
}
对于自定义类型（如结构体），必须显式提供比较规则：
struct Person {
string name;
int age;
Person(string n, int a) : name(n), age(a) {}
};
struct cmp_person {
bool operator()(const Person& a, const Person& b) const {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
}
};
set people;
people.insert(Person("Alice", 25));
people.insert(Person("Bob", 20));
people.insert(Person("Charlie", 25)); // 同龄但名字不同，仍可插入
注意：比较函数必须严格定义“严格弱序”（strict weak ordering），否则可能导致未定义行为。返回 true 表示第一个参数应排在第二个之前。
常见操作与技巧
除了 insert，set 还提供多种常用方法：
- find(x)：查找元素，返回迭代器，未找到则返回 end()
- count(x)：返回 0 或 1（因唯一性）
- erase(x)：删除指定值或迭代器指向的元素
- size()：元素个数
- empty()：判断是否为空
利用 find 可以判断某个值是否已存在：
if (s.find(5) != s.end()) {
cout << "5 exists in set" << endl;
}
基本上就这些。掌握 set 的去重机制和自定义排序，能让你在去重+排序的一体化处理中游刃有余。关键是理解它依赖“比较函数”而非“等于判断”来实现唯一性，这也是其强大灵活性的来源。
