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

> Author: OneCoder (李宏哲) | Canonical: https://www.coderli.com/cs-basics-25-cpp-set/
> Published: 2026-05-25 | Topic: CSP / NOIP 信奥竞赛 / CSP-J
> Tags: 科普, 计算机科学基础, GESP, CSP, C++, STL, set, multiset

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

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

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

**往期回顾：**

- [第一部分【计算机历史】系列文章合集（共8篇）](https://www.coderli.com/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%8E%86%E5%8F%B2/)
- [第二部分【C++的奇妙之旅】前24篇合集](https://www.coderli.com/categories/c-%E7%9A%84%E5%A5%87%E5%A6%99%E4%B9%8B%E6%97%85/)

---

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

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

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

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

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

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

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

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

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

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

用一个示意图来理解：

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

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

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

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

即使容器里有一百万（$10^6$）个元素，查找一个数字也**最多只需要比较 20 次左右**。比起 `vector` 挨个遍历的 100 万次比较，性能大幅提升。

---

## 二、 `set` 的基本操作

使用 `set` 需要引入头文件 `<set>`。

### 2.1 创建与初始化

```cpp
#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`)

```cpp
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` 中删除元素非常方便，可以直接传入要删除的值，也可以传入指向该元素的迭代器：

```cpp
std::set<int> s = {10, 20, 30};

s.erase(20); // 直接删除值等于 20 的元素
s.erase(50); // 尝试删除不存在的 50，什么也不会发生（erase 返回 0）
```

### 2.4 查找元素 (`find` 与 `count`)

这是 `set` 最常用的两个成员函数：

1. **`find(x)`**：寻找值为 `x` 的元素。
   - 如果找到了，返回指向该元素的**迭代器**。
   - 如果没找到，返回指向集合末尾的 **`s.end()`** 迭代器。
2. **`count(x)`**：统计值为 `x` 的元素在集合中出现的次数。
   - 因为 `set` 中元素是唯一的，所以返回值只可能是 `0`（不存在）或 `1`（存在）。这在代码中经常被用来当作“判断是否存在”的快捷写法。

```cpp
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 循环**：

```cpp
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` 进行边界查询时，**千万不要写成全局的调用方式**：

```cpp
// ❌ 错误示范：时间复杂度退化为 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`，里面放了几个重复的数字：

```cpp
#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()` 找到它对应的迭代器，然后**删除迭代器**，而不是直接删除数值：

```cpp
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`                     | **是**                                                        |

**使用建议**：

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

---

## 结语与下期预告

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

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

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

这又该用什么容器呢？

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

---
Source: OneCoder (https://www.coderli.com/cs-basics-25-cpp-set/) | GESP Wiki: https://wiki.coderli.com/ | OI-Game: https://oi.coderli.com/
