从字典到代码：map与multimap映射详解

你有没有用过《新华字典》？每个汉字（键）都对应着一段解释（值）。并且字典里的字是按拼音排序的，这样找起来特别快。这就是一种 “键-值”映射——键是汉字，值是解释。在 C++ 中，map 就是专门用来存储这种对应关系，并且自动按键排序的容器。

再想想小区里的电话本：同一栋楼可能有两个人都叫“王芳”，一个住302，一个住501。你需要同时保存两个“王芳”的电话号码。这时，一个键对应多个值的情况出现了，对应的容器就是 multimap（多重映射）。

map 和 multimap 非常适合处理“根据一个数据快速找到另一个相关数据”的问题，比如：

学号 → 学生姓名
城市 → 邮政编码
单词 → 中文释义
游戏 ID → 得分

1. 从生活中理解“键值对”与自动排序

想象你有一堆单词卡片，每张卡片正面是英文单词，背面是中文意思。如果你想让这些卡片按单词字母顺序排列，并且每张单词只有一张卡片（不允许重复），这就是 map。如果你同一个单词（比如“spring”）可能对应“春天”和“弹簧”两种意思，那你就需要允许重复的卡片，这就是 multimap。并且容器会自动帮你排好序，每次插入后你都不用手动排序。

2. map 和 multimap 的核心概念与区别

特性	map	multimap
键是否唯一	每个键只能出现一次	同一个键可以出现多次
是否自动排序	是（默认升序）	是（默认升序）
常用操作	插入、查找、修改、删除	插入、查找、删除（无修改，因为一个键可能对应多个值）
访问方式	可以用 `[]` 和 `at()`	不能用 `[]` 和 `at()`，必须通过迭代器
内部结构	红黑树（平衡二叉搜索树）	红黑树（平衡二叉搜索树）
时间复杂度	插入、删除、查找 O(log n)	插入、删除、查找 O(log n)（但查找单个键可能返回多个元素）

生活比喻：map 就像你班级的学号登记表，每个学号对应一个学生，学号不能重复。multimap 就像电话簿，一个姓名可能对应多个号码（家庭电话、公司电话、手机）。

3. 深入讲解：常用操作及其细节

3.1 头文件和声明

#include <map>      // map 和 multimap 都在这里
using namespace std;

// 声明 map，键为 string，值为 int
map<string, int> stu_score;  // 学生姓名 -> 成绩

// 声明 multimap，键为 string，值为 string
multimap<string, string> phone_book;  // 姓名 -> 电话

3.2 插入元素

map 的插入

// 方法一：使用 insert 和花括号
stu_score.insert({"Alice", 95});

// 方法二：使用 make_pair
stu_score.insert(make_pair("Bob", 87));

// 方法三：使用 [] 运算符（如果键不存在则自动插入默认值，然后修改）
stu_score["Charlie"] = 92;   // 如果 Charlie 不存在，插入后赋值为 92
stu_score["Alice"] = 96;     // 如果 Alice 已存在，直接覆盖值为 96

注意：insert 的返回值是一个 pair<iterator, bool>。在 map 中，如果插入的键已存在，bool 为 false，插入失败，容器不变。

auto result = stu_score.insert({"Alice", 100});
if (result.second == false) {
    cout << "插入失败，Alice 已存在，当前值为 " << result.first->second << endl;
}

multimap 的插入

multimap 没有 [] 运算符，只能用 insert 或 emplace，而且插入总是成功（因为键可以重复）。

phone_book.insert({"Zhang", "1380000"});
phone_book.insert({"Zhang", "1390000"}); // 键相同，值不同，允许

小技巧：用 emplace 可以避免临时对象拷贝，推荐在需要构造复杂类型时使用。

stu_score.emplace("Eve", 88);   // 直接构造键值对
phone_book.emplace("Li", "1370000");

3.3 访问元素（仅 map 有）

