c++ set容器用法 c++ set去重原理详解

尼克 2025-11-30 00:00:00 次阅读

set能自动去重并保持有序，其底层通常采用红黑树实现；插入时通过比较操作查找位置，若元素已存在（即互不小于对方）则插入失败，从而保证唯一性；支持自定义类型需提供比较规则，适用于需要有序且唯一数据的场景。

在C++中，set 是一个非常实用的关联式容器，常用于自动去重和保持元素有序。它属于STL（标准模板库）的一部分，定义在头文件中。

set的基本用法

set 容器内部存储唯一且按升序排列的元素。默认情况下，使用 operator 进行比较，因此元素必须支持比较操作。

常见操作示例：

插入元素：使用 insert() 方法，重复插入相同值不会生效。
删除元素：使用 erase()，可传值或迭代器。
查找元素：使用 find()，返回迭代器，未找到则返回 end()。
判断是否为空：empty()。
获取大小：size()。

代码示例：

#include 
#include 

int main() {
    std::set s;
    s.insert(5);
    s.insert(3);
    s.insert(5); // 重复，插入无效

    for (const auto& x : s) {
        std::cout << x << " "; // 输出：3 5
    }

    if (s.find(3) != s.end()) {
        std::cout << "\n3 存在";
    }

    return 0;
}

set去重的原理

set 能自动去重，根本原因在于其底层数据结构——通常实现为自平衡二叉搜索树（如红黑树）。

当调用 insert 插入元素时，set 会：

从根节点开始，按照比较规则（默认小于）查找插入位置。
如果发现已有相同值的节点（即 !a
此时插入失败，不修改容器，返回已存在节点的迭代器。

由于 set 要求元素“严格弱排序”，而“相等”被定义为：
两个元素 a 和 b 相等，当且仅当 a 且 b 。
这与 == 不同，但能保证唯一性。

自定义类型如何使用set

若要将自定义类型放入 set，必须提供比较方式。

可以通过重载 操作符，或传入比较函数对象。

示例：使用 struct 自定义比较

struct Person {
    int age;
    std::string name;
    
    bool operator<(const Person& other) const {
        return age < other.age; // 按年龄排序，自动去重
    }
};

std::set people;
people.insert({25, "Alice"});
people.insert({25, "Bob"}); // 若只比 age，则视为重复

注意：上述例子中，两个 age=25 的 Person 可能被视为相同。若需更精确去重，应在比较逻辑中加入 name 或其他字段。