一、课上练习

编程练习

1. set的增删查：L3271
2. 重复的学号：L3272

二、知识总结

✨ 核心思想

set 是 C++ 标准模板库（STL）中的一个关联容器，它主要用于存储唯一元素的集合，提供了高效的元素查找、插入和删除操作。set 的内部实现通常是一个平衡二叉搜索树（如红黑树），这使得大多数操作的时间复杂度为对数级别。

✨ 特性

set 具有以下核心特性：

• 元素唯一性：在 set 中，所有元素都是唯一的。尝试插入一个已经存在的元素会被忽略。
• 自动排序：set 中的元素根据其值自动排序，默认按照升序排序。
• 直接访问不可用：与 vector 和 deque 等序列容器不同，set 不支持随机访问操作。你不能通过下标访问 set 中的元素。

✨ 常用操作

set 支持以下常用操作：

• 插入元素：insert() 方法用于插入元素，如果元素已存在，则不会进行任何操作。
• 删除元素：erase() 方法可以根据元素值或迭代器位置来删除元素。
• 查找元素：find() 方法用于查找特定值的元素，返回一个指向找到的元素的迭代器，如果未找到，则返回 end()。
• 大小和容量：size() 返回 set 中元素的数量，empty() 检查 set 是否为空。

✨ 性能考虑

set 各操作的时间复杂度：

• 访问性能：查找、插入和删除操作通常具有 O(log n) 的时间复杂度，其中 n 是 set 中元素的数量。
• 内存使用：由于使用了红黑树或类似结构，set 的内存使用效率可能低于简单数组，但提供了额外的功能如自动排序和快速查找。

✨ 应用场景

set 适用于以下场景：

• 当需要保持元素的唯一性并且频繁进行查找、插入和删除操作时，set 是一个理想的选择。
• 在需要对元素进行排序且排序规则不经常变化的情况下使用 set，可以省去手动排序的麻烦。
• 当不需要按照插入顺序访问元素，而是需要按照某种顺序或基于元素值进行快速查找时，set 提供了优势。

总的来说，std::set 是一个功能强大的容器，适用于需要排序、唯一性和高效查找操作的场景。如果你的应用场景中元素的集合需要频繁的更新操作且每个元素必须是唯一的，set 将是一个非常合适的选择。

✨ 执行示例

下面展示一系列 set 操作的完整执行过程，帮助理解 set 内部的自动排序和去重机制。

操作序列：

1set<int> s;
2s.insert(5);   // 第1步
3s.insert(2);   // 第2步
4s.insert(8);   // 第3步
5s.insert(2);   // 第4步（重复元素）
6s.insert(1);   // 第5步
7s.erase(5);    // 第6步
8s.find(8);     // 第7步

如何判断 insert 是否成功：

1auto result = s.insert(2);
2// result.first 是指向元素的迭代器
3// result.second 是 bool，true 表示插入成功，false 表示元素已存在
4if (result.second) {
5    cout << "插入成功" << endl;
6} else {
7    cout << "元素已存在" << endl;
8}

迭代器遍历过程： 对于 set {1, 2, 8}，使用 begin() 到 end() 遍历：

• it = begin() -> 指向 1
• ++it -> 指向 2
• ++it -> 指向 8
• ++it -> 等于 end()，遍历结束

输出顺序一定是从小到大：1 2 8

✨ 解题步骤详解

以"去除重复数字"为例：

问题： 给定 n 个整数，去除重复数字后按升序输出。

解题步骤：

1. 选择数据结构：set 天然具有去重和排序功能，非常适合此题。
2. 读入数据：逐个读入 n 个整数，每个都 insert 到 set 中。重复的元素会被自动忽略。
3. 输出结果：用迭代器从 begin() 遍历到 end()，输出的顺序自动就是升序。

代码框架：

1set<int> s;
2for (int i = 0; i < n; i++) {
3    int x;
4    cin >> x;
5    s.insert(x);
6}
7for (auto it = s.begin(); it != s.end(); ++it) {
8    cout << *it << " ";
9}

时间复杂度分析： 插入 n 个元素，每次 O(log n)，总计 O(n log n)。遍历输出 O(n)。总复杂度 O(n log n)。

✨ 常见错误

1. 试图用下标访问 set 元素：set 不支持 s[0] 这样的随机访问，必须使用迭代器。如果需要第 k 个元素，只能从 begin() 开始移动 k 次。
2. 修改 set 中元素的值：set 的迭代器指向的元素是 const 的，不能直接修改 *it = newValue。如需修改，必须先 erase 再 insert。
3. erase 时迭代器失效：在循环中删除元素时，s.erase(it) 会使 it 失效。正确做法是 it = s.erase(it)（C++11 起 erase 返回下一个有效迭代器）。
4. 忘记 set 和 multiset 的区别：set 不允许重复元素，如果需要允许重复，应使用 multiset。
5. 自定义类型忘记定义比较运算符：set 内部需要比较元素大小。对于自定义结构体，必须重载 < 运算符或提供自定义比较函数。

✨ 代码实现

下面的代码展示了 set 的各种常用操作，包括插入、查找、删除、遍历和清空等：

1#include <iostream>
2#include <set>
3using namespace std;
4
5int main() {
6    // 创建并初始化set
7    set<int> st = {5, 1, 4, 2, 3};
8
9    // insert: 向set中添加元素
10    auto result = st.insert(6); // 尝试插入6
11    if (result.second) {
12        cout << "Insert 6 successful." << endl;
13    }
14    result = st.insert(3); // 尝试插入3（已存在）
15    if (!result.second) {
16        cout << "3 already exists in the set." << endl;
17    }
18
19    // find: 在set中查找元素
20    auto it = st.find(4);
21    if (it != st.end()) {
22        cout << "Found 4 in the set." << endl;
23    }
24
25    // erase: 从set中删除元素
26    st.erase(2); // 删除元素2
27    it = st.find(2);
28    if (it == st.end()) {
29        cout << "2 was successfully removed from the set." << endl;
30    }
31
32    // size: 获取set中元素的数量
33    cout << "Size of set: " << st.size() << endl;
34
35    // 使用范围for循环遍历并打印set中的所有元素
36    cout << "Elements in set: ";
37    for (auto it = st.begin(); it != st.end(); ++it) {
38            cout << *it << " ";
39    }
40    cout << endl;
41
42    // clear: 清空set中的所有元素
43    st.clear();
44
45    // empty: 检查set是否为空
46    if(st.empty()) {
47        cout << "Set is empty now." << endl;
48    }
49
50    return 0;
51}

三、课后练习

编程练习

1. 去除重复数字：L3273