波仔
🔷 第十三章 STL
📄 一句话概括

set = "自动排序 + 自动去重"的袋子。 你只管 insert，它自己保证没有重复、并且按升序排好。查找/插入/删除都是 O(log n)（底层是平衡二叉搜索树）。两条铁规矩：元素不能改（它是排序依据，set 的元素是 const 的，要改只能 erase 再 insert）；没有 []（想按值找就用 find / count）。实例02 就是它的入门：造一个整型集合、往里插数据，看它怎么自己排好、怎么把重复的挡掉。

📝 本节和前面几节的关系

13.2 讲了关联式容器的两组差别（存不存值 / 许不许重复），这一节打开的是"只存键 + 不许重复"那一格。 - 和 7.1 数组 比：数组要自己写循环去重、自己写排序； - 和 13.1.1 vector 比：vector 只管按顺序放，不管内容；set 主动维护内容的有序与唯一； - set 内部的"比较规则"就是 11.2.2 运算符重载里的 <； - 它和 10.4.5 嵌套类的思路一致：把"怎么维护顺序"这件脏活藏进类型内部，外面只看到一个干净的接口。 这一节引入的 pair 与"插入失败"的返回值，会一路用到 13.2.3 的 map。

一、set 的两条铁律（先立规矩）

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(5);
    s.insert(1);
    s.insert(5);        // ★ 重复的：插不进去（也不报错）
    s.insert(3);
    s.insert(1);        // ★ 再来一个重复的

    cout << "元素个数：" << s.size() << "（插了 5 次）" << endl;
    cout << "内容：";
    for (int x : s) cout << x << " ";     // ★ 自动升序
    cout << endl;

    // ── 铁律①：没有 [] ──────────────────
    // cout << s[0] << endl;              // ❌ 编译不过：set 没有 operator[]

    // ── 铁律②：元素不能改 ────────────────
    // *s.begin() = 100;                  // ❌ 报 assignment of read-only location

    // 想"改"，只能删了再插
    s.erase(3);
    s.insert(30);
    cout << "把 3 改成 30 之后：";
    for (int x : s) cout << x << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

元素个数：3（插了 5 次）
内容：1 3 5 
把 3 改成 30 之后：1 5 30

"插了 5 次只有 3 个"——这就是 set 的核心价值：去重是自动的，你不需要写任何判断。 同时注意输出永远是升序，哪怕你插入的顺序是乱的。

为什么"插不进去"不报错：set 认为"重复"是正常情况（日常里你经常不知道这东西在不在），所以它静静地不动。如果你想知道"到底插进去了没有"，得看 insert 的返回值（下面讲）。

二、insert 的返回值：一个 pair，一个 bool

这是 set 最值得单独记的一点——insert 不只插入，还告诉你"成功了没有"：

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> s;

    pair<set<string>::iterator, bool> r1 = s.insert("apple");
    cout << "第一次插 apple：" << (r1.second ? "成功" : "失败")
         << "，它现在在：" << *r1.first << endl;

    pair<set<string>::iterator, bool> r2 = s.insert("apple");
    cout << "第二次插 apple：" << (r2.second ? "成功" : "失败")
         << "，已存在的是：" << *r2.first << endl;

    // C++11 之后更省事的写法
    auto r3 = s.insert("banana");
    if (r3.second) cout << "banana 是新的" << endl;
    return 0;
}

看到什么算成功：

第一次插 apple：成功，它现在在：apple
第二次插 apple：失败，已存在的是：apple

读懂那个 pair：

成员 含义
.first 指向那个元素的迭代器（插进去的话指向新的；没插进去的话指向已存在的那个）
.second bool：是否真的插入成功了

这个设计很实用：一次操作同时完成"检查 + 插入"。比如"我要把新用户名加进名单，但如果已经有人用了就报错"—— cpp if (!users.insert(name).second) cout << "用户名已被占用" << endl; 不用先 find 再 insert（那是两次 O(log n)），一次就够。 顺带复习：pair 就是 12.2.2 的 Pair<T1, T2>，标准库版本叫 std::pair（定义在 <utility> 里，<set> 会间接带上）。

三、实例02：创建整型集合并插入数据（教材实例）

