multimap 一键多值

读完能做什么

• 能创建 multimap，用 insert 给同一个键加入多条独立记录。
• 能用 equal_range 遍历某个键对应的全部记录，用 count 数出记录条数；能说清 find 只给出一个匹配位置、遍历同键记录要用区间。
• 能分清 erase(key) 删掉该键的全部记录、erase(it) 只删一条。
• 能判断什么时候用 multimap、什么时候用 map<Key, vector<Value>>。

为什么需要它

map 的规则是“一个键对应一个值”。但现实里常常是“一个键对应好几条记录”：

• 一个学生有多门课的成绩；
• 一个作者有多本书；
• 一次考试里同一个人考了多次。

用 map 存，第二次遇到同一个键就会覆盖第一次的值，记录丢了。上一页的map 键值映射只解决了“一对一”。我们想要的是：允许同一个键出现多次，每条记录各自独立，同时又保持 map 那样的按键有序、快速定位。这就是 multimap。

它是什么

一句话：multimap 是“允许同一个键重复出现”的 map，每个键可以对应任意多条记录。

和 map 的区别。 map 里一个键只有一个元素；multimap 里同一个键可以有多个元素，它们按键排在一起，彼此独立。

没有 operator[]。 multimap 不提供中括号。因为 m[key] 的语义是“这个键对应的那一个值”，而 multimap 里一个键有多个值，[] 没法回答“要哪一个”，所以标准库干脆不给。

按键自动排序。 和 map 一样，multimap 按键升序排列，相同的键紧挨在一起，插入的先后不影响整体顺序。

记录之间的顺序。 同一个键的多条记录，按插入的先后排列（先插入的在前），这是 C++11 起标准规定的行为。

复杂度 O(log n)。 插入、查找、删除都是 O(log n)，n 是记录条数。

适用场景：需要“一个键保存多条独立记录”，并且经常要按键批量取出这些记录。使用时要 #include <map>（multimap 和 map 在同一个头文件里），本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

选读。 和 map 一样，multimap 底层通常用平衡二叉搜索树实现，所以能保持有序、查找快。

最小可运行示例

数据写在代码里，不需要输入。给键 A 插入两条记录、键 B 插入一条：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> scores;   // 键是姓名，值是成绩

    scores.insert(make_pair("A", 80));
    scores.insert(make_pair("B", 90));
    scores.insert(make_pair("A", 85));   // 键 A 再插一条，不会覆盖上一条

    cout << "size = " << scores.size() << '\n';
    cout << "count(\"A\") = " << scores.count("A") << '\n';

    cout << "全部记录：\n";
    for (const auto& p : scores) {
        cout << p.first << " " << p.second << '\n';
    }
    return 0;
}

输出：

size = 3
count("A") = 2
全部记录：
A 80
A 85
B 90

逐行看：

• multimap<string, int> scores; 创建一个空 multimap，键是 string、值是 int。它里面的每个元素都是一个 pair<const string, int>：p.first 是键（姓名），p.second 是值（成绩），it->second 同理。pair 的 first / second 用法见 pair 二元组。
• 三次 insert 都成功：A 插了两次，B 插了一次，所以 size() 是 3——重复的键不会被丢掉。
• scores.count("A") 是 2，表示键 A 有两条记录。
• 遍历输出 A 80、A 85、B 90：按键升序，键 A 的两条记录挨在一起，并且按插入先后排列。

一步步看变化

沿 ("A",80)、("B",90)、("A",85) 这组数据走一遍：

第 3 步是 multimap 和 map 的关键区别：如果用 map，这一句会覆盖 A 原来的值；multimap 则是新增一条记录，size() 从 2 变成 3，count("A") 从 1 变成 2。

逐项扩展核心操作

遍历同键记录：equal_range

想取出键 A 的所有记录，用成员 equal_range。它返回一对迭代器，圈出键为 A 的那一段区间：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> scores;
    scores.insert(make_pair("A", 80));
    scores.insert(make_pair("B", 90));
    scores.insert(make_pair("A", 85));

    auto range = scores.equal_range("A");   // [first, last) 覆盖所有键为 A 的记录
    cout << "键 A 的记录：";
    for (auto it = range.first; it != range.second; it++) {
        cout << it->second << ' ';
    }
    cout << '\n';

    cout << "count(\"A\") = " << scores.count("A") << '\n';
    cout << "find(\"A\")->second = " << scores.find("A")->second
         << "（只给出一个匹配位置）\n";
    return 0;
}

输出：

键 A 的记录：80 85 
count("A") = 2
find("A")->second = 80（只给出一个匹配位置）

• equal_range(key) 返回 pair<iterator, iterator>，表示左闭右开区间 [first, last)：first 指向键为 key 的第一段记录的起点，last 指向这些记录后面一个位置。用 for (auto it = range.first; it != range.second; it++) 就能走遍该键的全部记录。
• count("A") 是 2，正好等于这段区间的长度。想在代码里数出区间长度，用 distance(range.first, range.second)：multimap 的迭代器是双向迭代器，不能相减。
• find("A") 只给出一个匹配位置，所以 find("A")->second 是本机实测的 80，拿不到 85（标准只保证返回一个键为 A 的元素，不规定是哪一个）。要拿全部记录，必须用区间。

想同时拿到某个键记录的起点和终点，也可以分别用成员 lower_bound 和 upper_bound，它们合起来就是 equal_range。

