Lecture 3: 集合与映射（Set & Map：去重、词频统计与基于树的有序容器）（对应课程真实讲座 L06）

目录 · ← l2 · l4 →

Lecture 3: 集合与映射（Set & Map：去重、词频统计与基于树的有序容器）（对应课程真实讲座 L06）

概述

本讲解决两个高频需求：去重（同一批数据里只保留每种元素一份）与关联查询（按某个键快速找到对应的值）。为此引入两个新 ADT：集合 Set（元素的“成员关系”容器）与映射 Map（键→值的查表容器）。两者都建立在“有序结构”之上：元素/键始终按序排列，插入与查找都快得惊人（O(log n)），与课堂上之后才讲的哈希版本（HashSet/HashMap，平均 O(1)）形成对照。本讲用一个“去重挑战题”开场，并实现词频统计经典应用。 对应官方 L06（6/30，Sets and Maps）一讲；官方课上用《德古拉》全文做过词频统计演示。

核心概念与算法原理

1. 挑战题：去重（De-Dupe）

问题定义：写一个函数，输入一串字符串，把其中每种字符串恰好打印一次。例如 {"unicorn", "starfish", "hummingbird", "starfish", "unicorn", "unicorn"} 应打印 unicorn、starfish、hummingbird 各一次。 直观解释：官方 L06 开场先给“笨办法”：对每个元素回看它之前有没有出现过（双重循环），再进阶成“用一个辅助函数查区间”。两种做法都能对，但要么 O(n²) 慢、要么代码绕。直到把元素“扔进一个 Set”——重复项被容器自动吸收——一行核心逻辑解决问题，课堂的用意就是让大家先体会“没有好工具的痛”，再享受 ADT 的甜。 朴素法步骤分解：对第 i 个元素，向前扫描 0..i-1 检查是否重复，无重复才打印——最坏要两两比较 n²/2 次。Set 法：见示例 1。

2. Set：无重复的“成员判断机”

问题定义：需要一种容器回答“某元素在不在里面”，并且保证绝不存两份。 直观解释：数学集合的数据结构版。两个铁律（官方 L06 原话拆解）：① 不允许重复——同一元素插 100 次也只留 1 份；② 不保存插入顺序、也没有下标。所以 Set 的本质是“二元成员判断装置”：一个元素要么是成员，要么不是。 操作/步骤分解（官方 Set ↔ std::set）：

“有序性”与内部机制：打印或遍历 Set 时元素总是按序出现（官方 L06 点名：按 ASCII 序排列——大写字母排在小写前，因为 'A'=65 < 'a'=97）。这不是巧合：官方 Stanford Set 由平衡二叉搜索树（balanced BST）支撑，元素按键有序存放，从而插入、查找、删除都只要 O(log n)。C++ 标准库的 std::set 同样是平衡 BST（红黑树），行为完全一致——本笔记一律用 std 版，与课程的 Set 一一对应。

std::set<string> 内部是二叉搜索树(红黑树), 插入 "starfish" 已存在 → 直接忽略:
           hummingbird
          /            \
      dragon          starfish
                          \
                        unicorn
  遍历(中序)= dragon, hummingbird, starfish, unicorn  ← 天然有序

步骤分解（插入）：从根开始，与当前节点比较大小：小走左、大走右、相等说明重复直接返回——一路下行到空位即挂上新节点。树高约 log₂n，故每次比较 O(log n)。遍历：中序遍历（左—根—右）即得升序序列。

3. Set 的应用：去重与查重

• 全量去重：把 vector 元素全部 insert 进 set，重复被自动吸收；要回 vector 就遍历 set 倒回去（代价：排序后的顺序与原顺序无关）。
• 保留首次出现顺序的去重：set 只当“查重台账”——遍历原 vector，若 count(w)==0 就打印并登记。
• 找重复项：登记“已见过”，第二次见到就报“重复”；再套一个 set 可保证每个重复项只报一次（官方 L06 有整套变体练习）。
• “Set 很快”：官方 L06 强调 Set 操作远比“反复扫 vector 查重”快——后者最坏 O(n²)，Set 版每个元素只花 O(log n) 的树查找，总耗时 O(n log n)。

4. Map：键 → 值 的“活字典”

问题定义：要按“键”快速检索“值”：学号→姓名、ISBN→书名、单词→出现次数。 直观解释：Map 是关联式（associative）结构：每个键唯一、恰好映射一个值。官方 L06 的直观例子：把全班的社保号映射到姓名；喂进一个社保号，吐出一个名字。键集合本身就是一个 Set（键互不相同、按序排列），值是它“名下”挂的东西。 操作/步骤分解：

“探键”行为——官方 L06 的招牌知识点：

