C++ set怎么去重 C++集合容器自动排序去重原理【数据结构】

set插入自动去重依赖红黑树的二分查找与等价判断（非相等），要求比较函数满足严格弱序；若自定义类型仅重载operator==而未提供operator

set 插入时自动去重靠的是 std::less 和等价判断

不是靠“查重后再插入”，而是靠红黑树的插入逻辑：每次插入先按排序规则（默认 std::less）做二分查找，若已存在「等价」元素（即既不小于也不大于），就直接丢弃。这里的关键是「等价」≠「相等」——对 int 没区别，但自定义类型若只重载了 operator== 却没适配比较函数，set 仍会插入“看似重复”的元素。

常见错误现象：set 插入两个字段完全相同的对象，结果 size 变成 2。原因往往是只写了 operator==，却没提供 operator 或自定义 Compare 函数对象。

• 必须确保比较函数满足严格弱序（strict weak ordering）：反身性、反对称性、传递性、不可比性的传递性
• 不要用 return a.x == b.x && a.y == b.y 当 operator —— 这不满足严格弱序
• 推荐写法：return std::tie(a.x, a.y)

为什么 set 不用哈希而用红黑树实现

因为 set 的核心契约是「有序 + 去重」，不是「快查」。红黑树天然支持 O(log n) 插入/删除/查找，且中序遍历即升序；而哈希表（如 unordered_set）虽平均 O(1)，但不保证顺序，也无法直接支持 lower_bound、upper_bound 等范围操作。

性能影响明显：如果你只需要去重、不关心顺序，unordered_set 更快；但一旦需要迭代有序、或频繁调用 lower_bound 查找前驱后继，set 是唯一合理选择。

立即学习“C++免费学习笔记（深入）”；

• set 迭代器是双向迭代器，可 ++/–；unordered_set 是前向迭代器，只能 ++
• set::find 返回指向有序位置的迭代器；unordered_set::find 返回任意位置的迭代器
• 内存占用：红黑树每个节点带颜色和指针，比哈希桶略高，但更稳定（无哈希冲突扩容抖动）

手动触发去重？没必要，但要注意 insert 返回值

set::insert 返回 std::pair，其中 bool 表示是否成功插入（true = 新元素，false = 已存在）。这不是“手动去重”，而是标准协议的一部分，用于判断是否发生实际变更。

容易踩的坑：有人误用 set::emplace_hint 并传错 hint，导致性能退化甚至逻辑错误；还有人把 set 当作临时去重容器，反复构造再清空，其实不如直接用 std::vector + std::sort + std::unique（尤其数据量小或只去重一次时）。

• 大批量插入建议用范围构造：set s(v.begin(), v.end());，比循环 insert 快（内部优化为批量建树）
• 若只是临时去重并转回 vector，且不需要中间有序，unordered_set + vector 构造更快
• 别对 set 调用 std::unique —— 它要求相邻重复，而 set 根本不会存重复

自定义类型去重失败的典型调试路径

当 set 明明该去重却没去，优先检查三件事：

• 确认 MyClass 的比较函数是否被正确使用：在 set 模板参数里显式传入，或确保 operator 是 public 且非模板
• 打印插入前后 s.size() 和遍历输出，验证是否真没去重，还是你误判了“相同”逻辑（比如浮点数直接比较）
• 用 std::is_sorted(s.begin(), s.end(), comp) 检查是否真有序——如果返回 false，说明比较函数违反严格弱序，这是根本原因

最隐蔽的问题：比较函数里用了未初始化成员、或依赖外部状态（如全局变量），导致行为不稳定。这种 bug 往往只在特定编译器或优化等级下暴露。