删除：删全部还是删一条

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> scores;
    scores.insert(make_pair("A", 80));
    scores.insert(make_pair("B", 90));
    scores.insert(make_pair("A", 85));

    // 只删一条 A 记录：用迭代器
    auto it = scores.find("A");
    scores.erase(it);
    cout << "按迭代器删一条后 size = " << scores.size()
         << "，count(\"A\") = " << scores.count("A") << '\n';

    // 再插回一条，然后按键删除全部 A
    scores.insert(make_pair("A", 85));
    scores.erase("A");
    cout << "erase(\"A\") 后 size = " << scores.size()
         << "，count(\"A\") = " << scores.count("A") << '\n';

    cout << "剩下的记录：\n";
    for (const auto& p : scores) cout << p.first << " " << p.second << '\n';
    return 0;
}

输出：

按迭代器删一条后 size = 2，count("A") = 1
erase("A") 后 size = 1，count("A") = 0
剩下的记录：
B 90

• 第一步用 find("A") 定位到一条 A 记录（本机实测是 A:80），erase(it) 只删这一条，size() 从 3 变 2。
• 第二步 erase("A") 是按键删除，把键 A 的记录全部删掉，size() 从 3（补插回一条后）直接掉到 1。
• 想删键为 key 的单条记录，必须先用 find 或遍历区间拿到迭代器，再 erase(it)。

对比：map<Key, vector<Value>>

“一键多值”还有另一种常见写法：用 map，但把值类型换成 vector。

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, vector<int>> scores;    // 键 A 对应一个成绩列表

    scores["A"].push_back(80);          // operator[] 先建好一个空 vector
    scores["A"].push_back(85);
    scores["B"].push_back(90);

    cout << "A 的成绩：";
    for (int x : scores["A"]) cout << x << ' ';
    cout << '\n';
    cout << "size = " << scores.size() << "（这是键的个数）\n";
    return 0;
}

输出：

A 的成绩：80 85 
size = 2（这是键的个数）

两种写法怎么选：

简单说：数据本身就是一条条独立记录、需要按键批量扫一遍时，用 multimap 更自然；每个键对应一个“列表”整体、常常要用下标访问时，用 map<Key, vector<Value>> 更顺手。

什么时候选它、哪里容易错

没有 operator[]。 m[key] 在 multimap 上不能编译。要取值只能靠 find（一个位置）或 equal_range（一段区间）。这也是它和 map 最大的用法差别。

find 只给出一个匹配位置。 find(key) 返回键为 key 的某一个元素（本机实测是排在最前面的那一条），不是全部；标准没有规定必须是哪一条。要遍历同键记录，用 equal_range（或 lower_bound 到 upper_bound）。

erase(key) 删掉该键的全部记录。 想只删一条，必须先用 find 定位到具体迭代器，再 erase(it)。这一点和 multiset 一样。

size() 是记录总数，不是键的个数。 键 A 有两条记录时 size() 就多算一个。想知道有几个不同的键，得自己数（或改用 map）。

插入不会覆盖。 insert 在 multimap 上永远新增一条记录，返回的迭代器指向新插入的那条。这与 map::insert 的“键已存在就不插”不同。

复杂度 O(log n)。 插入、查找、删除都是 O(log n)。一次 equal_range 加上遍历该键的 k 条记录，代价是 O(log n + k)。

选读。 和 map 一样，multimap 底层通常是平衡二叉搜索树。同键记录挨在一起，靠的是“按比较规则相等”这个性质。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），在键 A 已有两条记录的基础上又插了一条 A:88。请先手推出输出，再运行核对：

multimap<string, int> m;
m.insert(make_pair("A", 80));
m.insert(make_pair("B", 90));
m.insert(make_pair("A", 85));
m.insert(make_pair("A", 88));       // 新增一条 A

cout << "size = " << m.size() << "，count(\"A\") = " << m.count("A") << '\n';

第 2 题：修改代码

下面这段片段用 erase("A") 删掉了键 A 的全部记录。请改成只删一条 A 记录，让输出变成 size = 2，count("A") = 1：

multimap<string, int> m;
m.insert(make_pair("A", 80));
m.insert(make_pair("B", 90));
m.insert(make_pair("A", 85));

m.erase("A");              // 这一句会删掉 A 的全部记录，请改成只删一条

cout << "size = " << m.size() << "，count(\"A\") = " << m.count("A") << '\n';

验证条件：先说出 erase("A") 和只删一条的结果分别是多少，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> m;
    m.insert(make_pair("A", 80));
    m.insert(make_pair("B", 90));
    m.insert(make_pair("A", 85));
    m.insert(make_pair("A", 88));       // 新增一条 A

    cout << "size = " << m.size() << "，count(\"A\") = " << m.count("A") << '\n';
    return 0;
}

size = 4，count("A") = 3

#include <bits/stdc++.h>
using namespace std;

int main() {
    multimap<string, int> m;
    m.insert(make_pair("A", 80));
    m.insert(make_pair("B", 90));
    m.insert(make_pair("A", 85));

    m.erase(m.find("A"));               // 只删一条 A 记录
    cout << "size = " << m.size() << "，count(\"A\") = " << m.count("A") << '\n';
    return 0;
}

size = 2，count("A") = 1

本页不安排「立即练习」小节：multimap 的入门 OJ 题目较少，一键多值场景在本章用上面的动手检查覆盖，等遇到真实的一键多值任务时再选用即可。

延伸阅读

• cppreference.com：std::multimap：标准库参考，需要精确查某个成员函数的签名和保证时看这里。