第6章 map 系列容器详解

map系列容器是STL中核心的关联式容器，与set系列（值为关键字）不同，map以「键值对（key-value）」为存储单元，核心作用是实现“关键字映射”，即通过唯一的key（关键字）对应唯一的value（值），底层基于红黑树实现，支持高效的查找、插入和删除操作，是日常开发和算法题中常用的映射工具。

---

🎯 本章学习目标

学完本章，你将能够：

1. 理解 map 的键值对（key-value）存储模型
2. 掌握 map 和 unordered_map 的区别与选型
3. 熟练使用 map 的插入、查找、删除、修改等操作
4. 理解 map 元素是 pair 类型，掌握 first/second 访问
5. 掌握 [] 操作符的插入与修改功能及注意事项
6. 了解 multimap 和 unordered_multimap 的用法
7. 理解 map 中 key 不可修改的原因
8. 能用 map 解决统计次数、字典映射等经典问题

---

🗺️ 本章知识图谱

map 系列容器
├── 四大容器
│   ├── map（有序、key唯一、红黑树）
│   ├── unordered_map（无序、key唯一、哈希表）
│   ├── multimap（有序、key可重复、红黑树）
│   └── unordered_multimap（无序、key可重复、哈希表）
├── 核心操作
│   ├── insert / emplace（插入）
│   ├── [] 操作符（插入+修改）
│   ├── find（查找）
│   ├── erase（删除）
│   ├── count（计数）
│   └── 遍历（first/second）
├── 元素类型
│   └── pair<key, value>
├── 底层实现
│   ├── 红黑树（map/multimap）
│   └── 哈希表（unordered_*）
├── 注意事项
│   ├── key 不可修改
│   ├── multimap 无 []
│   └── 头文件区分
└── 选型与场景

---

🍎 生活比喻：map 就像一本字典——拼音是 key，汉字是 value。你通过拼音（key）快速找到对应的汉字（value），字典里的词条按拼音顺序排列（map 有序）。unordered_map 就像散乱的单词卡，不按顺序排，但找起来特别快（靠索引）。multimap 就像多义词词典——一个拼音（key）可以对应多个汉字（value）。

一、map核心特性

map系列容器主要分为两类：map 和 unordered_map，与set系列对应，二者核心区别在于「有序性」和「底层实现」，具体特性对比如下：

容器类型	有序性	关键字（key）是否唯一	底层实现	核心效率（插入/查找/删除）	核心优势
map	✅ 是（默认升序）	✅ 唯一	红黑树（平衡二叉搜索树）	O(log n)（稳定）	有序映射，支持按key排序、范围查找
unordered_map	❌ 否	✅ 唯一	哈希表	O(1)（平均），最坏O(n)	查找速度极快，适合高频映射查询

补充：与map对应的“允许重复key”的容器为 multimap（有序）和 unordered_multimap（无序），核心区别是key可重复，value可不同，用法与map基本一致，仅插入和查找时需注意key的重复性。

二、map与set的核心区别

很多初学者会混淆map和set，二者同属关联式容器，但核心用途不同，具体区别如下：

1. 存储单元不同：set仅存储“值”（value），map存储“键值对（key-value）”；
2. 核心作用不同：set侧重“去重、排序、查找”，map侧重“关键字映射”（通过key找value）；
3. 关键字不同：set的关键字就是自身的值，map的关键字是独立的key，与value分离。

三、逐一详解：map系列容器用法

1. map：有序、key唯一的键值对映射

map是最常用的map系列容器，key唯一，插入后会自动按key升序排列，支持通过key快速查找、修改对应的value。

基础用法（完整代码）

#include <iostream>
#include <map>  // map的头文件
using namespace std;

int main() {
    // 1. 定义：key为int类型，value为string类型（默认key升序）
    map<int, string> mp;
    
    // 2. 插入元素（三种方式，推荐前两种）
    mp.insert(pair<int, string>(1, "apple"));  // 方式1：pair插入
    mp.emplace(2, "banana");                   // 方式2：emplace插入（更高效）
    mp[3] = "orange";                          // 方式3：[]赋值插入（不存在则创建，存在则修改）
    
    // 注意：key唯一，重复插入会失败
    mp.insert(pair<int, string>(1, "pear"));  // 重复key，插入无效
    
    // 3. 遍历（自动按key升序）
    cout << "map遍历（按key升序）：" << endl;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        // it->first 是key，it->second 是value
        cout << "key：" << it->first << "，value：" << it->second << endl;
    }
    // 输出：
    // key：1，value：apple
    // key：2，value：banana
    // key：3，value：orange
    
    // 4. 查找元素（通过key查找）
    auto find_it = mp.find(2);  // 查找key=2的元素，返回迭代器
    if (find_it != mp.end()) {
        cout << "\n找到key=2，对应的value：" << find_it->second << endl;
    } else {
        cout << "\n未找到key=2" << endl;
    }
    
    // 5. 修改value（通过key修改）
    mp[2] = "grape";  // 直接通过[]修改key对应的value
    cout << "\n修改后key=2的value：" << mp[2] << endl;  // 输出：grape
    
    // 6. 删除元素（三种方式）
    mp.erase(3);                // 方式1：通过key删除
    // mp.erase(find_it);        // 方式2：通过迭代器删除（删除key=2）
    // mp.erase(mp.begin(), mp.end());  // 方式3：删除指定范围元素
    
    // 7. 其他常用操作
    cout << "\nmap中元素个数：" << mp.size() << endl;  // 输出：2（删除了key=3）
    if (mp.empty()) {
        cout << "map为空" << endl;
    } else {
        cout << "map非空" << endl;
    }
    mp.clear();  // 清空map
    return 0;
}

