C / C++ / 系统课时

用 set 保存不重复的数据

用 set 保存不重复的数据

当程序只关心“某个值是否出现过”,并希望重复数据自动被拒绝时,std::set 是直接的选择。它保存唯一键,并按照比较规则保持有序。本节通过插入、查找和删除,掌握最常用的 set 操作及重复插入时的实际行为。

学习目标

  • 使用 insert、find 和 erase 管理 set 中的数据
  • 理解重复值为什么不会产生第二份元素
  • 理解 set 的有序性以及键不可直接修改的原因

set 同时保证唯一和有序

std::set<T> 保存的是键本身,不像 map 那样还有单独的映射值。默认情况下,它使用 std::less<T> 比较元素,因此遍历结果会按照升序排列。

更重要的是,set 不允许存在两个在比较规则下等价的键。再次插入已经存在的值不会覆盖原元素,也不会再增加一份副本,而是报告插入失败。

下面用一个标签集合完整演示插入、查找和删除:

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

int main() {
    std::set<std::string> tags;

    auto [it1, inserted1] = tags.insert("cpp");
    auto [it2, inserted2] = tags.insert("stl");
    auto [it3, inserted3] = tags.insert("cpp");

    std::cout << "insert cpp: " << (inserted1 ? "success" : "duplicate") << '\n';
    std::cout << "insert stl: " << (inserted2 ? "success" : "duplicate") << '\n';
    std::cout << "insert cpp again: " << (inserted3 ? "success" : "duplicate") << '\n';
    std::cout << "size: " << tags.size() << '\n';

    // find 返回指向元素的迭代器;找不到时返回 end()。
    std::cout << "find stl: "
              << (tags.find("stl") != tags.end() ? "yes" : "no") << '\n';

    // 对 set 按键删除时,返回实际删除的元素数量,只可能是 0 或 1。
    std::cout << "erase cpp: " << tags.erase("cpp") << '\n';

    std::cout << "remaining:";
    for (const auto& tag : tags) {
        std::cout << ' ' << tag;
    }
    std::cout << '\n';
}

预期输出:

text
insert cpp: success
insert stl: success
insert cpp again: duplicate
size: 2
find stl: yes
erase cpp: 1
remaining: stl

第三次调用 insert("cpp") 时,集合中已经有相同键,所以 size() 仍然是 2。这里使用的结构化绑定需要 C++17 或更高版本。

insert 怎样报告重复

对单个元素调用 set::insert 时,返回值包含两部分:一个迭代器和一个布尔值。迭代器指向集合中对应的元素,布尔值表示这次是否真正插入了新元素。

第一次插入 cpp 时,布尔值为 true;再次插入时为 false,但返回的迭代器仍然指向集合中已有的那个 cpp。因此,程序不需要先调用 find 再决定是否插入,直接检查 insert 的返回值即可避免一次重复查找。

查找与删除都按键进行

find(value) 用于判断某个键是否存在。找到时返回对应迭代器,找不到时返回 end()。这种接口适合需要继续访问该元素的场景。

删除时可以直接调用 erase(value)。对于 set,一个键最多只有一份,所以按键删除的返回值只会是 0 或 1:0 表示原本不存在,1 表示成功删除了一项。若手中已经有迭代器,也可以通过迭代器删除,避免再次按键查找。

常见操作的平均语义可以概括为:

操作 作用 典型时间复杂度
insert(value) 插入不存在的键 O(log⁡n)O(\log n)
find(value) 查找键 O(log⁡n)O(\log n)
erase(value) 按键删除 O(log⁡n)O(\log n)

这些复杂度来自 std::set 通常采用平衡搜索树实现,但 C++ 标准规定的是行为与复杂度要求,而不是要求某一种具体树结构。

为什么不能直接修改 set 中的值

set 的有序结构依赖每个元素的键值。如果一个元素已经放在某个有序位置后还能被任意改成另一个值,容器内部顺序就可能失效。因此,通过 set 的迭代器取得元素后,不能像修改普通容器元素那样直接改变它的键。

需要把 old 改成 new 时,通常应删除旧值,再插入新值。若程序需要为每个唯一键附带一个可以频繁修改的额外值,则更适合使用 std::map。

set 最适合表达“唯一值集合”:例如保存已经处理过的任务 ID、去重后的标签、允许访问的用户名或需要自动排序的编号。若只需要去重和快速成员判断、完全不关心顺序,也可以进一步考虑 std::unordered_set;但需要稳定的有序遍历或对数复杂度保证时,set 更直接。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 set 保存不重复的数据

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通