map学习总结

2026/8/17 1:09:20 拓冰建站浏览量

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 的基本操作、排序、二分、遍历就都熟了。

建站实战干货