map 键值映射

读完能做什么

• 能创建 map，用键 m[key] 存值、取值，并说出它和数组下标的区别。
• 能遍历 map，读出每个元素的 first（键）和 second（值），并解释输出为什么按键升序。
• 能用 count、find 查询键、用 erase 删除键，并说清 find 查不存在的键不会插入、operator[] 查不存在的键会插入默认值（用 size() 验证）。
• 能解释为什么迭代得到的键不能改，值可以改。

为什么需要它

数组用连续整数下标取数据，很适合“第几个”的问题：

int score[1005];
score[7] = 85;              // 片段：下标 7 就是第 8 个位置
cout << score[7];           // 按位置直接取

但很多问题的“索引”不是整数位置，而是任意一种键：姓名、单词、编号。比如统计每个单词出现了几次，我们想直接问“apple 的计数是多少”。用数组得自己把单词映射成整数，再开一张对照表；用两个平行数组查找要线性扫描，很慢。

我们希望有一个容器，能像数组那样用中括号 [] 按“键”取数据，只不过键可以是字符串这样的任意可比较类型。这就是 map。

它是什么

一句话：map 是标准库提供的关联数组，它把**键（key）和值（value）**一对一地存起来，按键就能快速找到对应的值。

键值对。 map 里的每个元素由两部分组成：一个键、一个值。map<string, int> 表示“键是 string、值是 int”。元素类型是 pair<const string, int>——也就是把两个值绑在一起的 pair，其中 first 是键、second 是值，键带 const（只读）。

与数组下标的区别。 数组的下标是连续的整数位置，从 0 开始，中间不能空；map 的键是任意可比较的类型，可以是字符串、整数、甚至 pair，不必连续、不必从 0 开始。数组下标只能是整数，map 的键是什么类型由你决定。

键不重复。 一个键在 map 里最多对应一个值。重复给同一个键赋值只会覆盖旧值。

默认按键升序。 map 按键的默认比较规则（<）自动排序，所以遍历时输出总是按键从小到大。对 map<string, int> 就是按字典序。

键不能改，值能改。 遍历得到的元素里，first（键）是 const 的，不能改；second（值）可以随意改。因为键决定了元素在容器里的位置，改键会破坏有序性。

复杂度 O(log n)。 按键查找、插入、删除都是 O(log n)，n 是键的个数。这比“用数组线性扫描”的 O(n) 快很多。

适用场景：需要“按某个键快速存取数据”，比如统计词频、姓名到成绩的对照、编号到信息的映射。使用时要 #include <map>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

选读。 map 内部通常用平衡二叉搜索树（红黑树）实现，这就是它能按键快速定位、并保持有序的原因。不了解树的结构也能正常使用 map。

最小可运行示例

数据写在代码里，不需要输入：

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

int main() {
    map<string, int> score;    // 键是 string，值是 int

    score["Li"] = 85;          // 用键赋值：键不存在就先插入再赋值
    score["Wang"] = 92;

    cout << "size = " << score.size() << '\n';
    cout << "Li 的成绩 = " << score["Li"] << '\n';

    for (const auto& p : score) {   // 每个元素是一个 pair<const string, int>
        cout << p.first << " " << p.second << '\n';
    }
    return 0;
}

输出：

size = 2
Li 的成绩 = 85
Li 85
Wang 92

逐行看：

• map<string, int> score; 创建一个空 map，键是 string，值是 int。
• score["Li"] = 85; 用中括号按键访问。因为 Li 这个键还不存在，map 会先插入一个值为默认值 0 的元素，再把它赋成 85。
• score.size() 是 2，说明 Li、Wang 各占一个元素。
• for (const auto& p : score) 遍历容器，p 是一个 pair<const string, int>，p.first 是键、p.second 是值。用 const auto& 是“只读地引用每个元素”，不复制、也不改动。
• 输出顺序是 Li 在前、Wang 在后：按键升序排列，和赋值顺序无关。

一步步看变化

用一组词 apple banana apple pear banana apple 统计每个词出现的次数，每读一个词就打印一次当前状态：

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

int main() {
    string words[] = {"apple", "banana", "apple", "pear", "banana", "apple"};
    map<string, int> cnt;

    for (const string& w : words) {
        cnt[w]++;              // 不存在就先插入 0，再 +1
        cout << "读入 " << w << " 后 size = " << cnt.size() << "，计数：";
        for (const auto& p : cnt) cout << p.first << "=" << p.second << " ";
        cout << '\n';
    }

    cout << "最终结果：\n";
    for (const auto& p : cnt) cout << p.first << " " << p.second << '\n';
    return 0;
}

