目录
- map 学习总结
- 1. map 是什么
- 2. 定义与初始化
- 3. 核心操作一览
- 4. 增删查改实战
- 5. 插入方式的选择（重点）
- 6. 排序：map 的"排序"由比较器决定
- 7. 二分查找：lower_bound / upper_bound / equal_range
- 8. 迭代器的特点
- 9. map 与 unordered_map、multimap 的对比
- 10. 自定义类型做 key
- 11. 常见坑汇总
- 12. 实战：词频统计（map 最经典的场景）
- 13. 自测练习
map 学习总结
std::map 是 C++ 标准库中最常用的关联容器之一，本文从零到熟练梳理它的所有核心用法。
1. map 是什么
- 存储键值对（key -> value），每个 key 唯一。
- 底层是红黑树（平衡二叉搜索树），插入、查找、删除都是 O(log n)。
- 自动按 key 排序（默认升序），遍历时天然有序。
- 属于"有序关联容器"，头文件
<map>。
#include <map>
#include <string>map<string, int> m; // key 是 string，value 是 int
对比记忆：vector 是"按下标排成一排"的顺序容器，map 是"按 key 组织成树"的关联容器。
2. 定义与初始化
#include <map>
#include <string>
using namespace std;// 1. 空 map
map<int, string> m1;// 2. 初始化列表
map<int, string> m2{{1, "one"}, {2, "two"}, {3, "three"}};// 3. 指定比较器（改变排序规则，见第 6 节）
map<int, string, greater<int>> m3; // 按 key 降序// 4. 从其他容器构造
vector<pair<int, string>> v{{1, "a"}, {2, "b"}};
map<int, string> m4(v.begin(), v.end());// 5. 拷贝构造
map<int, string> m5(m2);
注意：map 的元素类型是 pair<const Key, T>，key 是 const 的。
3. 核心操作一览
| 操作 | 写法 | 说明 | 复杂度 |
|---|---|---|---|
| 插入 | m.insert({k, v}) |
key 已存在则不插入，返回 pair<iterator, bool> |
O(log n) |
| 插入/更新 | m[k] = v |
key 不存在时先默认构造再赋值 | O(log n) |
| 插入/更新 | m.insert_or_assign(k, v) |
C++17，已存在则覆盖 | O(log n) |
| 查找 | m.find(k) |
返回迭代器，未找到返回 end() |
O(log n) |
| 计数 | m.count(k) |
返回 0 或 1（判断是否存在） | O(log n) |
| 判断存在 | m.contains(k) |
C++20，直接返回 bool | O(log n) |
| 访问 | m.at(k) |
key 不存在抛 out_of_range 异常 |
O(log n) |
| 删除 | m.erase(k) |
按 key 删除，返回删除个数 | O(log n) |
| 删除 | m.erase(it) |
按迭代器删除，返回下一个迭代器 | O(1) 均摊 |
| 二分查找 | m.lower_bound(k) |
第一个 key >= k 的迭代器 | O(log n) |
| 二分查找 | m.upper_bound(k) |
第一个 key > k 的迭代器 | O(log n) |
| 二分查找 | m.equal_range(k) |
返回 pair(lower_bound, upper_bound) |
O(log n) |
| 遍历 | for (auto& [k, v] : m) |
C++17 结构化绑定 | O(n) |
4. 增删查改实战
#include <iostream>
#include <map>
#include <string>
using namespace std;int main() {map<string, int> m;// ===== 插入 =====auto ret = m.insert({"apple", 3});cout << ret.second << endl; // 1，插入成功ret = m.insert({"apple", 5});cout << ret.second << endl; // 0，key 已存在，插入失败，value 不变// ===== 插入/更新 =====m["banana"] = 2; // 不存在，插入 {"banana", 2}m["apple"] = 10; // 已存在，更新为 10m.insert_or_assign("cherry", 1); // C++17，不存在则插入// ===== 访问 =====cout << m["apple"] << endl; // 10cout << m.at("banana") << endl; // 2// cout << m.at("none") << endl; // 抛 out_of_range 异常// ===== 查找 =====auto it = m.find("apple");if (it != m.end()) {cout << it->first << ": " << it->second << endl; // apple: 10}cout << m.count("apple") << endl; // 1// m.contains("apple") // C++20，等价于 count != 0// ===== 遍历（C++17 结构化绑定） =====for (auto& [k, v] : m) {cout << k << ": " << v << endl; // 按 key 升序输出}// 输出：// apple: 10// banana: 2// cherry: 1// ===== 删除 =====m.erase("banana"); // 按 key 删除，返回 1m.erase(m.begin()); // 按迭代器删除，返回下一个迭代器m.clear(); // 清空所有元素cout << m.size() << endl; // 0return 0;
}
5. 插入方式的选择（重点）
operator[] 与 insert 的本质区别：
m["key"]; // key 不存在时，会【默认构造】一个 value 插入进去！
m.insert({"key", v}); // key 存在时不插入，不覆盖
- 用
[]做查找是危险的：只是"读"也会插入一个默认值（value 类型必须可默认构造）。 - 只想插入不覆盖 → 用
insert； - 想插入或更新 → 用
[]或insert_or_assign； - 不想默认构造（构造开销大）→ 用
try_emplace（C++17）。
map<string, vector<int>> m;
m["nums"]; // 直接插入一个空 vector，无意义且浪费
6. 排序：map 的"排序"由比较器决定
map 在插入时就按 key 排好序，之后不能动态改。排序规则在创建时通过第三个模板参数指定：
#include <map>
#include <functional>
#include <string>
using namespace std;// 默认：key 升序
map<int, string> m1;// key 降序
map<int, string, greater<int>> m2;// 自定义比较器（函数对象）
struct Cmp {bool operator()(const string& a, const string& b) const {return a.size() < b.size(); // 按字符串长度排序}
};
map<string, int, Cmp> m3;// C++20：lambda 作为比较器
auto cmp = [](int a, int b) { return a > b; };
map<int, int, decltype(cmp)> m4(cmp);
关键限制：
- 比较器必须是严格弱序（严格小于关系：反自反、非对称、传递）。
- 创建后不能换比较器，想换顺序只能新建 map 再插入：
map<int, string, greater<int>> m2(m1.begin(), m1.end());
- map 只按 key 排序，想按 value 排序必须拷到
vector再sort：
map<string, int> m{{"banana", 3}, {"apple", 1}, {"cherry", 2}};
vector<pair<string, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), [](auto& a, auto& b) {return a.second < b.second; // 按 value 升序
});
7. 二分查找：lower_bound / upper_bound / equal_range
map 天然有序，可以直接二分，注意查找的对象是 key 区间：
map<int, string> m{{1, "a"}, {3, "c"}, {5, "e"}, {7, "g"}};auto it1 = m.lower_bound(4); // 第一个 key >= 4 的元素 -> {5, "e"}
auto it2 = m.upper_bound(4); // 第一个 key > 4 的元素 -> {5, "e"}
auto it3 = m.lower_bound(3); // -> {3, "c"}
auto it4 = m.upper_bound(3); // -> {5, "e"}// equal_range 同时拿到 [lower, upper)，常用来批量处理一段 key
auto [lo, hi] = m.equal_range(3); // 覆盖 key == 3 的区间（对 map 只有一个元素）
for (auto it = lo; it != hi; ++it) {cout << it->first << endl;
}
小技巧：equal_range 配合 multimap 才是真正的"批量取同 key 元素"场景（见第 9 节）。
8. 迭代器的特点
- map 的迭代器是双向迭代器：只支持
++/--，不支持it + n（vector 才可以）。 it->first是 key，const 的，不可修改；it->second是 value，可以修改。- 删除元素只会使指向被删元素的迭代器失效，其它迭代器不受影响，所以可以边遍历边删：
for (auto it = m.begin(); it != m.end();) {if (it->second == 0) it = m.erase(it); // erase 返回下一个迭代器else ++it;
}
9. map 与 unordered_map、multimap 的对比
map |
unordered_map |
multimap |
|
|---|---|---|---|
| 底层 | 红黑树 | 哈希表 | 红黑树 |
| 有序 | 按 key 有序 | 无序 | 按 key 有序 |
| key 重复 | 不允许 | 不允许 | 允许 |
| 复杂度 | 插入/查找/删除 O(log n) | 平均 O(1) | O(log n) |
operator[] |
有（会默认插入） | 有 | 没有 |
| 适用场景 | 需要有序、范围查询、求前驱后继 | 只求查找速度，不关心顺序 | 一个 key 对应多个值 |
#include <unordered_map>
unordered_map<string, int> um; // 查找最快，但遍历顺序不确定#include <map>
multimap<string, int> mm;
mm.insert({"apple", 1});
mm.insert({"apple", 2}); // 允许重复 keyauto [lo, hi] = mm.equal_range("apple"); // 取出所有 "apple" 的元素
for (auto it = lo; it != hi; ++it) cout << it->second << " "; // 1 2
选择建议：要排序/区间查询用 map，只追求 O(1) 查找用 unordered_map。
10. 自定义类型做 key
key 必须能"比较大小"，所以自定义类型要重载 operator<（满足严格弱序）：
#include <map>
#include <string>
using namespace std;struct Student {string name;int score;bool operator<(const Student& other) const { // 必须 constreturn score < other.score; // 按分数排序}
};map<Student, string> m;
m.insert({{"Alice", 90}, "A班"});
m.insert({{"Bob", 85}, "B班"});
// 遍历时按 score 升序：Bob(85) -> Alice(90)
11. 常见坑汇总
[]查找会误插入：if (m["key"] == 0)会在 key 不存在时插入默认值。判断存在用find/count/contains。at()访问不存在的 key 会抛异常，[]不会（它插入）。调试用at，快速写用[]，但要小心。- key 是 const：迭代器不能改 key；
set/map因此无法使用unique、remove、sort等会改元素的算法（详见《C++容器算法》笔记）。 - 自定义 key 忘了写
operator<→ 编译报错。 - 比较器不满足严格弱序（如
a <= b）→ 行为未定义，树可能坏掉。 - 遍历时修改 key：不行，编译器直接报错（
it->first是 const）。 - map 的迭代器是双向的，别写
it + 1。 - 不要用
[]读一个构造开销很大的 value 类型（如vector、string），会白白默认构造一次。
12. 实战：词频统计（map 最经典的场景）
#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;int main() {string text = "apple banana apple cherry banana apple";istringstream iss(text);string word;// 1. 统计词频：key 不存在时 [] 会插入默认值 0，再 +1map<string, int> freq;while (iss >> word) {freq[word]++;}// 2. map 默认按 key 排序，按词频降序需要拷到 vectorvector<pair<string, int>> v(freq.begin(), freq.end());sort(v.begin(), v.end(), [](auto& a, auto& b) {return a.second > b.second; // 词频降序，相同则保持 key 升序});// 3. 输出for (auto& [w, c] : v) {cout << w << ": " << c << endl;}// 输出：// apple: 3// banana: 2// cherry: 1return 0;
}
13. 自测练习
- 统计一段文字中每个字符出现的次数，按出现次数降序输出。
- 给定数组，找出第一个重复出现的元素（map 记录元素是否见过）。
- 两个 map 中 key 相同的 value 相加，结果存到一个新 map 中。
- 找出一组学生成绩中分数最高的学生姓名（map<name, score> + 遍历比较）。
- 用
multimap实现"班级 -> 学生"的分组存储，并打印每个班级的所有学生。 - 写一个
map<int, int>，用lower_bound找出第一个大于等于x的 key。
练完这 6 题，map 的基本操作、排序、二分、遍历就都熟了。