补充：key 降序排列与 set 类似，map 也支持自定义排序，实现 key 降序：

// 定义降序排序规则
struct cmp {
    bool operator()(const int& a, const int& b) const {
        return a > b;  // key降序
    }
};

map<int, string, cmp> mp;  // 降序map
mp.emplace(1, "apple");
mp.emplace(2, "banana");
// 遍历输出：key：2，value：banana；key：1，value：apple

2. unordered_map：无序、key 唯一的键值对映射

unordered_map 与 map 的核心区别是「无序」，底层基于哈希表实现，查找、插入、删除的平均效率比 map 高，但不支持排序，key 同样唯一。

基础用法（核心代码）

#include <iostream>
#include <unordered_map>  // unordered_map的头文件
using namespace std;

int main() {
    // 1. 定义：key为string类型，value为int类型（无序）
    unordered_map<string, int> umap;
    
    // 2. 插入元素（与map用法一致）
    umap.emplace("apple", 10);
    umap.emplace("banana", 20);
    umap["orange"] = 15;
    umap.emplace("apple", 12);  // 重复key，插入无效
    
    // 3. 遍历（无序，每次运行顺序可能不同）
    cout << "unordered_map遍历（无序）：" << endl;
    for (auto& pair : umap) {
        cout << "key：" << pair.first << "，value：" << pair.second << endl;
    }
    // 示例输出（顺序不固定）：
    // key：banana，value：20
    // key：apple，value：10
    // key：orange，value：15
    
    // 4. 查找、修改、删除（与map用法一致）
    auto find_it = umap.find("orange");
    if (find_it != umap.end()) {
        cout << "\n找到key=orange，value：" << find_it->second << endl;
    }
    umap["orange"] = 18;  // 修改value
    umap.erase("banana"); // 删除key=banana
    
    // 5. 其他常用操作
    cout << "\nunordered_map元素个数：" << umap.size() << endl;  // 输出：2
    umap.clear();
    return 0;
}

3. multimap：有序、key 可重复的键值对映射

multimap 与 map 的核心区别是「key 可重复」，底层同样是红黑树，支持按 key 升序排列，适合需要多个相同 key 对应不同 value 的场景（如：一个学生对应多门课程成绩）。

基础用法（核心代码）

#include <iostream>
#include <map>
using namespace std;

int main() {
    multimap<string, int> mmp;  // key可重复，有序
    
    // 插入相同key的不同value
    mmp.emplace("张三", 90);
    mmp.emplace("张三", 85);
    mmp.emplace("李四", 95);
    
    // 遍历（按key升序，相同key的value按插入顺序排列）
    cout << "multimap遍历：" << endl;
    for (auto& pair : mmp) {
        cout << "key：" << pair.first << "，value：" << pair.second << endl;
    }
    // 输出：
    // key：张三，value：90
    // key：张三，value：85
    // key：李四，value：95
    
    // 统计相同key的个数
    cout << "\n张三的成绩个数：" << mmp.count("张三") << endl;  // 输出：2
    
    // 查找所有key=张三的元素
    auto range = mmp.equal_range("张三");
    cout << "\n张三的所有成绩：";
    for (auto it = range.first; it != range.second; it++) {
        cout << it->second << " ";
    }
    cout << endl;  // 输出：90 85
    
    return 0;
}

4. unordered_multimap：无序、key 可重复的键值对映射

unordered_multimap 与 unordered_map 的核心区别是「key 可重复」，底层基于哈希表实现，无序，适合需要快速统计相同 key 对应多个 value 的场景，用法与 multimap 类似，仅无排序功能。

四、常用操作汇总（map 系列通用）

