17370845950

set是基于红黑树实现的自动排序、去重关联容器，插入/查找/删除均为O(log n)；默认升序，支持greater或lambda自定义降序；insert返回pair指示是否插入成功，去重依赖等价关系而非相等。

在 C++ 中，set 是一个基于红黑树（Red-Black Tree）实现的关联式容器，它天然支持自动排序和元素去重，不需要手动干预。只要把元素插入进去，它就会按升序排列，且重复值只会保留一份。

set 的基本用法和自动排序原理

set 内部使用红黑树组织数据，所有插入、查找、删除操作的时间复杂度都是 O(log n)。红黑树是一种自平衡二叉搜索树，它要求左子树所有节点值小于根，右子树所有节点值大于根——这直接决定了元素插入后自动按升序排列。

• 默认按 比较：比如 set 插入 {5, 2, 8, 2, 1}，最终内容是 {1, 2, 5, 8}
• 插入重复元素时，insert() 返回一个 pair，其中 second 为 false，表示未插入成功
• 不能通过下标访问（如 s[0]），只能用迭代器遍历

如何自定义排序规则（比如降序）

如果想让 set 按降序排列，可以传入自定义比较函数对象（仿函数）或 lambda（C++11 起支持）：

• 用 greater： set> s; → 从大到小
• 用 lambda（需配合 decltype 或写成函数对象）：实际中更常用的是写结构体或用 std::greater
• 自定义类型必须提供可比较的 operator

去重是怎么做到的？和 insert 的返回值有关

set::insert() 的返回类型是 pair，其中 bool 表示是否成功插入。内部逻辑是：先查找是否存在相等元素（用 operator== 等价于 !(a），若已存在，就跳过插入。

• 注意：去重依据是“等价”而非“相等”。对 int 来说效果一样；但对浮点数或自定义类型要小心精度和比较逻辑
• 没有类似 unordered_set 的哈希机制，所以不依赖 hash 和 ==，只依赖严格弱序（strict weak ordering）
• 不能修改已插入元素的值（因为会破坏红黑树结构），如需更新，应先删后插

常见操作示例（代码片段）

以下是最常用的操作写法：

• 声明与初始化：set s = {3, 1, 4, 1, 5}; // 自动变成 {1,3,4,5}
• 插入：s.insert(2); // 成功返回 true
• 查找：if (s.find(4) != s.end()) { /* 存在 */ }
• 遍历：for (int x : s) cout
• 获取大小：s.size() 返回不重复的元素个数