一、课上练习

编程练习

1. map的增删查：L3281
2. 统计每个数出现的次数：L3282
3. 宇宙总统：L3283

二、知识总结

✨ 核心思想

map 是 C++ 标准模板库（STL）中的一个关联容器，它以键值对的形式存储元素，其中每个键都是唯一的，并且每个键都映射到一个值。map 的内部实现通常是自平衡的二叉搜索树（如红黑树），提供了有序的键值对存储，并确保主要操作具有对数时间复杂度。

✨ 特性

map 具有以下核心特性：

• 键值对存储：map 存储的是键值对，键是唯一的。
• 自动排序：元素根据键自动排序，即按照键升序排序。
• 元素访问：通过键访问元素，如果键不存在，则访问会创建一个新的元素。
• 不允许修改键：map 中的键是常量，一旦创建，你不能修改键的值，但可以修改与键关联的值。

✨ 常用操作

map 支持以下常用操作：

• 插入元素：使用 insert() 或 emplace() 方法插入新的键值对。如果键已经存在，则操作不会替换现有元素。
• 删除元素：使用 erase() 方法根据键或迭代器删除元素。
• 查找元素：使用 find() 方法通过键查找元素，返回一个指向该键值对的迭代器，如果未找到，则返回 end()。
• 访问元素：可以使用 operator[] 直接通过键访问值。如果键不存在，operator[] 会插入一个具有该键的新元素，并返回对其值的引用。

✨ 性能考虑

map 各操作的时间复杂度：

• 操作性能：查找、插入和删除操作通常具有 O(log n) 的时间复杂度，其中 n 是 map 中元素的数量。
• 空间效率：由于内部使用树结构，map 比简单数组或未排序的数据结构使用更多的内存，以支持快速操作。

✨ 应用场景

map 适用于以下场景：

• 当你需要根据键快速查找、更新或删除元素时，map 是一个理想的选择。
• map 适用于需要按键排序的情况，如需要按照某种顺序处理或输出键值对。
• 当元素的插入顺序不重要，但每个元素需要通过一个唯一标识符访问时，map 提供了优越的性能和便利。

总的来说，map 是一个功能丰富的容器，用于存储唯一键到值的映射，支持快速的查找、插入和删除操作，并保持元素有序。它适用于许多需要高效访问和维护键值对数据的应用场景。

✨ 执行示例

下面展示 map 的常见操作的完整执行过程。

操作序列：

1map<string, int> m;
2m["banana"] = 3;       // 第1步
3m["apple"] = 5;        // 第2步
4m["cherry"] = 2;       // 第3步
5m["banana"] = 7;       // 第4步（更新已有键）
6m.erase("apple");      // 第5步
7cout << m["grape"];     // 第6步（访问不存在的键）

特别注意第 6 步： 使用 [] 访问不存在的键时，map 会自动创建该键并赋默认值（int 为 0，string 为 ""）。这是一个常见的陷阱！如果只想查询是否存在，应该用 find() 或 count()。

安全的查询方式：

1// 方法1：使用 find
2auto it = m.find("grape");
3if (it != m.end()) {
4    cout << it->second;  // 存在
5} else {
6    cout << "不存在";
7}
8
9// 方法2：使用 count
10if (m.count("grape") > 0) {
11    cout << m["grape"];  // 此时可以安全使用 []
12}

✨ 解题步骤详解

以"统计每个数出现的次数"为例：

问题： 给定 n 个整数，统计每个数出现的次数，按数值从小到大输出。

解题步骤：

1. 选择数据结构：map 正好可以将数值映射到出现次数，且自动按键排序。
2. 读入并统计：每读入一个数 x，执行 m[x]++。如果 x 第一次出现，m[x] 自动初始化为 0，加 1 后变为 1。
3. 输出结果：遍历 map，每个元素的 first 是数值，second 是次数。

代码框架：

1map<int, int> cnt;
2for (int i = 0; i < n; i++) {
3    int x;
4    cin >> x;
5    cnt[x]++;  // 关键操作：自动创建并累加
6}
7for (auto it = cnt.begin(); it != cnt.end(); ++it) {
8    cout << it->first << " " << it->second << endl;
9}

为什么 map 比数组更适合： 如果数据范围很大（如 -10^9 到 10^9），用数组需要巨大的空间。map 只存储实际出现的元素，空间效率高。

✨ 常见错误

1. 用 [] 查询导致意外插入元素：if (m["key"] == 0) 这样的写法会在 map 中插入 "key"。应改用 if (m.find("key") == m.end()) 或 if (m.count("key") == 0)。
2. 遍历时修改 map：在 for 循环遍历 map 的过程中插入或删除元素会导致迭代器失效。如果需要删除，使用 it = m.erase(it) 的写法。
3. 混淆 map 和 unorderedmap：map 内部是红黑树，键有序，操作 O(log n)；unorderedmap 内部是哈希表，键无序，操作平均 O(1)。根据题目是否要求有序来选择。
4. 忘记 map 的键是 const 的：不能通过迭代器修改键值 it->first = newKey，只能修改值 it->second = newValue。
5. pair 的使用不熟练：map 的每个元素是 pair。访问键用 .first，访问值用 .second。insert 时需要传入 pair 类型。

✨ 代码实现

下面的代码展示了 map 的各种常用操作，包括插入、访问、查找和遍历等：

1#include <iostream>
2#include <map>
3#include <string>
4
5using namespace std;
6
7int main() {
8    // 创建一个map，键为string，值为int
9    map<string, int> ageMap;
10
11    // 插入数据
12    ageMap["Alice"] = 30;
13    ageMap["Bob"] = 25;
14    ageMap["Charlie"] = 35;
15
16    // 使用insert函数插入键值对
17    ageMap.insert(pair<string, int>("David", 28));
18
19    // 访问元素
20    cout << "Charlie's age: " << ageMap["Charlie"] << endl;
21
22    // 检查元素是否存在
23    if (ageMap.find("Eve") == ageMap.end()) {
24        cout << "Eve not found in ageMap." << endl;
25    } else {
26        cout << "Eve's age: " << ageMap["Eve"] << endl;
27    }
28
29    // 使用迭代器遍历map
30    cout << "All elements in ageMap:" << endl;
31    for (map<string, int>::iterator it = ageMap.begin(); it != ageMap.end(); ++it) {
32        cout << "Name: " << it->first << ", Age: " << it->second << endl;
33    }
34
35    // 使用auto关键字简化迭代器的类型
36    cout << "Using auto keyword for iteration:" << endl;
37    for (auto it = ageMap.begin(); it != ageMap.end(); ++it) {
38        cout << "Name: " << it->first << ", Age: " << it->second << endl;
39    }
40
41    return 0;
42}

三、课后练习

编程练习

1. 宇宙总统2：L3284