本讲对应视频《CSP复赛专题11-数据结构3》（43′42″），讲解 C++ STL 的关联容器： set / multiset / pair / map，并拓展 unordered_map。学生已经掌握了数组、vector、 栈与队列，本讲要解决的是他们第一次遇到的真实困境："想用下标，但下标不是小整数" （编号到 20 亿）、"下标是字符串"（姓名→分数）、"还要顺带排好序"。
学情上的典型困难：① 习惯 a[x] 之后，遇到大编号仍想开数组；
② 不知道 mp[key] 会插入 key，写出"边查边改 size"的隐蔽 bug；
③ 以为 map 比数组"高级"就到处乱用，反而把 O(1) 写成 O(log n)。
insert/find/count/erase，能说出各操作的 O(log n) 代价；
能独立完成"明明的随机数"与"主要成分"两道真题。① set 的去重有序与迭代器用法；② map 的 [] 陷阱；
③ lower_bound / upper_bound 的语义；④ 两道真题的建模。
① 为什么 [] 会插入元素（它返回引用，必须能写）；
② 双向迭代器不支持 <；③ 摩尔投票"最后还要数一遍"的必要性。
| 环节 | 时间 | 教师活动 | 学生活动 | 设计意图 |
|---|---|---|---|---|
| ① 动机引入 | 4′ | 第 3 页：三种"下标用不了"的时刻（编号 2e9 / 姓名是字符串 / 还要排序）， 追问"这时候数组还能怎么办" | 回答并说出困难 | 用真实困境建立必要性 |
| ② set 天性 | 8′ | 第 4 页动画：逐个插入，让学生先猜下一个数会落在哪， 再点揭示；重复的被吞掉时追问 insert 返回什么 | 预测落点与返回值 | 把"去重 + 有序"变成可预测过程 |
| ③ 二分定位 | 6′ | 第 5 页动画单步二分，讲清 lower/upper 的"插入位置记忆法" | 口头报 left / right / mid | 把 O(log n) 落到具体次数 |
| ④ map 与 [] 陷阱 | 8′ | 第 6 页动画：重点点「用 [] 访问不存在的人」， 让学生亲眼看到 size 变大 | 观察 size 变化，说出正确判存在写法 | 本讲最高频 bug 的现场暴露 |
| ⑤ 代价对比 | 3′ | 第 7 页：切换 n=16 / 1024 / 100000，看比较次数差距 | 读数字并感受量级 | 建立复杂度直觉 |
| ⑥ 例题1 | 7′ | 第 8–9 页：动画插完 + 代码走读，强调迭代器用 !=、取值用 *it |
跟着写一遍遍历 | 拿下真题 |
| ⑦ 例题2 | 9′ | 第 10–11 页：两种模式对照，map 计数 → 摩尔投票， 追问"抵消剩下的就一定超过一半吗" | 回答并说明为什么要再数一遍 | 把 O(1) 空间解法讲透 |
问：直接讲 unordered_map 不是更快更好吗，为什么要花时间讲 map？
答：因为复赛里"要按 key 顺序输出""要找第一个 ≥ x"这类需求非常常见，
unordered_map 做不到。而且 map 的 O(log n) 是稳定保证，unordered_map 的最坏情况是 O(n)。
先掌握 map，再按需求降级到 unordered_map，才是可靠的选型路径。