C++ set

我们在数学课上都学过 “集合”，数学集合有一个很明显的特点：里面的元素不能重复。在编写程序时，如果我们只关心 “某个值存不存在、能不能自动去掉重复数据”，而不关心元素排在第几个下标位置，就可以使用 C++ 标准库提供的 std::set。

对于 std::set 来说，它最重要的特点只有两个词：唯一、有序。放进 set 里的元素不会出现重复，而且容器内部会默认按照从小到大的规则自动排好序。你只管把数据往里放，至于 “有没有重复”、“应该排在哪个位置”，set 都会自动处理好。

C++ set 的创建与遍历

在 C++ 中，std::set 是定义在 <set> 头文件中的有序关联容器，用来保存类型相同且彼此唯一的一组元素。

语法：

#include <set>

std::set<元素类型> 变量名 = {元素1, 元素2, ...};

说明：

创建 std::set 时，我们可以直接使用花括号给出初始元素，不写初始值则会创建一个空集合。哪怕花括号里写了重复的值，或者顺序是乱的，set 在创建时也会自动去重并排好序。std::set 常用的成员函数如下表所示。

示例 1：创建并遍历 set

#include <iostream>
#include <set>

int main() {
    // 放入乱序与重复元素
    std::set<int> nums = {30, 10, 20, 10, 30};

    std::cout << nums.size() << '\n';
    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

3
10 20 30

分析：

从运行结果可以看出，虽然初始化 nums 时写了 5 个整数，其中 10 和 30 各出现了两次且顺序是乱的，但 nums.size() 输出的结果是 3，说明重复项已被自动去掉。同时遍历输出的结果是 10 20 30，说明 std::set 默认按从小到大的顺序把它们排整齐了。

这里小伙伴们要注意，std::set 中元素的位置由大小比较规则决定，不支持像 std::vector 那样使用 [] 下标访问，也没有 push_back() 函数。如果平时只需要去重、不需要按大小排序，也可以选用无序集合 std::unordered_set。

向 set 中插入元素：insert()

既然 std::set 没有头部和尾部追加的概念，后续想往集合里添加新元素时，我们统一调用 insert() 成员函数即可。

语法：

集合名.insert(元素);

说明：

调用 s.insert(x) 时，如果元素 x 在集合里还不存在，就会插入进去并自动排到合适的位置。如果这个值已经存在了，set 就会直接忽略这次操作，不会保存重复的值。

示例 2：插入新元素与重复元素

#include <iostream>
#include <set>

int main() {
    std::set<int> nums = {10, 30};

    nums.insert(20);    // 插入新元素 20
    nums.insert(10);    // 插入已存在的元素 10

    std::cout << nums.size() << '\n';
    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

3
10 20 30

分析：

nums.insert(20); 这句代码表示把 20 放进集合中，它会自动排到 10 和 30 中间。接着执行 nums.insert(10); 时，因为 10 原本就已经在集合里了，这次插入会被自动忽略，所以 nums.size() 依然是 3。

查找与删除 set 中的元素

std::set 最主要的用途之一，就是快速判断 “某个值在不在集合里”，以及定位或删除指定的元素。

语法：

集合名.contains(要查找的值);
auto pos = 集合名.find(要查找的值);
集合名.erase(要删除的值);

说明：

在查找和删除元素时，我们可以按这 3 个成员函数的分工来选择：

• contains()：判断目标值是否存在，找到返回 true，找不到返回 false。如果只是想判断某个值在不在集合里，放进 if 条件中最直观。
• find()：查找目标元素所在的位置，返回一个只读迭代器 pos。如果找到了，可以像指针那样通过 *pos 取出它的值。如果找遍整个集合都没找到，则会返回代表末尾边界的 s.end()。
• erase()：既可以直接传入元素值 s.erase(x) 按值删除，也可以传入前面查找到的迭代器 s.erase(pos) 按位置删除。

示例 3：查找与删除元素

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> langs = {"C++", "Go", "Python"};

    if (langs.contains("Python")) {
        std::cout << "包含 Python\n";
    }

    auto pos = langs.find("Go");
    if (pos != langs.end()) {
        std::cout << "即将删除：" << *pos << '\n';
        langs.erase(pos);    // 按已找到的位置删除
    }

    for (const std::string& lang : langs) {
        std::cout << lang << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

包含 Python
即将删除：Go
C++ Python

分析：

在这个例子中，langs.contains("Python") 直接返回 true，说明 "Python" 在集合中。接着调用 langs.find("Go") 查找元素位置，并将返回的迭代器保存在 pos 中。

因为没找到目标时 find() 会返回末尾边界 end()，所以条件 pos != langs.end() 成立就代表查找成功。随后我们先通过 *pos 取出元素值打印出来，再把 pos 直接传给 langs.erase(pos) 完成删除，省去了让容器再去查找第二遍的开销。

如果在删除前不需要做额外读取或提示，只是单纯想把集合里的 "Go" 删掉，直接按值调用 erase() 会更简短。对于删除操作来说，下面 2 种方式都能把 "Go" 移除：

// 方式 1（推荐）
langs.erase("Go");

// 方式 2
auto pos = langs.find("Go");
if (pos != langs.end()) {
    langs.erase(pos);
}

其中，方式 1 直接传入要删除的值：如果 "Go" 存在就会被删掉，如果原本就不存在则什么都不会发生，也不会报错。单纯删除某个元素时，在实际开发中我们更推荐使用方式 1。

修改 set 中的元素

在 std::set 中，所有的元素都是只读的。为什么不允许直接修改元素的值呢？原因其实很好理解：set 是靠元素本身的值来决定谁排在前面、谁排在后面的。如果在 {10, 20, 30} 中允许直接把中间的 20 改成 99，那序列就会变成 {10, 99, 30}，整个容器从小到大的排序结构就被破坏了。

因此，即使通过 find() 拿到了指向某个元素的迭代器 pos，它也是只读的。如果尝试像下面这样原地修改它的值，编译时就会直接报错：

auto pos = nums.find(20);
*pos = 50;    // 不能直接修改元素值

当我们需要把 set 中的某个旧值替换成新值时，只需要分两步处理就可以了：先调用 erase() 删掉旧值，再调用 insert() 插入新值。请看下面例子。

示例 4：替换 set 中的元素

#include <iostream>
#include <set>

int main() {
    std::set<int> nums = {10, 20, 30};

    nums.erase(20);     // 先删除旧值 20
    nums.insert(50);    // 再插入新值 50

    for (int n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

10 30 50

分析：

先执行 nums.erase(20); 再执行 nums.insert(50);，不仅把原来的 20 替换成了 50，而且 std::set 在插入 50 时还会自动重新排好位置，把它放到 30 后面，确保整个集合依然保持从小到大的有序状态。