operator[]：m[key]
- 如果 key 存在，返回值的引用，可修改。
- 如果 key 不存在，自动插入一个键值对，值采用默认构造（比如 int 是 0，string 是空字符串），然后返回值的引用。
  警示：[] 可能会无意中插入新元素，导致容器变大，这在一些只读场景下是危险的。
at(key)（C++11）：
- 如果 key 存在，返回值的引用。
- 如果 key 不存在，抛出 std::out_of_range 异常。
  推荐：只读或确定键存在时使用，更安全。

map<string, int> m;
m["apple"] = 10;        // 插入 apple -> 10
cout << m["apple"];     // 输出 10，不会插入
cout << m["banana"];    // 不存在，自动插入 banana -> 0，输出 0（可能不是你想要的）

// 安全方式：先用 find 或 count 检查，或用 at
try {
    cout << m.at("banana"); // 抛出异常
} catch (const out_of_range& e) {
    cout << "找不到 banana";
}

对于 multimap，无法直接通过键访问单个值，因为你不知道应该返回哪一个。必须通过迭代器或 equal_range 来遍历所有值。

3.4 查找元素

函数	适用容器	说明
`find(key)`	map, multimap	返回指向第一个键等于 key 的迭代器；若不存在则返回 `end()`。
`count(key)`	map, multimap	返回键等于 key 的元素个数（map 返回 0 或 1；multimap 可能大于 1）
`lower_bound(key)`	map, multimap	返回指向第一个键不小于 key 的迭代器（即 >= key）
`upper_bound(key)`	map, multimap	返回指向第一个键大于 key 的迭代器
`equal_range(key)`	map, multimap	返回一个 `pair`，first 是 `lower_bound`，second 是 `upper_bound`，这两个迭代器之间的所有元素就是键等于 key 的全部。

对于 multimap 的查找：如果你想找到键为 "Zhang" 的所有电话，最好用 equal_range 或 lower_bound + upper_bound。

auto range = phone_book.equal_range("Zhang");
for (auto it = range.first; it != range.second; ++it) {
    cout << it->second << " ";
}

3.5 删除元素

erase(key)：删除所有键等于 key 的元素，返回删除的个数。
erase(iterator)：删除迭代器指向的单个元素（注意：删除后该迭代器失效，但其他迭代器不受影响）。
erase(first, last)：删除区间 [first, last) 内的所有元素。
clear()：清空所有元素。

stu_score.erase("Alice");           // 删除键为 Alice 的条目
phone_book.erase("Zhang");          // 删除所有 Zhang 的电话（返回 2）
auto it = phone_book.find("Li");
if (it != phone_book.end()) phone_book.erase(it); // 仅删除第一个 Li

3.6 遍历

遍历时，迭代器指向的是 pair<const Key, T>，所以访问键用 it->first，访问值用 it->second。

// 传统迭代器
for (auto it = m.begin(); it != m.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
}

// 范围 for（推荐，更简洁）
for (const auto& p : m) {
    cout << p.first << " -> " << p.second << endl;
}

3.7 自定义排序

默认按键的升序（小于比较）。可以指定比较器，比如降序、按长度排序等。

// 按键降序（从大到小）
map<int, string, greater<int>> m;  // greater<int> 表示降序

// 自定义比较器：按字符串长度排序
struct CompareByLength {
    bool operator()(const string& a, const string& b) const {
        return a.size() < b.size();
    }
};
map<string, int, CompareByLength> m2;

4. 新手最容易犯的 4 个错误

❌ 错误 1：在 map 中用 `[]` 查找而不想插入

map<string, int> scores;
// ...
int x = scores["unknown"];  // 如果 "unknown" 不存在，会自动插入，x 值为 0

正确做法：先 find 或 count 检查，或使用 at()。

❌ 错误 2：在 multimap 中用 `[]` 访问

multimap 没有 [] 运算符，编译会报错。必须用 insert 插入，用 equal_range 查找。

❌ 错误 3：删除迭代器后继续使用