操作	语法	说明
插入	insert(pair) / emplace(key, value) / [key] = value	emplace 效率最高，[] 可用于插入和修改
查找	find(key)	返回指向该 key 的迭代器，找不到返回 end ()
统计个数	count(key)	返回该 key 的个数（map/unordered_map 只能是 0 或 1）
修改 value	map[key] = new_value	仅 map/unordered_map 支持，multimap 需通过迭代器修改
删除	erase (key) /erase (迭代器) /erase (范围)	按 key 删除时，multimap 会删除所有该 key 的元素
清空	clear()	清空所有键值对
判空	empty()	为空返回 true，否则返回 false
获取大小	size()	返回键值对的个数

五、适用场景总结（一句话选型）

有序映射、key 唯一 → 用 map（如：用户 ID 对应用户名，需要按 ID 排序）； 快速映射、key 唯一、不在乎顺序 → 用 unordered_map（效率最优，如：缓存映射、快速查询）； 有序映射、key 可重复 → 用 multimap（如：一个 key 对应多个 value，需要排序）； 快速映射、key 可重复、不在乎顺序 → 用 unordered_multimap（如：统计相同 key 的多个 value）。

六、注意事项

map 系列容器的 key 是不可修改的（底层红黑树 / 哈希表依赖 key 排序 / 哈希），若需修改 key，需先删除旧 key，再插入新 key； unordered_map 的 key 需要支持哈希函数，自定义类型作为 key 时，需重写哈希函数和 == 运算符； multimap 不支持 [] 操作符（因为 key 可重复，无法确定对应哪个 value），修改 value 需通过迭代器； 头文件区分：map、multimap 包含 <map>；unordered_map、unordered_multimap 包含 <unordered_map>。

---

七、🔖 本章小结

map 系列容器实现 key 到 value 的映射：底层红黑树保证按 key 有序，插入、删除、查找均为 O(log n)。key 唯一且不可修改，元素是 pair，用 first / second 访问；用下标访问不存在的 key 会自动插入，统计计数时直接写 mp[x]++。不要求有序、追求更快查找时改用 unordered_map；允许重复 key 则用 multimap。

八、📝 实战练习

练习题 1（选择题）

题目： map 的底层数据结构是？

A. 哈希表 B. 红黑树 C. 双向链表 D. 二叉堆

🔑 点击查看答案与解析

答案： B

**解析：**map 和 multimap 底层都是红黑树，所以元素按 key 有序排列，插入查找删除都是 O(log n)。A 是 unordered_map 的底层结构。

---

练习题 2（判断题）

题目： map 中每个 key 只能对应一个 value，key 是唯一的（ ）

🔑 点击查看答案与解析

答案： 正确

**解析：**map 的 key 是唯一的，一个 key 只能对应一个 value。如果 key 可重复，应该用 multimap。

---

练习题 3（选择题）

题目： map 中的元素类型是？

A. pair<const key, value> B. pair<key, value> C. struct {key; value;} D. tuple<key, value>

🔑 点击查看答案与解析

答案： A

**解析：**map 的元素是 pair 类型，其中 first 是 key（const 修饰，不可修改），second 是 value（可修改）。用迭代器访问时，it->first 是 key，it->second 是 value。

---

练习题 4（选择题）

题目： 关于 map 的 [] 操作符，以下说法错误的是？

A. mp[key] = value 可以插入新的键值对 B. mp[key] = value 可以修改已存在 key 的 value C. 如果 key 不存在，mp[key] 会自动插入一个默认 value D. multimap 也支持 [] 操作符

🔑 点击查看答案与解析

答案： D

解析：

• A、B、C 都正确：[] 操作符既可以插入也可以修改，如果 key 不存在会自动插入（value 用默认构造，如 int 是 0）
• D 错误：multimap 不支持 []，因为 key 可重复，无法确定要返回哪个 value

⚠️ 注意：用 [] 访问不存在的 key 会自动插入，这是一个容易忽略的坑！如果只是想查找而不想插入，应该用 find()。

---

练习题 5（程序阅读题）

题目： 阅读以下代码，写出输出结果：

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> mp;
    mp[1] = "apple";
    mp[3] = "cherry";
    mp[2] = "banana";
    mp[1] = "apricot";
    
    cout << mp.size() << " ";
    cout << mp.begin()->first << " ";
    cout << mp.rbegin()->second << endl;
    return 0;
}

🔑 点击查看答案与解析

答案： 3 1 cherry

解析：

• mp[1] = "apple" →
• mp[3] = "cherry" →
• mp[2] = "banana" → {1:"apple", 2:"banana", 3:"cherry"}（按 key 升序）
• mp[1] = "apricot" → key 已存在，修改 value →

size() = 3（3 个 key） begin()->first = 1（最小的 key） rbegin()->second = "cherry"（最大 key 3 对应的 value）

输出：3 1 cherry

---

练习题 6（判断题）

题目： map 中可以直接通过迭代器修改 key 的值（ ）

🔑 点击查看答案与解析

答案： 错误

