178 lines
7.8 KiB
Markdown
178 lines
7.8 KiB
Markdown
### **C++ STL 核心容器讲义：`set` 集合**
|
||
|
||
#### **一、 引言**
|
||
|
||
##### **1.1 问题引入：智能的木材仓库**
|
||
|
||
【例17-5 木材仓库】我们来管理一个特殊的木材仓库。这个仓库有以下几条严格的规则：
|
||
1. **唯一性**：仓库里不会有两根长度完全相同的木材。
|
||
2. **动态变化**：需要频繁地“进货”（加入新木材）和“出货”（取出木材）。
|
||
3. **智能出货**：当需要取出一根长度为 `Length` 的木材时：
|
||
* 如果有，就取出它。
|
||
* 如果没有，不能随便拿，必须取出仓库中与之长度**最接近**的一根。
|
||
* 如果最接近的有两根（一长一短），则**优先取短**的那一根。
|
||
|
||
##### **1.2 价值阐述：为什么需要 `set`？**
|
||
|
||
我们来分析一下这个仓库对数据容器的需求：
|
||
1. **元素唯一**：这要求容器能自动处理重复元素。
|
||
2. **动态增删**：容器必须支持高效的插入和删除。
|
||
3. **快速查找“最接近”**：这是最核心、最难的需求。要找“最接近”，数据最好是**有序**的，这样我们才能快速定位到一个值和它的“左邻右舍”。
|
||
|
||
常规的 `vector` 或数组，虽然可以排序，但每次插入新元素都会破坏顺序，需要重新排序，效率极低。我们需要一个**“时刻保持有序”**且能**“自动去重”**的智能容器。
|
||
|
||
C++ STL (Standard Template Library) 中，就提供了这样一个完美的工具——`std::set`。
|
||
|
||
##### **1.3 学习目标**
|
||
|
||
学完本讲义，你将能够：
|
||
1. 理解 `set` 的三大核心特性：有序性、唯一性、动态性。
|
||
2. 熟练掌握 `set` 的创建、插入(`insert`)、查找(`find`)、删除(`erase`)等基本操作。
|
||
3. 掌握使用 `lower_bound` 在 `set` 中高效查找“第一个大于或等于”目标值的元素。
|
||
4. 运用 `set` 解决需要维护动态有序集合的复杂问题。
|
||
|
||
---
|
||
|
||
#### **二、 `set` 详解：一个自动排序与去重的集合**
|
||
|
||
##### **2.1 `set` 的核心特性**
|
||
|
||
`set` 是一个容器，你可以把它想象成一个“数学集合”。它最重要的三个特性是：
|
||
|
||
1. **元素唯一性 (Uniqueness)**：`set` 中不允许存在重复的元素。如果你尝试插入一个已经存在的元素，`set` 会自动忽略这次插入操作。
|
||
2. **自动排序 (Ordering)**：无论你以何种顺序插入元素，`set` 内部都会**始终**按照元素的值（从小到大）来维护一个有序的序列。
|
||
3. **动态增删 (Dynamic)**：可以高效地添加或删除元素，并且在操作后依然保持有序。
|
||
|
||
**内部原理揭秘**：`set` 之所以能拥有这些神奇的特性，是因为它的底层通常是由一种叫做**“红黑树”**（一种高度自平衡的二叉搜索树）的数据结构实现的。这保证了它的各项操作（插入、删除、查找）都具有非常高效的对数时间复杂度 $O(\log N)$。
|
||
|
||
##### **2.2 基本操作**
|
||
|
||
使用 `set` 前，必须包含头文件：`#include <set>`
|
||
|
||
1. **创建 `set`**：
|
||
```cpp
|
||
#include <set>
|
||
using namespace std;
|
||
|
||
set<int> wood_set; // 创建一个名为 wood_set 的集合，专门存放 int 类型的木材长度
|
||
```
|
||
语法：`set<DataType> variable_name;`
|
||
|
||
2. **插入元素：`insert()`**
|
||
* **作用**：将一个元素添加到集合中。
|
||
* **用法**：`wood_set.insert(length);`
|
||
* `set` 会自动完成排序和去重工作。
|
||
|
||
3. **查找元素：`find()`**
|
||
* **作用**：在集合中查找指定的元素。
|
||
* **返回值**：返回一个指向元素的**迭代器 (Iterator)**。迭代器可以理解为指向容器内部元素的一个“指针”或“书签”。
|
||
* 如果**找到了**，返回指向该元素的迭代器。
|
||
* 如果**没找到**，返回一个特殊的迭代器 `wood_set.end()`。`.end()` 本身不指向任何有效元素，它只是一个“集合末尾之后”的标志，专门用来表示“未找到”。
|
||
* **用法**（判断元素是否存在）：
|
||
```cpp
|
||
if (wood_set.find(length) != wood_set.end()) {
|
||
cout << "Already Exist\n";
|
||
} else {
|
||
// 元素不存在，可以进行插入
|
||
wood_set.insert(length);
|
||
}
|
||
```
|
||
|
||
4. **删除元素：`erase()`**
|
||
* **作用**：从集合中移除指定的元素。
|
||
* **用法**：`wood_set.erase(length);`
|
||
|
||
5. **检查是否为空：`empty()`**
|
||
* **作用**：判断集合中是否有元素。
|
||
* **用法**：`if (wood_set.empty()) { ... }`
|
||
|
||
---
|
||
|
||
#### **三、 实战演练：解决木材仓库问题**
|
||
|
||
##### **3.1 处理“进货”操作 (格式 `1 Length`)**
|
||
|
||
这个需求与 `set` 的 `find` 和 `insert` 操作契合。
|
||
```cpp
|
||
int type, length;
|
||
cin >> type >> length;
|
||
|
||
if (type == 1) {
|
||
if (wood_set.find(length) != wood_set.end()) {
|
||
cout << "Already Exist\n";
|
||
} else {
|
||
wood_set.insert(length);
|
||
}
|
||
}
|
||
```
|
||
|
||
##### **3.2 处理“出货”操作 (格式 `2 Length`)**
|
||
|
||
这是本题的核心难点，也是 `set` 有序性大放异彩的地方。
|
||
|
||
**第一步：处理空仓库的边界情况**
|
||
```cpp
|
||
if (wood_set.empty()) {
|
||
cout << "Empty\n";
|
||
continue; // 直接处理下一条操作
|
||
}
|
||
```
|
||
|
||
**第二步：寻找“最接近”的两个候选者**
|
||
在一个有序的集合中，与目标 `Length` 最接近的数，只可能是：
|
||
* **候选者 A (后继)**：在**大于或等于** `Length` 的数中，最小的那一个。
|
||
* **候选者 B (前驱)**：在**严格小于** `Length` 的数中，最大的那一个。
|
||
|
||
如何高效地找到这两个候选者？答案是**二分查找**。`set` 的有序性让它天生支持二分。
|
||
|
||
**寻找候选者 A (后继)：`lower_bound()`**
|
||
`lower_bound` 是 C++ 算法库中的一个函数，它能在有序容器中进行二分查找，找到第一个**不小于**（即大于或等于）目标值的位置。
|
||
|
||
```cpp
|
||
// 在 wood_set 中查找第一个不小于 length 的元素
|
||
auto it_A = wood_set.lower_bound(length);
|
||
```
|
||
* `it_A` 是一个迭代器，指向候选者A。
|
||
|
||
**寻找候选者 B (前驱)**
|
||
候选者 B 正是候选者 A 在有序序列中的**前一个元素**。
|
||
|
||
```cpp
|
||
// 如果 it_A 不是集合的第一个元素，那么它一定有前驱
|
||
if (it_A != wood_set.begin()) {
|
||
auto it_B = prev(it_A); // C++11 之后，用 prev(it) 获取前一个迭代器
|
||
// 或者 it_B = it_A; it_B--; (C++11 之前)
|
||
// ... 此时 it_B 指向候选者 B ...
|
||
}
|
||
```
|
||
|
||
**第三步：比较候选者，做出最终选择**
|
||
现在我们最多有两个候选者（由 `it_A` 和 `it_B` 指向），接下来就是简单的比较：
|
||
1. 如果只有一个候选者（比如 `it_A` 是集合的第一个元素，没有前驱 `it_B`），那就直接选它。
|
||
2. 如果两个都有，就分别计算它们与 `Length` 的差值。
|
||
3. 如果差值不同，选差值小的那个。
|
||
4. 如果差值相同，按题目要求，**优先选短的**，即选候选者B。
|
||
|
||
**第四步：执行出货**
|
||
确定了最终要取出的木材 `best_choice` 之后，将其从集合中删除。
|
||
```cpp
|
||
cout << best_choice << "\n";
|
||
wood_set.erase(best_choice);
|
||
```
|
||
|
||
---
|
||
|
||
#### **四、 总结**
|
||
|
||
`set` 是 C++ STL 中一个极其强大的容器，是解决**动态有序集合**相关问题。
|
||
|
||
* **核心原理**：底层由**平衡二叉搜索树**实现，保证了**有序性**和各项操作的**对数时间复杂度 ($O(\log N)$)**。
|
||
* **三大特性**：**元素唯一**、**自动排序**、**高效增删**。
|
||
* **核心操作回顾**：
|
||
* **创建**: `set<T> s;`
|
||
* **插入**: `s.insert(val);`
|
||
* **判断存在**: `s.find(val) != s.end()`
|
||
* **删除**: `s.erase(val);`
|
||
* **查找下界**: `s.lower_bound(val);` (极其重要，用于在有序集合中定位)
|
||
|
||
当你遇到的问题需要维护一个不允许重复且时刻需要保持有序的数据集合时，第一时间就应该想到 `set`。 |