【信奥业余科普】C++ 的奇妙之旅 | 25：自动排序的利器——集合（set）与多重集合（multiset）

发表于 2026/05/25

作者 OneCoder

次浏览 16 分钟阅读

上一篇文章我们拆解了 deque 双端队列，并以此告别了“序列容器”的世界。在之前的文章中，无论是 vector、stack、queue 还是 deque，元素都是按照我们 插入的顺序 排列的。如果想要查找某个元素是否存在，在没有排序的情况下，我们只能从头到尾挨个找，时间复杂度是 $O(n)$。

如果我们需要一个容器，能 自动帮我们去重、排序，并且在 极短的时间内（比如 $O(\log n)$） 查找到某个元素，该怎么办呢？

这就需要请出我们今天的主角—— 关联容器（Associative Containers） 的敲门砖：set（集合）和 multiset（多重集合）。

往期回顾：

一、什么是关联容器与集合（set）？

在介绍 STL 中的 set 之前，我们先理解一下什么叫关联容器。

序列容器（如 vector）关注的是元素的位置：你把元素放在第几个位置，它就在第几个位置。 关联容器关注的是元素的值：元素存放在什么位置，是由元素自身的值（通常称为 键 Key）决定的。容器内部会根据元素的值自动把它们组织起来，实现极速的查找。

C++ STL 中的 set 翻译成中文就是集合。它与数学中的“集合”概念完美对应，拥有两个核心特点：

去重（Uniqueness）：集合中的每个元素都必须是独一无二的，不能出现重复的元素。
有序（Ordered）：集合中的元素会自动按照从小到大的顺序（升序）排好。

1.1 底层结构：平衡二叉搜索树（红黑树）

为什么 set 既能保持有序，又能在 $O(\log n)$ 的时间内完成插入、删除和查找？

这得益于它的底层数据结构——红黑树（Red-Black Tree）。它是一种自平衡的二叉搜索树。

在信奥阶段，我们不需要去深究红黑树复杂的旋转和着色算法。我们只需要直观地理解二叉搜索树（BST）的“查找二分法”：

每个节点最多有两个子节点（左子节点和右子节点）。
任何一个节点的左子树中所有节点的值，都比当前节点小。
任何一个节点的右子树中所有节点的值，都比当前节点大。

用一个示意图来理解：

       8  (根节点)
     /   \
    4     12
   / \   /  \
  2   6 10  14

当我们要在这个树里查找数字 10 时：

拿 10 和根节点 8 比较，因为 10 > 8，所以往右走，来到 12。
拿 10 和 12 比较，因为 10 < 12，所以往左走，来到 10。
找到了！

对于拥有 $n$ 个元素的平衡二叉搜索树，树的高度大约为 $\log_2 n$。这意味着，无论查找、插入还是删除，我们最多只需要比较 $\log_2 n$ 次。

即使容器里有一百万（$10^6$）个元素，查找一个数字也最多只需要比较 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; // 输出 2

2.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`	首个 $\ge 5$ 的元素是 `5` 本身
`5`	`upper_bound(5)`	`7`	首个 $> 5$ 的元素是 `7`
`6`	`lower_bound(6)`	`7`	首个 $\ge 6$ 的元素是 `7`
`6`	`upper_bound(6)`	`7`	首个 $> 6$ 的元素是 `7`
`10`	`lower_bound(10)`	`s.end()`	找不到 $\ge 10$ 的元素，返回尾部迭代器

⚠️ 信奥必看避坑指南：必须调用成员函数！

在 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，如果强行使用全局二分，它内部只能以类似于逐个遍历的方式寻找，时间复杂度会退化为 $O(n)$。而调用 s.lower_bound() 成员函数，它会直接利用红黑树的树状结构进行查找，保持完美的 $O(\log n)$ 性能。

四、多重集合 (`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` (红黑树)
插入元素	$O(1)$ （直接在末尾追加）	$O(n)$ （为了保持有序，需要移动后续元素）	$O(\log n)$ （树节点查找插入）
查找是否存在	$O(n)$ （需要从头找到尾）	$O(\log n)$ （可以使用 `binary_search`）	$O(\log n)$
任意位置删除	$O(n)$ （删除后需要整体前移）	$O(n)$ （删除后需要整体前移）	$O(\log n)$
内存开销	极低（连续内存，没有额外负担）	极低	较高（每个节点需要额外存储父、左、右指针和节点颜色信息）
自动去重	否	需手动配合 `std::unique`	是

使用建议：

如果数据只在最开始插入一次，后续只有频繁的查找，推荐使用排好序的 vector + std::lower_bound，因为它内存紧凑，对 CPU 缓存友好，常数更小。
如果你的数据是一边不断插入/删除，一边又在不停查找的动态过程，那么 set 是唯一的选择。

结语与下期预告

今天我们了解了 set 和 multiset。它们通过神奇的平衡二叉树结构，把插入、删除和查找的时间复杂度完美控制在了 $O(\log n)$。

不过，set 只能存放单一的元素（也就是 Key）。如果我们希望给每个元素关联一个“附加信息”，比如：

输入人名（Key），查到他的电话号码（Value）；
输入学号（Key），查到他的信奥成绩（Value）；

这又该用什么容器呢？

下一篇文章，我们将介绍关联容器的另一个核心成员——map（映射）。它能以同样的 $O(\log n)$ 效率，帮我们建立完美的“键值对”对应关系，敬请期待！

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

信奥业余科普, C++的奇妙之旅

科普计算机科学基础 GESP CSP C++ STL set multiset

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、 什么是关联容器与集合（set）？

1.1 底层结构：平衡二叉搜索树（红黑树）

二、 set 的基本操作

2.1 创建与初始化

2.2 插入元素 (insert)

2.3 删除元素 (erase)

2.4 查找元素 (find 与 count)