Appearance
附录 B · 高频考点 · 易错点 · 速查总表
本附录由全书九章的"考点总结表"聚合而成，星标为考频与重要度。用途：考前 30 分钟过一遍。
一、五星考点速览（⭐⭐⭐⭐⭐，必考级）
| 考点 | 出处章 | 一句话结论 |
|---|---|---|
| vector 底层是连续内存，支持随机访问 O(1) | 第2章 | 用下标访问是 O(1)，中间插删是 O(n) |
size() ≤ capacity()，reserve 不改 size | 第2章 | 扩容会重新分配 + 拷贝，迭代器全部失效 |
list 不支持 []，任意位置插删 O(1) | 第3章 | 前提：已持有该位置的迭代器 |
| list 迭代器稳定，插入不失效 | 第3章 | vector 插入可能全部失效 |
| deque 双端操作 O(1) 且支持随机访问 | 第4章 | 无 capacity() / reserve() |
| set 底层红黑树，有序 + 去重，O(log n) | 第5章 | unordered_set 是哈希表，平均 O(1) 但无序 |
multiset::erase(值) 删除所有等值元素 | 第5章 | 只删一个要用 find 拿迭代器再 erase |
| 关联式容器的元素 / key 不可修改 | 第5、6章 | 想改就先删再插 |
map 元素是 pair<const Key, T> | 第6章 | first 是 key，second 是 value |
map[key] 访问不存在的 key 会自动插入 | 第6章 | 只想查找请用 find，否则会污染容器 |
mp[x]++ 是计数统计的标准写法 | 第6章 | map 遍历天然按 key 升序 |
stack 是 LIFO，pop() 不返回元素 | 第7章 | 取栈顶用 top()，判空后再访问 |
queue 是 FIFO，front() / back() 别搞反 | 第8章 | BFS 的标准载体 |
stack / queue 无迭代器、不可遍历、无 clear() | 第7、8章 | 清空用循环 pop 或重新赋值 |
priority_queue 默认大顶堆（底层 vector + less） | 第9章 | 小顶堆要写 greater<int> |
| priority_queue 只能访问堆顶，push/pop 是 O(log n) | 第9章 | TopK 用小顶堆维护 |
pair 的 first / second 与字典序比较 | 第10章 | 先比 first，相等再比 second |
二、时间复杂度速查表
| 容器 | 随机访问 | 头插/头删 | 尾插/尾删 | 中间插删 | 查找 | 底层 |
|---|---|---|---|---|---|---|
vector | O(1) | O(n) | 均摊 O(1) | O(n) | O(n) | 连续数组 |
list | ❌ O(n) | O(1) | O(1) | O(1)（有迭代器） | O(n) | 双向链表 |
deque | O(1) | O(1) | O(1) | O(n) | O(n) | 分段连续 |
set / map | ❌ | — | — | O(log n) | O(log n) | 红黑树 |
multiset / multimap | ❌ | — | — | O(log n) | O(log n) | 红黑树 |
unordered_set / unordered_map | ❌ | — | — | 平均 O(1) | 平均 O(1) | 哈希表 |
stack | ❌ | — | 顶 O(1) | ❌ | ❌ | 默认 deque |
queue | ❌ | 头 O(1) | 尾 O(1) | ❌ | ❌ | 默认 deque |
priority_queue | ❌ | — | O(log n) | ❌ | 仅堆顶 O(1) | 二叉堆 |
注：
unordered_*的最坏情况为 O(n)（哈希冲突），平均为 O(1)。
三、头文件与声明速查
| 容器 | 头文件 | 标准声明写法 |
|---|---|---|
vector | <vector> | vector<int> v; |
list | <list> | list<int> l; |
deque | <deque> | deque<int> dq; |
set | <set> | set<int> s; |
multiset | <set> | multiset<int> ms; |
unordered_set | <unordered_set> | unordered_set<int> us; |
map | <map> | map<string, int> mp; |
multimap | <map> | multimap<string, int> mmp; |
unordered_map | <unordered_map> | unordered_map<string, int> ump; |
stack | <stack> | stack<int> st; |
queue | <queue> | queue<int> q; |
priority_queue | <queue> | priority_queue<int> pq;（大顶堆） |
pair | <utility> | pair<int, string> p; |
算法（sort 等） | <algorithm> | sort(v.begin(), v.end()); |
四、常用成员函数速查
| 类别 | 函数 | 适用容器 |
|---|---|---|
| 容量 | size() / empty() | 全部 |
| 容量 | capacity() / reserve(n) | vector（string 亦有） |
| 容量 | resize(n) | vector、deque、list 等序列式容器及 string |
| 首尾 | front() / back() | vector、list、deque、queue |
| 插入 | push_back(x) / insert(pos, x) | vector、list、deque、关联式用 insert(x) |
| 插入 | push_front(x) | list、deque |
| 删除 | pop_back() / pop_front() | vector、list、deque |
| 删除 | erase(it) / erase(值) / clear() | vector、list、deque、关联式（适配器无 clear） |
| 查找 | find(x)（成员函数） | set/map 系列，O(log n) 或平均 O(1) |
| 查找 | find(b, e, x)（算法） | vector、list、deque，O(n) |
| 计数 | count(x) | set/map 系列 |
| 区间 | lower_bound(x) / upper_bound(x) | 有序容器（set/map）成员函数 |
| 适配器 | push() / pop() / top() | stack |
| 适配器 | push() / pop() / front() / back() | queue |
| 适配器 | push() / pop() / top() | priority_queue |
| 其他 | remove(值) / sort() / unique() / merge() | list（成员函数版） |
五、易错点 TOP 20
| # | 易错点 | 正确认知 |
|---|---|---|
| 1 | 以为所有容器都能用 [] | list、set、map（除 map[key] 语义）、适配器都不支持下标随机访问 |
| 2 | 以为 map[key] 只是查找 | 会插入一个默认值的元素，改变 size() |
| 3 | 以为 pop() 会返回弹出的元素 | pop() 返回 void，必须先 top() 再 pop() |
| 4 | 空容器直接 top() / front() | 行为未定义，必须先判 empty() |
| 5 | 用 sort() 排 list | list 有成员函数 sort()，algorithm 的 sort 需要随机访问迭代器 |
| 6 | unique() 后以为已去重 | unique 只是把重复元素挪到尾部，必须再 erase |
| 7 | vector 扩容后还用旧迭代器 | 扩容会重新分配内存，所有迭代器/引用/指针失效 |
| 8 | 试图修改 set 的元素、map 的 key | 不可修改，需先删后插 |
| 9 | multiset::erase(值) 以为只删一个 | 删除所有等值元素 |
| 10 | 遍历 stack / queue | 适配器无迭代器，无法遍历 |
| 11 | 以为 stack 默认是 vector | 默认底层是 deque |
| 12 | 以为 priority_queue 默认小顶堆 | 默认大顶堆，小顶堆要写 greater<T> |
| 13 | 以为 priority_queue 的 push/pop 是 O(1) | 实为 O(log n)（堆的上滤/下滤） |
| 14 | pair 比较时搞反顺序 | 先比 first，first 相等才比 second（字典序） |
| 15 | 以为 reserve 会改变 size | reserve 只分配容量，resize 才改变元素个数 |
| 16 | 以为 deque 完全连续 | 是分段连续，靠中控数组管理 |
| 17 | list 的 remove 与算法 remove 混淆 | list::remove(值) 真正删除；算法版只移动 |
| 18 | unordered_* 以为一定比 map 快 | 平均 O(1)，但哈希冲突时退化，且无序、开销大 |
| 19 | 忘记判空就 pop | 空容器 pop 是未定义行为 |
| 20 | 一律用 vector 硬套 | 应按"访问方式 + 插入位置 + 是否需要有序/去重"选型 |
六、选型决策速查
需要遍历吗？
├─ 否 → 只需取一头？ ── stack（一头）/ queue（两头）/ priority_queue（取最值）
└─ 是 → 需要按 key 查找或去重吗？
├─ 是 → 需要有序吗？
│ ├─ 是 → set / map（O(log n)，红黑树）
│ └─ 否 → unordered_set / unordered_map（平均 O(1)，哈希表）
│ └─ 允许重复？→ multi_* / unordered_multi_*
└─ 否 → 插入删除主要发生在哪里？
├─ 尾部 → vector
├─ 头尾都有 → deque
└─ 中间频繁 → list考点权重以各章"考点总结表"为准；易错点按出现频次归纳。