任务：按教材要求，造一个 int 的 set，插数据、看结果。

#include <iostream>
#include <set>
using namespace std;

int main() {
    // ── ① 创建并初始化 ──────────────────
    int arr[] = {3, 5, 1, 7, 3, 9, 5, 1, 8};
    set<int> s(arr, arr + 9);            // 用区间构造（迭代器）

    cout << "① 用数组构造后：";
    for (int x : s) cout << x << " ";
    cout << "  （数组有 9 个，set 里只有 " << s.size() << " 个）" << endl;

    // ── ② 继续插入 ──────────────────────
    s.insert(2);
    s.insert(6);
    s.insert(1);                          // 已存在，无效
    s.insert(5);                          // 已存在，无效
    cout << "② 再插 2、6、1、5 之后：";
    for (int x : s) cout << x << " ";
    cout << "  （size=" << s.size() << "）" << endl;

    // ── ③ 查找：find 与 count ────────────
    if (s.find(7) != s.end())
        cout << "③ find(7)：找到了" << endl;
    if (s.find(100) == s.end())
        cout << "③ find(100)：没找到" << endl;

    cout << "③ count(5)   = " << s.count(5)   << "（存在 → 1）" << endl;
    cout << "③ count(100) = " << s.count(100) << "（不存在 → 0）" << endl;

    // ── ④ 遍历：迭代器 / 范围 for ─────────
    cout << "④ 正序：";
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it) cout << *it << " ";
    cout << endl;

    cout << "④ 倒序（反向迭代器）：";
    for (set<int>::reverse_iterator it = s.rbegin(); it != s.rend(); ++it) cout << *it << " ";
    cout << endl;

    // ── ⑤ 删除 ──────────────────────────
    s.erase(1);                           // 按键删
    cout << "⑤ 删掉 1 之后：";
    for (int x : s) cout << x << " ";
    cout << endl;

    s.erase(s.begin());                   // 按迭代器删（删最小的）
    cout << "⑤ 再删掉最小的之后：";
    for (int x : s) cout << x << " ";
    cout << endl;

    // ── ⑥ 首尾 ──────────────────────────
    cout << "⑥ 最小 = " << *s.begin() << "，最大 = " << *s.rbegin() << endl;
    cout << "   实际值：front 没有这个函数，但 begin() 就是最小值；rbegin() 是最大值" << endl;

    return 0;
}

看到什么算成功：

① 用数组构造后：1 3 5 7 8 9   （数组有 9 个，set 里只有 6 个）
② 再插 2、6、1、5 之后：1 2 3 5 6 7 8 9   （size=8）
③ find(7)：找到了
③ find(100)：没找到
③ count(5)   = 1（存在 → 1）
③ count(100) = 0（不存在 → 0）
④ 正序：1 2 3 5 6 7 8 9 
④ 倒序（反向迭代器）：9 8 7 6 5 3 2 1 
⑤ 删掉 1 之后：2 3 5 6 7 8 9 
⑤ 再删掉最小的之后：3 5 6 7 8 9 
⑥ 最小 = 3，最大 = 9
   实际值：front 没有这个函数，但 begin() 就是最小值；rbegin() 是最大值

六个必须收下的点：

  1. set<int> s(arr, arr + 9); —— 用两个迭代器构造。arr 是指针，指针也是迭代器（7.5.1 讲的"数组名退化成指针"在这里派上用场）。9 个数据里 3、5、1 各重复，所以只剩 6 个。
  2. erase 有两个重载：传"键"（s.erase(1)）和传"迭代器"（s.erase(s.begin())）。这是在 list / vector 那里已经见过的"迭代器定位"思路的延续。
  3. find 返回迭代器：找到就指向那个元素，没找到就返回 s.end()。所以判断"在不在"要写 != s.end()（和 13.1 里 vector 的 find 写法一样）。
  4. count 在 set 里只有 0 或 1：因为不许重复。set 的 count 实际用途就是"在不在"，比 find 写起来短。（在 multiset 里它能返回大于 1 的数——13.2.2。）
  5. rbegin() / rend() 是反向迭代器：rbegin() 指向最大元素，所以"取最大值"就是 *s.rbegin()。set 没有 front() / back()（那是序列容器的），但 begin() / rbegin() 顶上了这两个位置。
  6. set 永远有序，所以不需要 sort：任何时候遍历都是升序。想改排序规则，得在定义时给第二个模板参数（见下）。