1. 查询不存在的键时返回该值类型的默认值（int 得 0、string 得空串）；
2. 用 m[key] 语法查询不存在的键时，map 会把该键加进去并配上默认值——副作用！官方演示：map["Sonia"] 查完，map 里多出一个 “Sonia: 空串”。get(key) 则只返回默认值、不插入。

C++ 标准库忠实复刻了这一对行为：std::map 的 operator[] 找不到键就插入默认值；at(key) 找不到则抛异常（相当于“无副作用查询”，但要小心异常）；count(key) 只回答“在不在”。惯用法：先 count 探键、再 [] 取值，避免误插与异常。 键不可变语义：给已有键赋新值 = 覆盖旧映射（官方：m["Julie"] = "Zelenski" 之后再 m["Julie"] = "Stanford"，旧值被覆盖，size 不变）。 多值关联（键 → 容器）：一个键只能映射一个值，但那个值可以是整个容器！map<string, vector<string>> 让“同名（键）→ 多个姓氏（值容器）”成为可能。官方 L06 强调：取出容器后必须用引用接收（vector<string>& v = m["Julie"]），否则拿到的是拷贝，往里 add 等于白干（练习 2 专门考这一点）。

5. 词频统计与“出现最多的词”

问题定义：给一段文本，统计每个词出现几次；进一步找出出现次数最多的词。 直观解释：官方 L06 用《德古拉》全文演示：map<string,int> 键为单词、值为次数，一行 counts[word]++ 完成“没见过就记 1、见过就加 1”的完整逻辑——因为 [] 对不存在的键先补 0 再自增。要按频率找最热词，遍历键值对维护最大值即可（示例 2）。 命名约定（官方 L06 提及）：map 变量名建议写成“键To值”式，如 wordToFrequency、isbnToTitle，把键值关系直接写进名字；词频表常见命名 counts。

6. 有序 vs 无序：Set/Map 与 HashSet/HashMap 的取舍

问题定义：既然要“超快查找”，为什么课程先教“有序版”而非哈希版？ 直观解释：官方 L06 预告：课程库里同时存在 HashSet/HashMap（无序、基于哈希表，平均 O(1)）与 Set/Map（有序、基于平衡 BST，O(log n)）。四个容器的查找都快到在日常数据上几乎无感；差别在于：有序版保证遍历有序、支持“找前驱/后继、区间”等操作，代价是每次 O(log n)；无序版更快但顺序随机。官方明确“本期只需知道概念差异，哈希实现细节到第 24 讲”。 对照表：

同样插入 {"starfish","unicorn","hummingbird","dragon"}:
  std::set 遍历:    dragon → hummingbird → starfish → unicorn   (有序)
  std::unordered_set 遍历:  顺序随机,每次运行都可能不同

代码示例与实现详解

示例 1：Set 去重——挑战题的标准解法与“保序”变体

// 文件: set_dedupe_demo.cpp
// 演示: std::set 去重(有序输出) 与 保留首次出现顺序的去重
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

// 解法 A: 把元素全扔进 set,重复项自动被吸收; 遍历即得有序去重结果
void printUniqueSorted(const vector<string>& words)
{
    set<string> uniqueSet;                  // 空集合
    for (const string& w : words) {
        uniqueSet.insert(w);                // 重复插入被静默忽略
    }
    for (const string& w : uniqueSet) {     // 按键升序遍历
        cout << w << endl;
    }
}

// 解法 B: 用 set 当“查重台账”,保持元素在原 vector 里的首次出现顺序
void printUniqueInOrder(const vector<string>& words)
{
    set<string> seen;                       // 记录“已见过的词”
    for (const string& w : words) {
        if (seen.count(w) == 0) {           // 首次出现才打印 (count 返回 0 或 1)
            cout << w << endl;
            seen.insert(w);                 // 登记,防止下次再打印
        }
    }
}

int main()
{
    vector<string> creatures = {"unicorn", "starfish", "hummingbird",
                                "starfish", "unicorn", "unicorn"};
    cout << "== 解法 A: 有序去重输出 ==" << endl;
    printUniqueSorted(creatures);           // hummingbird / starfish / unicorn
    cout << "== 解法 B: 保留首次出现顺序 ==" << endl;
    printUniqueInOrder(creatures);          // unicorn / starfish / hummingbird
    return 0;
}

【代码做什么】：解法 A 一字排开地 insert，由 set 自己吞掉重复，遍历输出即升序去重结果；解法 B 用 seen.count(w) == 0 判断“从没见过”，头一回见到才打印并登记。main 用官方 L06 的独角兽/海星/蜂鸟数据验证两种输出的顺序差异。

