2026/3/27

一、std::map 核心知识点

1. 基本特性

• 键值对存储：map<KeyType, ValueType>，键唯一、自动升序排序。
• 底层：红黑树，插入/删除/查找均为 $O(\log n)$。
• 键不可重复，重复插入会覆盖旧值。

2. 高频操作

操作	代码示例	说明
插入	mp[key] = val / mp.insert({key, val})	[] 会自动创建不存在的键
访问	mp[key] / mp.at(key)	at() 不存在会抛异常，更安全
遍历	for (auto& p : mp) { p.first; p.second; }	.first 是键，.second 是值（自带，无需定义）
查找	mp.find(key) / mp.count(key)	find() 返回迭代器；count() 返回 1/0（存在/不存在）
删除	mp.erase(key) / mp.erase(it)	按键删除或按迭代器删除

3. 典型应用

• 统计数组元素出现次数：map<int, int> cnt; for (int x : arr) cnt[x]++;
• 数值映射到位置：mp[瓶子数] = 位置编号，快速查询。

---

二、std::queue 核心知识点

1. 基本特性

• 先进先出（FIFO）：队尾进，队头出。
• 只能访问队头/队尾，不能随机访问或遍历。

2. 高频操作

操作	代码示例	说明
入队	q.push(x)	向队尾添加元素
取队头	q.front()	仅读取，不删除
出队	q.pop()	删除队头，无返回值
判空/大小	q.empty() / q.size()	必须先判空再调用 front()/pop()

3. 典型应用

• 模拟内存/缓存（FIFO 页面置换）：push 新元素，满了就 pop 队头。
• 遍历查找元素：必须 front() → pop() → 判断 → push() 放回，循环 size 次。

4. 函数传参

• 必须传引用：void func(queue<int> &q)，否则会复制一份，原队列不变。
• 只读场景：void func(const queue<int> &q)。

---

三、std::priority_queue 核心知识点

1. 基本特性

• 优先队列：默认大顶堆（最大元素在队头），自动排序。
• 底层：堆结构，插入/删除均为 $O(\log n)$。

2. 高频操作

操作	代码示例	说明
入队	q.push(x)	自动调整堆结构
取队头	q.top()	注意：不是 front()！
出队	q.pop()	删除队头（最大/最小元素）
判空/大小	q.empty() / q.size()	同 queue

3. 堆类型切换

• 大顶堆（默认）：priority_queue<int> q;
• 小顶堆：priority_queue<int, vector<int>, greater<int>> q;

4. 典型应用

• 合并果子（哈夫曼树）：每次取最小两堆合并，用小顶堆实现。
• 贪心算法、Dijkstra 最短路。

---

四、std::set 核心知识点

1. 基本特性

• 有序集合：元素唯一、自动升序排序。
• 底层：红黑树，插入/删除/查找均为 $O(\log n)$。
• 不能随机访问，只能用迭代器遍历。

2. 高频操作

操作	代码示例	说明
插入	s.insert(x)	已存在则不插入
查找	s.find(x) / s.count(x)	同 map
删除	s.erase(x) / s.erase(it)	同 map
边界查找	s.lower_bound(x) / s.upper_bound(x)	找第一个 ≥x / >x 的元素
前驱/后继	prev(it) / next(it)	找迭代器的前/后一个元素

3. 典型应用

• 木材仓库问题：快速查找最接近目标值的元素，比较前驱和后继的差值。
• 去重 + 自动排序。

---

五、std::string::find 核心知识点

1. 基本用法

size_t pos = str.find(目标);       // 从开头找
size_t pos = str.find(目标, 起始位置); // 从指定位置开始找

• 返回值：找到返回下标（从0开始），找不到返回 string::npos。
• 判断是否包含：if (str.find(x) != string::npos)。

2. 注意事项

• 只返回第一次出现的位置。
• 区分大小写。

1. 变量名冲突：不要用 count 作为变量名（STL 有同名函数）。
2. 容器访问越界：调用 front()/pop()/top() 前必须先 empty() 判空。
3. 循环队列查找：必须先保存 size = q.size()，再循环 size 次，否则队列大小变化会导致死循环。
4. 函数传参：queue/map/set 等容器传参必须用引用 &，否则会复制副本。
5. 数据范围：数值超过 int 范围时（如 $10^9$），要用 long long 避免溢出。
6. map vs unordered_map：
   • 需要有序 → map
   • 只需要快速查找 → unordered_map
7. queue vs priority_queue：
   • 先进先出 → queue
   • 需要按优先级出队 → priority_queue