【信奥业余科普】C++ 的奇妙之旅 | 25:自动排序的利器——集合(set)与多重集合(multiset)
上一篇文章我们拆解了 deque 双端队列,并以此告别了“序列容器”的世界。在之前的文章中,无论是 vector、stack、queue 还是 deque,元素都是按照我们 插入的顺序 排列的。如果想要查找某个元素是否存在,在没有排序的情况下,我们只能从头到尾挨个找,时...
上一篇文章我们拆解了 deque 双端队列,并以此告别了“序列容器”的世界。在之前的文章中,无论是 vector、stack、queue 还是 deque,元素都是按照我们 插入的顺序 排列的。如果想要查找某个元素是否存在,在没有排序的情况下,我们只能从头到尾挨个找,时间复杂度是 。
如果我们需要一个容器,能 自动帮我们去重、排序,并且在 极短的时间内(比如 ) 查找到某个元素,该怎么办呢?
这就需要请出我们今天的主角—— 关联容器(Associative Containers) 的敲门砖:set(集合)和 multiset(多重集合)。
往期回顾:
一、 什么是关联容器与集合(set)?
在介绍 STL 中的 set 之前,我们先理解一下什么叫关联容器。
序列容器(如 vector)关注的是元素的位置:你把元素放在第几个位置,它就在第几个位置。
关联容器关注的是元素的值:元素存放在什么位置,是由元素自身的值(通常称为 键 Key)决定的。容器内部会根据元素的值自动把它们组织起来,实现极速的查找。
C++ STL 中的 set 翻译成中文就是集合。它与数学中的“集合”概念完美对应,拥有两个核心特点:
- 去重(Uniqueness):集合中的每个元素都必须是独一无二的,不能出现重复的元素。
- 有序(Ordered):集合中的元素会自动按照从小到大的顺序(升序)排好。
1.1 底层结构:平衡二叉搜索树(红黑树)
为什么 set 既能保持有序,又能在 的时间内完成插入、删除和查找?
这得益于它的底层数据结构——红黑树(Red-Black Tree)。它是一种自平衡的二叉搜索树。
在信奥阶段,我们不需要去深究红黑树复杂的旋转和着色算法。我们只需要直观地理解二叉搜索树(BST)的“查找二分法”:
- 每个节点最多有两个子节点(左子节点和右子节点)。
- 任何一个节点的左子树中所有节点的值,都比当前节点小。
- 任何一个节点的右子树中所有节点的值,都比当前节点大。
用一个示意图来理解:
8 (根节点)
/ \
4 12
/ \ / \
2 6 10 14当我们要在这个树里查找数字 10 时:
- 拿
10和根节点8比较,因为10 > 8,所以往右走,来到12。 - 拿
10和12比较,因为10 < 12,所以往左走,来到10。 - 找到了!
对于拥有 个元素的平衡二叉搜索树,树的高度大约为 。这意味着,无论查找、插入还是删除,我们最多只需要比较 次。
即使容器里有一百万()个元素,查找一个数字也最多只需要比较 20 次左右。比起 vector 挨个遍历的 100 万次比较,性能大幅提升。
二、 set 的基本操作
使用 set 需要引入头文件 <set>。
2.1 创建与初始化
#include <set>
std::set<int> s1; // 创建一个空的 int 集合
std::set<int> s2 = {3, 1, 4, 1, 5, 9}; // 使用初始化列表趣味思考:如果你遍历 s2,输出会是什么?
因为 set 会自动去重加升序排序,重复的 1 会被剔除。所以输出将是:1 3 4 5 9。
2.2 插入元素 (insert)
std::set<int> s;
s.insert(10);
s.insert(20);
s.insert(10); // 再次插入 10,set 发现已经存在了,会默默忽略它
std::cout << "当前大小: " << s.size() << std::endl; // 输出 22.3 删除元素 (erase)
在 set 中删除元素非常方便,可以直接传入要删除的值,也可以传入指向该元素的迭代器:
std::set<int> s = {10, 20, 30};
s.erase(20); // 直接删除值等于 20 的元素
s.erase(50); // 尝试删除不存在的 50,什么也不会发生(erase 返回 0)2.4 查找元素 (find 与 count)
这是 set 最常用的两个成员函数:
find(x):寻找值为x的元素。- 如果找到了,返回指向该元素的迭代器。
- 如果没找到,返回指向集合末尾的
s.end()迭代器。
count(x):统计值为x的元素在集合中出现的次数。- 因为
set中元素是唯一的,所以返回值只可能是0(不存在)或1(存在)。这在代码中经常被用来当作“判断是否存在”的快捷写法。
- 因为
std::set<int> s = {10, 20, 30};
// 方法一:用 find 查找
auto it = s.find(20);
if (it != s.end()) {
std::cout << "找到了数字 20" << std::endl;
}
// 方法二:用 count 快捷判断
if (s.count(40)) {
std::cout << "40 存在" << std::endl;
} else {
std::cout << "40 不存在" << std::endl; // 会执行这一行
}2.5 遍历集合
因为 set 的元素在内存中并不是连续存放的,所以它不支持下标随机访问(即不能写 s[i])。我们必须使用迭代器,或者最方便的范围 for 循环:
std::set<int> s = {50, 10, 30, 20};
// 推荐写法:范围 for 循环
for (int x : s) {
std::cout << x << " "; // 输出:10 20 30 50
}[!NOTE]
set的迭代器是“双向迭代器”(Bidirectional Iterator)。这意味着你可以对它进行自增it++或自减it--,但不能进行快速跨步,例如it + 5或是it += 2在set中都是非法的编译错误。
三、 进阶利器:寻找边界(lower_bound 与 upper_bound)
在信奥竞赛(如 CSP-J/S、GESP 等)中,set 的这两个边界查找函数极其重要,是二分算法的有力帮手:
s.lower_bound(x):返回指向首个大于或等于x的元素的迭代器。s.upper_bound(x):返回指向首个大于x的元素的迭代器。
我们通过一个实例来直观感受它们之间的差异:
假设集合 s = {1, 3, 5, 7, 9}:
查找目标 x |
s.lower_bound(x) 返回值 |
指向的值 | 说明 |
|---|---|---|---|
5 |
lower_bound(5) |
5 |
首个 的元素是 5 本身 |
5 |
upper_bound(5) |
7 |
首个 的元素是 7 |
6 |
lower_bound(6) |
7 |
首个 的元素是 7 |
6 |
upper_bound(6) |
7 |
首个 的元素是 7 |
10 |
lower_bound(10) |
s.end() |
找不到 的元素,返回尾部迭代器 |
⚠️ 信奥必看避坑指南:必须调用成员函数!
在 C++ 中,全局头文件 <algorithm> 里也有 std::lower_bound 和 std::upper_bound。
当你需要对 set 进行边界查询时,千万不要写成全局的调用方式:
// ❌ 错误示范:时间复杂度退化为 O(n),会导致超时 (TLE)!
auto it = std::lower_bound(s.begin(), s.end(), 6);
// 正确示范:时间复杂度为高效的 O(log n)
auto it = s.lower_bound(6);为什么?
全局的 std::lower_bound 适用于支持随机访问的容器(如 vector)。对于不支持随机访问的 set,如果强行使用全局二分,它内部只能以类似于逐个遍历的方式寻找,时间复杂度会退化为 。而调用 s.lower_bound() 成员函数,它会直接利用红黑树的树状结构进行查找,保持完美的 性能。
四、 多重集合 (multiset) 与经典“大坑”
有的时候,我们确实需要保持容器元素有序,但允许元素重复。这时候我们就需要使用 multiset(多重集合)。
multiset 同样包含在 <set> 头文件中,用法与 set 几乎一模一样。但由于它允许元素重复,在删除元素时,隐藏着一个极其经典的高频翻车陷阱。
🚨 经典陷阱:被全部消灭的重复元素
假设我们有一个 multiset,里面放了几个重复的数字:
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms = {1, 2, 2, 2, 3};
// 我们的初衷:只删除其中的“一个”数字 2
ms.erase(2);
// 输出集合里的元素
for (int x : ms) {
std::cout << x << " ";
}
return 0;
}请问:输出结果是什么?
- 许多人直觉以为会输出:
1 2 2 3(只删掉了一个2)。 - 但实际运行结果是:
1 3!所有的2都被删光了!
这是因为,当你向 erase() 传入一个具体的数值时,multiset 会把所有值等于该数的元素全部清除。
💡 正确解法:使用迭代器精准打击
如果你的业务场景只需要删除一个重复的元素,必须先用 find() 找到它对应的迭代器,然后删除迭代器,而不是直接删除数值:
std::multiset<int> ms = {1, 2, 2, 2, 3};
auto it = ms.find(2); // find 始终返回指向“第一个”匹配元素的迭代器
if (it != ms.end()) {
ms.erase(it); // 传入迭代器,只删除这一个特定的元素!
}
// 此时输出:1 2 2 3 (符合预期!)五、 set vs vector:深度性能大比拼
在竞赛做题时,我们应该选择 vector 还是 set?来看这张对比表:
| 对比维度 | vector (无序) |
vector (有序 + 二分) |
set (红黑树) |
|---|---|---|---|
| 插入元素 | (直接在末尾追加) | (为了保持有序,需要移动后续元素) | (树节点查找插入) |
| 查找是否存在 | (需要从头找到尾) | (可以使用 binary_search) |
|
| 任意位置删除 | (删除后需要整体前移) | (删除后需要整体前移) | |
| 内存开销 | 极低 (连续内存,没有额外负担) | 极低 | 较高 (每个节点需要额外存储父、左、右指针和节点颜色信息) |
| 自动去重 | 否 | 需手动配合 std::unique |
是 |
使用建议:
- 如果数据只在最开始插入一次,后续只有频繁的查找,推荐使用排好序的
vector+std::lower_bound,因为它内存紧凑,对 CPU 缓存友好,常数更小。 - 如果你的数据是一边不断插入/删除,一边又在不停查找的动态过程,那么
set是唯一的选择。
结语与下期预告
今天我们了解了 set 和 multiset。它们通过神奇的平衡二叉树结构,把插入、删除和查找的时间复杂度完美控制在了 。
不过,set 只能存放单一的元素(也就是 Key)。如果我们希望给每个元素关联一个“附加信息”,比如:
- 输入人名(Key),查到他的电话号码(Value);
- 输入学号(Key),查到他的信奥成绩(Value);
这又该用什么容器呢?
下一篇文章,我们将介绍关联容器的另一个核心成员——map(映射)。它能以同样的 效率,帮我们建立完美的“键值对”对应关系,敬请期待!
看完题解,马上用 240 关实战检验掌握度
覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。
配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。
同专栏相关推荐
【信奥业余科普】C++ 的奇妙之旅 | 21:拒绝重复造轮子——STL标准模板库的设计思想与底层逻辑
在前面的二十篇文章中,我们从底层的"0和1"、变量的内存布局,一路讲到了函数、指针与引用。到目前为止,我们已经掌握了 C++ 中最基本的构件。 但在实际的软件开发中,如果每次遇到问题都要从零开始手写数组管理、排序算法,效率就太低了。为了解决这个问题,C++ 提供了一套功...
【信奥业余科普】C++ 的奇妙之旅 | 22:深入 vector——动态数组的使用与底层细节
上一篇文章介绍了 STL 的整体设计思想——容器、迭代器、算法三层架构。从本篇开始,我们将逐一深入 STL 中最常用的容器。 第一个要详细展开的,自然是 vector——信奥中使用频率最高的容器,没有之一。
【信奥业余科普】C++ 的奇妙之旅 | 23:主动限制的艺术——栈(stack)与队列(queue)
上一篇文章我们介绍了 vector 动态数组。vector 支持末尾追加、下标随机访问、中间插入删除等操作,功能非常灵活。 既然 vector 已经足够通用,为什么 STL 中还要专门提供 stack(栈)和 queue(队列)? 这就引出了软件工程中一个重要的设计思想...
OneCoder
始于 2012持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com