c++中如何使用set集合去重_c++ set容器用法

std::set能自动去重因其底层为红黑树，插入时按Compare规则判定等价元素，相同键只保留一个，与允许重复的std::multiset本质不同。

为什么 std::set 能自动去重

std::set 底层是红黑树（平衡二叉搜索树），插入时会按严格弱序比较元素，相同元素视为“等价”，只保留一个。它不接受重复键——这和 std::multiset 有本质区别。

注意：std::set 的“相同”由 Compare 模板参数决定，默认是 std::less，即用 比较。如果两个对象 a 和 b 满足 !(a ，就认为它们相等，后者不会插入。

• 自定义类型必须提供可比较的 operator 或传入自定义比较函数
• 不能用 == 判断是否重复——set 根本不调用 operator==
• 去重发生在 insert()、emplace() 等插入操作时，不是构造后扫描清理

基本去重写法：插入即过滤

最常用方式就是遍历原始数据，逐个 insert() 到 std::set 中。重复元素会被静默忽略，返回值还能告诉你是否真插入了。

std::vector nums = {1, 2, 2, 3, 3, 4}; std::set unique_set; for (int x : nums) {     unique_set.insert(x); // 重复的 2、3 只存一份 } // unique_set 现在是 {1, 2, 3, 4}

• insert() 返回 std::pair，.second 为 true 表示新插入
• 若需统计去重数量或跳过重复逻辑，可用 if (unique_set.insert(x).second) { ... }
• 想保留原始顺序？set 不行——它按排序顺序存；改用 std::unordered_set + std::vector 记录顺序

处理自定义结构体：必须定义比较逻辑

比如有个 Person 类，按 id 去重，但没定义 operator 就直接塞进 set，编译直接报错：

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

error: no match for 'operator

正确做法是让类型可比较。推荐在类内定义 operator（仅当自然序有意义时）：

struct Person {     int id;     std::string name;     bool operator<(const Person& other) const {         return id < other.id; // 仅靠 id 判断大小/唯一性     } };

然后就能用了：

std::set people; people.insert({1, "Alice"}); people.insert({1, "Bob"}); // 插入失败：id 相同，视为重复

• 不要用 memcmp 或指针地址比较——行为未定义
• 若需多字段联合去重（如 id+name），operator 必须实现字典序，例如先比 id，相等再比 name
• 不想改结构体？用外部比较器：std::set s(cmp)，其中 cmp 是 lambda 或函数对象

性能与替代方案：别为了去重硬套 set

std::set 插入是 O(log n)，整体去重是 O(n log n)，且内存开销比 std::vector 大得多。如果你只想要去重结果、不关心顺序、也不需要后续查找，更高效的做法是：

• 先用 std::sort + std::unique（原地去重，O(n log n) 时间，O(1) 额外空间）
• 或者用 std::unordered_set：平均 O(1) 插入，去重更快，但不排序、无序
• std::set 真正优势在于：需要**有序集合 + 动态增删 + 自动去重**三者同时满足，比如实时维护一个去重后的排行榜

重复元素多、数据量大时，unordered_set 通常比 set 快 2–5 倍；但要注意哈希冲突和自定义类型的 hash 实现——这点比 set 的比较逻辑更容易出错。