auto it = m.find("key");
m.erase(it);
cout << it->first;  // 错误！it 已经失效

正确做法：删除后不要再使用该迭代器，如果需要在删除后继续遍历，可以用 it = m.erase(it)（C++11 中 erase 返回下一个元素的迭代器）。

❌ 错误 4：忽略 `insert` 的返回值（map 中）

m.insert({"Alice", 100});
m.insert({"Alice", 200}); // 不会覆盖，因为 Alice 已存在
// 你可能以为 Alice 变成了 200，实际仍是 100

正确做法：检查返回值，或者直接用 [] 赋值（想覆盖时）。

5. 完整可运行的 C++ 示例（成绩管理与电话本）

#include <iostream>
#include <map>          // map 和 multimap 头文件
#include <string>
using namespace std;

int main() {
    // ========== 1. map 示例：学生成绩 ==========
    cout << "=== map 示例：学生成绩 ===" << endl;
    map<string, int> scores;  // 键: 姓名(string), 值: 分数(int)

    // 插入键值对
    scores["Alice"] = 95;     // 先插入（默认值0，再赋95）
    scores.insert({"Bob", 87});
    scores.emplace("Charlie", 92);

    // 修改已有键的值
    scores["Alice"] = 96;     // Alice 已存在，直接覆盖

    // 自动按姓名升序排序（字母顺序）
    cout << "当前成绩表（按姓名排序）:" << endl;
    for (const auto& p : scores) {
        cout << p.first << " : " << p.second << endl;
    }

    // 查找
    auto it = scores.find("Charlie");
    if (it != scores.end()) {
        cout << "Charlie 的成绩是: " << it->second << endl;
    }

    // 使用 count 判断键是否存在
    cout << "Charlie 出现次数: " << scores.count("Charlie") << endl;  // 1
    cout << "Eve 出现次数: " << scores.count("Eve") << endl;          // 0

    // 使用 at 安全访问
    try {
        cout << "Alice 的成绩 (at): " << scores.at("Alice") << endl;
    } catch (const out_of_range& e) {
        cout << "键不存在" << endl;
    }

    // 删除
    scores.erase("Bob");
    cout << "删除 Bob 后: ";
    for (const auto& p : scores) cout << p.first << ":" << p.second << " ";
    cout << endl;

    cout << endl;

    // ========== 2. multimap 示例：电话本 ==========
    cout << "=== multimap 示例：电话本（同名多个电话） ===" << endl;
    multimap<string, string> phoneBook;  // 姓名 -> 电话

    phoneBook.insert({"Zhang", "1380000"});
    phoneBook.insert({"Zhang", "1390000"});
    phoneBook.insert({"Li",   "1370000"});
    phoneBook.insert({"Wang", "1360000"});

    // 遍历（自动按键排序，相同键保持插入顺序）
    cout << "电话本内容（按姓名排序）:" << endl;
    for (const auto& p : phoneBook) {
        cout << p.first << " : " << p.second << endl;
    }

    // 查找某个键对应的所有值
    string target = "Zhang";
    auto range = phoneBook.equal_range(target);
    cout << target << " 的电话有: ";
    for (auto it = range.first; it != range.second; ++it) {
        cout << it->second << " ";
    }
    cout << endl;

    cout << target << " 出现次数: " << phoneBook.count(target) << endl; // 2

    // 删除一个键对应的特定值（通过迭代器）
    auto it2 = phoneBook.find("Li");
    if (it2 != phoneBook.end()) phoneBook.erase(it2);
    cout << "删除第一个 Li 后，剩余 Li 个数: " << phoneBook.count("Li") << endl; // 0

    // 删除所有键为某个值的元素
    phoneBook.erase("Zhang");
    cout << "删除所有 Zhang 后，电话本剩余个数: " << phoneBook.size() << endl; // 1 (Wang)

    return 0;
}

输出结果：