【实现机制解说】：set::insert 返回 pair<迭代器, bool>，bool 位告知“这次是否真的插入了”（已存在时为 false）——官方练习里“只打印重复项一次”等变体可借它实现。count(w) 对 set 只会返回 0 或 1，因为集合语义禁止重复，用它判断成员关系最直白。复杂度对比：若用 vector 的双重循环去重，最坏 O(n²) 次比较；这里每个词一次树查找 O(log n)，总 O(n log n)。遍历 set 得到的是升序而非插入序，所以解法 A 与解法 B 输出顺序不同——想保序就自己维护“首次出现”逻辑，想让容器代劳排序就接受字典序。

示例 2：Map 词频统计——找“出现最多的词”

// 文件: word_freq_demo.cpp
// 演示: std::map 词频统计、按键序遍历、查找最高频词(官方用《德古拉》全文,
//       这里用内嵌小文本代替文件输入,逻辑完全一致)
#include <iostream>
#include <map>
#include <sstream>   // istringstream: 自动按空白切词
#include <string>
using namespace std;

int main()
{
    // 一段模拟课文(可想象成官方课上打开的 poem.txt / dracula.txt)
    const string text =
        "roses are red butterflies are beautiful "
        "red roses are lovely beautiful butterflies";

    map<string, int> wordToFreq;        // 命名约定: 键To值
    istringstream iss(text);
    string word;
    while (iss >> word) {
        wordToFreq[word]++;             // 探键: 新词自动补 0,再自增
    }

    // (1) 遍历: std::map 的 range-for 每次给出 pair<const 键, 值>
    cout << "== 词频表(按键升序) ==" << endl;
    for (const auto& kv : wordToFreq) {
        cout << kv.first << ": " << kv.second << endl;
    }

    // (2) 找出现次数最多的词(遍历一遍,维护当前冠军)
    string topWord;
    int topFreq = -1;
    for (const auto& kv : wordToFreq) {
        if (kv.second > topFreq) {      // 严格大于: 平手时保留先遇到的
            topWord = kv.first;
            topFreq = kv.second;
        }
    }
    cout << "出现最多的词: \"" << topWord << "\", 共 " << topFreq << " 次" << endl;

    // (3) 探键行为演示: operator[] 会“顺手”插入默认值
    cout << "查不在表里的词 zzz 的次数: " << wordToFreq["zzz"] << endl;
    cout << "副作用? zzz 被插进表了: " << wordToFreq.count("zzz") << " (1=是)" << endl;
    cout << "用 count 探键(无副作用): " << wordToFreq.count("qix") << endl;
    return 0;
}

【代码做什么】：istringstream 按空白把课文切成单词，wordToFreq[word]++ 一行完成“首次出现记 1、再次出现加 1”；随后按键升序打印词频表，再单遍扫描找出最高频词；最后演示 operator[] 探键会插入默认值、count() 无副作用。

【实现机制解说】：词频统计的“魔法”全在 wordToFreq[word]++ 的求值顺序：operator[] 找不到键时先构造 {word, 0} 插入并返回其引用，++ 再把它加到 1；找得到则直接对旧值自增——两行 if/else 压缩成一行。这与官方 Stanford Map 的 m[word]++ 行为一致（官方特别注明 get(word)++ 会编译失败，因为 get 返回的是临时值不可自增）。const auto& kv 中 kv.first 是键、kv.second 是值；auto& 引用遍历避免复制整个 pair。找最高频词是线性扫描：map 已按键排好序，但“最大频率”与键序无关，必须逐对比较——复杂度 O(n)。最后一个知识点是副作用：查 “zzz” 之后表里真的多了 zzz:0；需要“只查不改”就用 count/find（或 at，但要注意它找不到会抛异常）。官方课上跑通《德古拉》全文后还加了“打印出现超过 100 次的词”的阈值筛选，道理与这里完全相同。

示例 3：Map 的多值关联——键 → 容器，以及引用陷阱

// 文件: multivalue_map_demo.cpp
// 演示: map<string, vector<string>> 让一个键关联多个值(值本身是个容器)
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main()
{
    // 课程 → 选课学生名单 (键唯一, 值是一个可增长的 vector)
    map<string, vector<string>> courseToStudents;

    // 关键: 用【引用】接收返回值! 否则拿到拷贝, push_back 改的是副本
    vector<string>& cs106b = courseToStudents["CS106B"];
    cs106b.push_back("Ada");
    cs106b.push_back("Alan");

    // 也可以不建中间变量, 直接链式操作(每次返回的都是同一份引用)
    courseToStudents["CS103"].push_back("Grace");
    courseToStudents["CS103"].push_back("Edsger");

    // 遍历: 键升序; 每个键名下再遍历其 vector
    cout << "== 选课名单(按键升序) ==" << endl;
    for (const auto& kv : courseToStudents) {
        cout << kv.first << ": ";
        for (const string& name : kv.second) {
            cout << name << " ";
        }
        cout << endl;
    }

    // 对照: 若忘记引用, 会发生什么?
    vector<string> copy = courseToStudents["CS106B"];   // 整份拷贝!
    copy.push_back("Linus");                            // 只改了副本
    cout << "CS106B 名单末尾是否多了 Linus? "
         << (courseToStudents["CS106B"].back() == "Linus" ? "是" : "否(拷贝被丢弃)")
         << endl;
    return 0;
}

