C / C++ / 系统课时
用 set 保存不重复的数据
用 set 保存不重复的数据
当程序只关心“某个值是否出现过”,并希望重复数据自动被拒绝时,std::set 是直接的选择。它保存唯一键,并按照比较规则保持有序。本节通过插入、查找和删除,掌握最常用的 set 操作及重复插入时的实际行为。
学习目标
- 使用
insert、find和erase管理set中的数据 - 理解重复值为什么不会产生第二份元素
- 理解
set的有序性以及键不可直接修改的原因
set 同时保证唯一和有序
std::set<T> 保存的是键本身,不像 map 那样还有单独的映射值。默认情况下,它使用 std::less<T> 比较元素,因此遍历结果会按照升序排列。
更重要的是,set 不允许存在两个在比较规则下等价的键。再次插入已经存在的值不会覆盖原元素,也不会再增加一份副本,而是报告插入失败。
下面用一个标签集合完整演示插入、查找和删除:
#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';
}预期输出:
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) |
插入不存在的键 | |
find(value) |
查找键 | |
erase(value) |
按键删除 |
这些复杂度来自 std::set 通常采用平衡搜索树实现,但 C++ 标准规定的是行为与复杂度要求,而不是要求某一种具体树结构。
为什么不能直接修改 set 中的值
set 的有序结构依赖每个元素的键值。如果一个元素已经放在某个有序位置后还能被任意改成另一个值,容器内部顺序就可能失效。因此,通过 set 的迭代器取得元素后,不能像修改普通容器元素那样直接改变它的键。
需要把 old 改成 new 时,通常应删除旧值,再插入新值。若程序需要为每个唯一键附带一个可以频繁修改的额外值,则更适合使用 std::map。
set 最适合表达“唯一值集合”:例如保存已经处理过的任务 ID、去重后的标签、允许访问的用户名或需要自动排序的编号。若只需要去重和快速成员判断、完全不关心顺序,也可以进一步考虑 std::unordered_set;但需要稳定的有序遍历或对数复杂度保证时,set 更直接。