=== map 示例：学生成绩 ===
当前成绩表（按姓名排序）:
Alice : 96
Bob : 87
Charlie : 92
Charlie 的成绩是: 92
Charlie 出现次数: 1
Eve 出现次数: 0
Alice 的成绩 (at): 96
删除 Bob 后: Alice:96 Charlie:92 David:88 

=== multimap 示例：电话本（同名多个电话） ===
电话本内容（按姓名排序）:
Li : 1370000
Wang : 1360000
Zhang : 1380000
Zhang : 1390000
Zhang 的电话有: 1380000 1390000 
Zhang 出现次数: 2
删除第一个 Li 后，剩余 Li 个数: 0
删除所有 Zhang 后，电话本剩余个数: 1

6. Python 模拟 map 和 multimap

Python 的 dict 相当于 map，但它是无序的（Python 3.7 后保持插入顺序，但依然不会按键排序）。若需要排序，可以用 sorted(dict.items())。对于 multimap，建议用 collections.defaultdict(list) 实现一个键对应多个值。

from collections import defaultdict

# ========== 1. 模拟 map（字典）==========
print("=== Python 字典（类似 map）===")
scores = {}  # 空字典

# 插入或修改
scores["Alice"] = 95
scores["Bob"] = 87
scores["Charlie"] = 92
scores["Alice"] = 96  # 覆盖

# 遍历（插入顺序）
print("当前成绩表（插入顺序）:")
for name, score in scores.items():
    print(f"{name} : {score}")

# 查找
if "Charlie" in scores:
    print("Charlie 的成绩是:", scores["Charlie"])

# 计数（键唯一，用 in 检查）
print("Charlie 出现次数:", 1 if "Charlie" in scores else 0)  # 1

# 删除
del scores["Bob"]
print("删除 Bob 后:", scores)

# 使用 get 安全访问
alice_score = scores.get("Alice", "不存在")
print("Alice 的成绩:", alice_score)

# ========== 2. 模拟 multimap ==========
print("\n=== 模拟 multimap（defaultdict(list)）===")
phone_book = defaultdict(list)  # 每个键对应一个列表

# 插入多个电话
phone_book["Zhang"].append("1380000")
phone_book["Zhang"].append("1390000")
phone_book["Li"].append("1370000")
phone_book["Wang"].append("1360000")

print("电话本内容:")
for name, phones in phone_book.items():
    print(f"{name} : {', '.join(phones)}")

# 查找某个键的所有值
target = "Zhang"
print(f"{target} 的电话有: {phone_book[target]}")

# 计数
print(f"{target} 出现次数: {len(phone_book[target])}")  # 2

# 删除一个键的某个值（需要手动从列表中移除）
if "Li" in phone_book:
    phone_book["Li"].remove("1370000")
    if not phone_book["Li"]:
        del phone_book["Li"]
print("删除 Li 的一个电话后，Li 的剩余电话:", phone_book.get("Li", []))

# 删除整个键
del phone_book["Zhang"]
print("删除所有 Zhang 后，剩余键:", list(phone_book.keys()))

注意：Python 的 defaultdict(list) 当访问一个不存在的键时会自动创建空列表，需要小心。如果需要按键排序，可以在输出时 sorted(phone_book.items())。

7. 总结与相关指引

map vs multimap：键是否唯一，决定了访问方式的不同。
自动排序：基于红黑树，插入/删除/查找都是 O(log n)。
map 特有的 [] 和 at：[] 会默认插入，at 会异常，选择要谨慎。
multimap 的查找：equal_range 是最佳选择。
自定义比较器：灵活控制排序逻辑。
Python 代替方案：dict + sorted() 模拟 map，defaultdict(list) 模拟 multimap。

掌握了 map 和 multimap，你就拥有了一个“自动排好序的数据字典”。接下来，你可以进一步了解它们底层的红黑树数据结构，以及 C++ 标准库中另两个关联容器：unordered_map 和 unordered_multimap，它们基于哈希表，是“无序但更快”的选择。

例题精讲