【代码做什么】：以“课程→学生名单”演示键到容器的映射：用引用接收 operator[] 的返回值后 push_back，真正把学生加进 map 内的 vector；遍历打印时外层按键升序、内层逐个输出名字；最后故意演示“忘写引用”的后果——改动只落在副本上，被悄悄丢弃。

【实现机制解说】：map 的值类型是 vector<string> 时，m[key] 的返回类型是 vector<string>&（引用）。写成 vector<string> v = m["CS106B"] 会触发拷贝构造——复制整条名单；对 v 的任何修改都与 map 无关，函数结束副本销毁，改动蒸发。官方 L06 练习 2 正是这个坑：没写 & 时打印出的名单全是空的。这也是“值语义”的体现：C++ 里普通赋值默认拷贝，想“拿到并操作原件”必须显式用引用或指针。此外注意 kv.second 遍历 vector 时用 const string& name 只读引用，避免每轮复制一个字符串。

复杂度分析

要点：有序容器把“保持有序”内建进每次操作，换来可预期的升序遍历；无序容器放弃顺序换平均常数时间。两者都远快于“在 vector 里线性扫描查重”的 O(n²)。n 不大时差距无所谓，选型口诀：要顺序输出用 set/map，只求快不求序用 unordered 版（官方 L06 亦如此建议）。

关键要点

• Set 是“二元成员机”：同一元素永远只存一份，回答只有“在/不在”，遍历天然升序。
• 有序的代价与回报对称：set/map 每次 O(log n)，换来排序遍历；由平衡 BST（红黑树）支撑。
• map[key] 会“探键即插入”：查不存在的键会顺手塞进一个默认值；只查不改用 count/find。
• 键要“挂”多个值：让值本身成为容器（如 map<string, vector<string>>），且取出时务必用引用接收。
• 词频统计一行流：counts[word]++ = “没见过记 1、见过加 1”；变量命名用 “键To值”，如 wordToFreq。

常见陷阱与注意事项

• 误以为 set 保插入序：set 遍历永远是升序。规避：要保序就去重时自己维护“首次出现”判断。
• map[key] 查询的副作用：读一下不存在的键就污染了表。规避：先 count(key) 再决定是否 [] 取值。
• 拿 map 的容器值时不写引用：vector<string> v = m[k] 是拷贝，改动无效。规避：写 auto& v = m[k]。
• 对 set 用下标：set 没有下标、没有 []。规避：用 count/find 判断成员、range-for 遍历。
• 值覆盖的误判：m[k] = v2 不会新增一对，而是覆盖旧值。规避：先想清楚“覆盖 vs 新增”的语义，必要时先 count。
• 给元素排序的依据想当然：字符串按 ASCII 序排，大写全在小写之前（"Apple" < "banana"）。规避：要“正常字典序”先统一小写再入 set/map。
• 遍历时修改容器：range-for 遍历 set/map 时插入或删除元素会使迭代器失效。规避：先收集要删的键，遍历结束后再删。

思考题（带答案）

问题 1：vector<string> v = {"a","b","a","c","b"}，想把 v 变成无重复版本（顺序随意），代码怎么写？复杂度多少？ 答案：set<string> s(v.begin(), v.end()); v.assign(s.begin(), s.end());——构造 set 自动去重并排序，再倒回 vector。复杂度 O(n log n)（n 次插入 × log n）。要保留原顺序则改为：遍历 v，用 set<string> seen 判重，首次见到的元素 push_back 进新 vector。

问题 2：为什么官方 L06 说 Set/Map 的插入查找“很快”，比“反复扫 vector”快？请给出数量级对比。 答案：vector 里线性查重 n 个元素最坏 O(n²) 次比较；set 每次插入沿树下行 O(log n)，共 O(n log n)。对 n=100 万，前者约 10¹² 次比较（不可行），后者约 2×10⁷ 次（瞬间完成）。树高 log₂n 意味着“规模翻倍只多 1 层比较”——这就是 O(log n) 的威力（下一讲用大 O 记号正式刻画）。

问题 3：写出用 map 统计字符频次的代码片段：给定 string s，统计每个字母出现次数并输出次数最多的字母。 答案：map<char,int> freq; for (char ch : s) freq[ch]++; 然后单遍扫描找最大：char best; int mx=-1; for (auto& kv : freq) if (kv.second > mx) { mx = kv.second; best = kv.first; }。若要忽略大小写/只统计字母，可先 tolower 并用 isalpha 过滤（把示例 2 的“词”换成“字符”即可）。