**解析：**map 的 key 是 const 的，不能直接修改。因为 key 是红黑树排序的依据，修改 key 会破坏树结构。如果需要修改 key，只能先删除旧的键值对，再插入新的。

---

练习题 7（编程题）

题目： 输入 n 个整数，统计每个数字出现的次数，然后按数字从小到大输出每个数字及其出现次数。

**输入格式：**第一行一个整数 n，第二行 n 个整数 **输出格式：**多行，每行一个数字和它的出现次数

样例输入：

8
1 3 2 3 1 3 2 1

样例输出：

1 3
2 2
3 3

🔑 点击查看答案与解析

参考代码：

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<int, int> mp;  // key:数字, value:出现次数
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x]++;  // key 不存在则自动初始化为0，然后++
    }
    
    // 遍历输出（map 自动按 key 升序）
    for (auto& p : mp) {
        cout << p.first << " " << p.second << endl;
    }
    
    return 0;
}

**解析：**这是 map 最经典的应用——统计次数。核心技巧是 mp[x]++：

• 如果 x 不在 map 中，mp[x] 会自动插入 x，value 默认为 0，然后 ++ 变成 1
• 如果 x 已在 map 中，mp[x] 返回 value 的引用，直接 ++ 即可

map 会自动按 key 排序，所以输出自然就是从小到大的顺序。这道题用 map 做非常简洁。

---

练习题 8（编程题）

题目： 给定两个字符串 s 和 t，判断它们是否是字母异位词（即两个字符串中每个字母出现的次数都相同，只是顺序不同）。 **输入格式：**两行，第一行字符串 s，第二行字符串 t（均由小写字母组成）。 **输出格式：**若是字母异位词输出 Yes，否则输出 No。

样例输入 1：

anagram
nagaram

样例输出 1：

Yes

样例输入 2：

rat
car

样例输出 2：

No

🔑 点击查看答案与解析

参考代码：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    
    if (s.size() != t.size()) {
        cout << "No" << endl;
        return 0;
    }
    
    map<char, int> mp;
    
    // 统计 s 中每个字符的出现次数
    for (char c : s) {
        mp[c]++;
    }
    
    // 用 t 中的字符减少计数
    for (char c : t) {
        mp[c]--;
        if (mp[c] < 0) {  // t 中有 s 没有的字符，或次数更多
            cout << "No" << endl;
            return 0;
        }
    }
    
    // 检查所有字符的计数是否都为 0
    for (auto& p : mp) {
        if (p.second != 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

**解析：**这是 map 的经典应用题。思路：

1. 先用 map 统计第一个字符串中每个字符的出现次数
2. 再遍历第二个字符串，每个字符对应计数减 1
3. 如果出现负数，说明第二个字符串有第一个字符串没有的字符（或更多）
4. 最后检查所有计数是否都为 0

如果全部为 0，说明两个字符串每个字符出现的次数都相同，就是字母异位词。

这道题也可以用数组（因为字母只有 26 个）来做，效率更高，但用 map 更通用（比如 Unicode 字符的情况）。

---

九、📊 考点总结表

知识点	重要程度	出题形式	易错点
map 底层是红黑树	⭐⭐⭐⭐⭐	选择题、判断题	与哈希表混淆
key 唯一、自动排序	⭐⭐⭐⭐⭐	选择题、判断题	与 unordered_map 混淆
元素是 pair 类型	⭐⭐⭐⭐	选择题、编程题	first/second 搞反
[] 自动插入	⭐⭐⭐⭐⭐	选择题、编程题	以为只是查找
key 不可修改	⭐⭐⭐⭐	选择题、判断题	以为可以改 key
multimap 无 []	⭐⭐⭐	选择题	以为 multimap 也有 []
统计次数经典应用	⭐⭐⭐⭐⭐	编程题	不会用 mp[x]++
头文件区分	⭐⭐⭐	选择题、判断题	map 和 unordered_map 搞混
插入查找删除 O(log n)	⭐⭐⭐⭐	选择题	时间复杂度记错
map vs unordered_map 选型	⭐⭐⭐⭐	选择题、简答题	选型依据记不清

---

⭐ 必背速记卡

┌──────────────────────────────────────┐
│  map 系列必背速记卡                   │
├──────────────────────────────────────┤
│  1. 键值对存储，key-value 映射        │
│  2. map/multimap 底层红黑树，有序     │
│  3. unordered_* 底层哈希表，无序     │
│  4. map/unordered_map 的 key 唯一    │
│  5. multimap/umm 的 key 可重复       │
│  6. 元素是 pair，first是key、second是值│
│  7. [] 操作符：不存在则插入，存在则修改│
│  8. key 不可修改，只能删了再插         │
│  9. 经典应用：统计次数、字典映射       │
│  10. 头文件：<map> 和 <unordered_map> │
└──────────────────────────────────────┘