输出：

读入 apple 后 size = 1，计数：apple=1 
读入 banana 后 size = 2，计数：apple=1 banana=1 
读入 apple 后 size = 2，计数：apple=2 banana=1 
读入 pear 后 size = 3，计数：apple=2 banana=1 pear=1 
读入 banana 后 size = 3，计数：apple=2 banana=2 pear=1 
读入 apple 后 size = 3，计数：apple=3 banana=2 pear=1 
最终结果：
apple 3
banana 2
pear 1

把每个词和计数变化对应起来：

• cnt[w]++ 一行的效果分两种情况：w 不在 map 里时，先插入一个值 0 的元素，再 +1；w 已经在时，直接 +1。所以统计词频只需要一行。
• 观察 size()：只有第一次见到某个词时才从 1 变大，重复的词不会增加键的个数。
• 最终输出按键升序：apple、banana、pear，和读入顺序 apple banana pear 不同也不影响结果。

逐项扩展核心操作

查找与计数：count、find

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

int main() {
    map<string, int> cnt = {{"apple", 3}, {"banana", 2}, {"pear", 1}};

    cout << "count(\"banana\") = " << cnt.count("banana") << '\n';
    cout << "count(\"kiwi\") = " << cnt.count("kiwi") << '\n';

    auto it = cnt.find("banana");
    if (it != cnt.end()) {
        cout << "find 命中：" << it->first << " " << it->second << '\n';
    }
    cout << "查询后 size = " << cnt.size() << '\n';
    return 0;
}

输出：

count("banana") = 1
count("kiwi") = 0
find 命中：banana 2
查询后 size = 3

• cnt.count(key) 返回键为 key 的元素个数。map 里一个键最多一个元素，所以结果是 0 或 1。banana 这个键存在，返回 1；kiwi 不存在，返回 0。注意 count 数的是元素个数，不是值的大小。
• cnt.find(key) 返回指向该元素的迭代器，找不到返回 cnt.end()。用之前先和 cnt.end() 比较。
• it->first 是键、it->second 是值（it->first 等价于 (*it).first）。所以 find("banana") 命中后打印出键 banana、值 2。
• 两次查询之后 size() 仍是 3，find、count 都不会插入。

find 不会插入，operator[] 会插入

这是 map 最容易踩的坑。下面用一个独立小例对比：先放一个键 apple，然后分别用 find 和 operator[] 去碰一个不存在的键 pear，每次都打印 size()：

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

int main() {
    map<string, int> cnt;
    cnt["apple"] = 3;

    cout << "初始 size = " << cnt.size() << '\n';

    // find 查不存在的键：不会插入
    auto it = cnt.find("pear");
    cout << "find(pear) 命中？" << (it != cnt.end())
         << "，之后 size = " << cnt.size() << '\n';

    // operator[] 查不存在的键：插入一个默认值 0
    int v = cnt["pear"];
    cout << "读 cnt[pear] 得到 " << v
         << "，之后 size = " << cnt.size() << '\n';

    // 现在这个键真的在容器里了，find 能命中
    cout << "find(pear) 现在命中？" << (cnt.find("pear") != cnt.end()) << '\n';
    return 0;
}

输出：

初始 size = 1
find(pear) 命中？0，之后 size = 1
读 cnt[pear] 得到 0，之后 size = 2
find(pear) 现在命中？1

所以：只想判断“这个键在不在”，用 find 或 count，不要用 operator[]。 否则一个只读的查询会悄悄改变容器，后面 size()、遍历结果都会多出不该有的键。

添加元素：insert 与下标

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

int main() {
    map<string, int> m;
    m["apple"] = 3;

    m["apple"] = 5;                    // 下标赋值：直接覆盖旧值
    cout << "下标赋值后 apple = " << m["apple"] << '\n';

    m.insert(make_pair("apple", 9));   // insert：键已存在则不覆盖
    cout << "insert 后 apple = " << m["apple"] << '\n';

    auto ret = m.insert(make_pair("pear", 1));
    cout << "插入新键 pear 成功？" << ret.second
         << "，pear = " << m["pear"] << '\n';
    return 0;
}

输出：

下标赋值后 apple = 5
insert 后 apple = 5
插入新键 pear 成功？1，pear = 1