四、想让 set 按自己的规则排

set 的完整模板签名是 set<键类型, 比较器, 分配器>（默认参数的存在感——正是 12.2.3 讲的"库能长大而不弄坏老代码"）：

#include <iostream>
#include <set>
#include <string>
using namespace std;

struct ByLength {                                   // 函数对象（仿函数）：重载了 () 的类
    bool operator()(const string &a, const string &b) const {
        if (a.size() != b.size()) return a.size() < b.size();   // 先按长度
        return a < b;                                            // 长度相同按字典序
    }
};

int main() {
    set<string, ByLength> s;                        // ★ 第二个模板参数
    s.insert("banana");
    s.insert("kiwi");
    s.insert("apple");
    s.insert("fig");
    s.insert("cherry");

    cout << "按长度排序：";
    for (const string &x : s) cout << x << "(" << x.size() << ") ";
    cout << endl;

    // 默认的 set 是按字典序
    set<string> d = {"banana", "kiwi", "apple", "fig", "cherry"};
    cout << "默认字典序：";
    for (const string &x : d) cout << x << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

按长度排序：fig(3) kiwi(4) apple(5) banana(6) cherry(6) 
默认字典序：apple banana cherry fig kiwi

两点说明：

  1. ByLength 是个"函数对象"（也叫仿函数）：它就是 10.4 那一章学的普通类，只不过重载了 operator()——于是它的对象能像函数一样被调用（cmp(a, b)）。这是 STL 里传递"自定义规则"的标准手法（13.3.3 的 sort 也用）。
  2. 比较器必须是"严格弱序"：不能有 a < a 为真、a<b 和 b<a 不能同时为真。写错了（比如用 <=）会造成未定义行为——set 会认为两个元素"相等"，然后丢掉一个。这是 set 最阴的一个坑：它不报错，只是默默少东西。

五、动手 Demo：用 set 做一个"生词本"

任务：手上有一份"已学过的词"（set），把一段文章里的生词挑出来（文章里出现、但不在已学词表里的词）。

#include <iostream>
#include <set>
#include <string>
#include <sstream>
using namespace std;

int main() {
    // ① 已学过的词表（set 自动去重、自动排序）
    set<string> known = {"apple", "banana", "cherry", "desk", "book"};
    cout << "已学词表（" << known.size() << " 个）：";
    for (const string &w : known) cout << w << " ";
    cout << endl;

    // ② 一篇文章（空格分隔的英文单词）
    string text = "I eat apple on my desk and read a good book every day";

    // ③ 挑生词：出现但"不在已知表里"
    set<string> unknown;                       // 生词也用 set：自动去重
    stringstream ss(text);
    string w;
    while (ss >> w) {
        if (known.find(w) == known.end())      // ★ 一次查找就是 O(log n)
            unknown.insert(w);
    }

    cout << "生词 " << unknown.size() << " 个：";
    for (const string &x : unknown) cout << x << " ";
    cout << endl;

    // ④ 顺便看看：生词里有没有"以大写开头"的（用 find_if + lambda 也行，这里手写）
    cout << "其中大写开头的：";
    for (const string &x : unknown)
        if (!x.empty() && x[0] >= 'A' && x[0] <= 'Z') cout << x << " ";
    cout << endl;

    // ⑤ 把生词加进词表（合并两个集合）
    known.insert(unknown.begin(), unknown.end());   // ★ 区间插入
    cout << "合并后词表共 " << known.size() << " 个词" << endl;
    return 0;
}

看到什么算成功：

已学词表（5 个）：apple banana book cherry desk 
生词 9 个：I a and day eat every good my on read 
其中大写开头的：I 
合并后词表共 14 个词

三个值得收下的写法：

写法 说明
known.find(w) == known.end() 判断"不在表里"的标准写法——find 找不到时返回 end()
known.insert(unknown.begin(), unknown.end()) 区间插入：把另一个容器的整段插进来。set 会自动把重复的挡掉，所以直接合并不用先去重
unknown 也用 set 生词本身也去重了（文中若出现两次，只算一个）+ 输出自动按字母序

这个 Demo 的意义：把"要判断的东西"放进 set，让查找从 O(n) 变成 O(log n)。 现实里的黑白名单、用户名占用检查、爬虫 URL 去重都是这个套路。 想要更快：只去重、不需要有序遍历时，用 unordered_set（哈希表，平均 O(1)）。 顺带一提：x[0] >= 'A' 这种按字节判断对英文字母有效；中文不能用它——因为 UTF-8 下一个汉字是 3 个字节（这也是本节没做"汉字过滤"的原因，string 按字节算，切汉字会切出乱码）。

30 秒实验

  1. 验证"重复插不进去"：连续 s.insert(1); s.insert(1); s.insert(1); 之后打印 s.size() → 只增加 1。
  2. 验证 insert 的返回值：cout << s.insert(3).second << " " << s.insert(7).second << endl;（假设 3 已在、7 不在）→ 输出 0 1。
  3. 验证"比较器写错会丢东西"：把 ByLength 里的 < 全改成 <=，插一堆长度相同的词（如 apple、mango、peach）→ size() 少一个（set 认为它们"相等"）。这就是"比较器必须严格弱序"的现场。
  4. 验证不能排序：sort(s.begin(), s.end()); → 编译不过（set 的迭代器是双向的，13.4.4）。

常见误区

  1. "set 能按下标取"——没有 []。要"第 n 个"只能 advance(it, n)（O(n)，等于白建了树）。如果频繁需要"第 n 个"，set 就是选错了。
  2. "insert 返回 bool"——返回的是 pair<iterator, bool>。想直接当条件用，要写 .second（或者用 C++17 的结构化绑定 auto [it, ok] = s.insert(x);）。
  3. "set 里的元素可以随便改"——编译不过（元素是 const）。正确做法：erase 掉，再 insert 新的。
  4. "count 在 set 里能返回 2"——不可能，最多 1。要"个数超过 1"，那是 multiset（13.2.2）。
  5. "比较器里写 <= 也没什么"——会造成元素丢失、且不报错。比较器必须满足"严格弱序"：不能有 a < a 为真、a < b 与 b < a 不能同真。
  6. "set 遍历慢，所以 set 差"——是取舍：set 牺牲遍历速度换来了 O(log n) 的查找/去重/排序。"只要去重、不要顺序"用 unordered_set；"要按下标扫"用 vector。
  7. "用 set 存自定义类，只要写个构造就行"——不行，必须能比较：要么重载 operator<（11.2），要么给比较器。否则报错长得吓人（模板展开几十行），看最后一条 note 最快。
  8. "erase(x) 删不掉会报错"——不报错（删 0 个而已）。想知道删掉没有，看 erase 的返回值（返回删除的元素个数，set 里是 0 或 1）。
自测三问（点开对答案） 1. **`set` 保证哪两件事？代价是什么？**——保证：**① 无重复（自动去重）；② 始终有序（默认升序）**。代价：**元素不能改**（是排序依据）、**没有 `[]`**、**不能 `sort`**（本来就有序）、**每个元素有树的额外开销、遍历不如 `vector` 快**。换来的好处是**查找/插入/删除都 O(log n)**。 2. **`s.insert(x)` 的返回值是什么意思？怎么用它？**——返回 **`pair`**：`.first` 指向那个元素（插入失败时指向**已存在的那个**），`.second` 表示**是否真插进去了**。**最实用的写法：`if (!users.insert(name).second) 报错`**——一次操作同时完成"检查 + 插入"。 3. **`s.find(x)` 和 `s.count(x)` 用哪个？**——**`set` 里两者判断"在不在"的效力一样**（`count` 只有 0/1）。**`find` 的好处是能拿到迭代器（后续可以 `erase(it)`）**；**`count` 写起来短**。**在 `multiset` 里 `count` 才有"数个数"的真正用途。** 判断"在不在"**都要和 `end()` 比**：`s.find(x) != s.end()`。

相关笔记