insert 返回一个 pair<iterator, bool>：first 是指向该键元素的迭代器，second 表示这次是否真的插入了新元素。上面 insert(make_pair("apple", 9)) 因为 apple 已存在，没有插入，apple 的值仍是 5；insert(make_pair("pear", 1)) 是新键，second 是 1（真），插入成功。

注意：ret.second 为真表示插入成功，为假表示键已存在、没有插入。这两个含义不要记反。

删除元素

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

int main() {
    map<string, int> m = {{"apple", 3}, {"banana", 2}, {"pear", 1}};

    m.erase("banana");                 // 按键删除
    cout << "erase(banana) 后 size = " << m.size() << '\n';

    auto it = m.find("pear");
    if (it != m.end()) m.erase(it);    // 按迭代器删除
    cout << "erase(find(pear)) 后 size = " << m.size() << '\n';

    for (const auto& p : m) cout << p.first << " " << p.second << '\n';
    return 0;
}

输出：

erase(banana) 后 size = 2
erase(find(pear)) 后 size = 1
apple 3

修改键要“先删后插”

遍历得到的元素里，first 是 const，不能直接改：

// 错误示例：map 元素的键是 const，不能直接赋值修改
#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> m;
    m["apple"] = 3;

    auto it = m.begin();
    it->first = "pear";        // 编译错误：first 是 const，不能改
    return 0;
}

这段不能通过编译。如果确实要“改键”，只能先删除旧键、再插入新键：

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

int main() {
    map<string, int> m;
    m["apple"] = 3;

    int v = m["apple"];        // 先取出值
    m.erase("apple");          // 删掉旧键
    m["pear"] = v;             // 用新键存回去

    for (const auto& p : m) cout << p.first << " " << p.second << '\n';
    return 0;
}

输出：

pear 3

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

operator[] 会插入，find、count 不会。 这是 map 最危险的坑：m["x"] 即使只是读，只要 x 不存在就会插入一个默认值元素。只判断存在性时用 count 或 find；只有确实想新建或取值时才用 []。

迭代得到的是 pair<const Key, T>，键不能改、值能改。 用 it->first 读键、it->second 读写值。想换键必须“先删后插”。

默认按键升序，和插入顺序无关。 需要按值排序、或按别的规则排序，得把元素先搬进 vector 再 sort。

一个键只对应一个值。 如果同一个键要多条记录，用 multimap 一键多值。

复杂度 O(log n)。 按键查找、插入、删除都是 O(log n)。如果不需要有序、只要查找快，可以用 unordered_map（哈希表，平均 O(1)，选读）。

选读。 map 底层通常是红黑树，按键比较一步步下降，所以能保持有序。底层结构不是使用前提，掌握本页的操作就够了。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），接着最小示例的统计结果又读入了 banana 和 apple 两个词。请先手推出输出，再运行核对：

map<string, int> cnt = {{"apple", 3}, {"banana", 2}, {"pear", 1}};
vector<string> more = {"banana", "apple"};   // 再读入两个词

for (const string& w : more) cnt[w]++;

cout << "apple = " << cnt["apple"]
     << "，banana = " << cnt["banana"]
     << "，pear = " << cnt["pear"] << '\n';

第 2 题：修改代码

下面这段片段按键是字符串统计个数。请把它改成按整数编号统计 {5, 3, 5} 的出现次数，让输出变成两行 3 1 和 5 2（按编号升序）：

map<string, int> cnt;              // 键现在是字符串
vector<string> data = {"a", "b", "a"};
for (const string& x : data) cnt[x]++;

for (const auto& p : cnt) cout << p.first << " " << p.second << '\n';

验证条件：先说出 3 和 5 各出现几次、输出顺序如何，再运行核对。

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

int main() {
    map<string, int> cnt = {{"apple", 3}, {"banana", 2}, {"pear", 1}};
    vector<string> more = {"banana", "apple"};   // 再读入两个词

    for (const string& w : more) cnt[w]++;

    cout << "apple = " << cnt["apple"]
         << "，banana = " << cnt["banana"]
         << "，pear = " << cnt["pear"] << '\n';
    return 0;
}

apple = 4，banana = 3，pear = 1

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

int main() {
    map<int, int> cnt;                 // 键换成整数编号
    vector<int> data = {5, 3, 5};

    for (int x : data) cnt[x]++;

    for (const auto& p : cnt) cout << p.first << " " << p.second << '\n';
    return 0;
}

3 1
5 2

立即练习

两道题都只需要数组、循环和本页讲过的 map 操作。做完后请说明：为什么这里用 map 比用数组更合适？