一、map 长什么样

map<string, int> m;

    键（key，const）      值（value，可改）
    ┌──────────┬─────────┐
    │ "apple"  │    3    │   ← 一个元素 = 一个 pair<const string, int>
    │ "banana" │    2    │
    │ "cherry" │    1    │
    └──────────┴─────────┘
     按键自动升序排列（按 "apple" < "banana" < "cherry"）

set 和 map 的关系，一句话说完：

二、三种插入方式：哪种用在哪

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

int main() {
    map<string, int> m;

    // ── 方式① 下标赋值：最方便，但会"偷偷建"（详见下一节）──
    m["apple"] = 3;
    m["banana"] = 2;

    // ── 方式② insert + make_pair：不会覆盖已存在的值 ──
    m.insert(make_pair("cherry", 1));
    m.insert(make_pair("apple", 99));       // ★ apple 已存在 → 这一句不起作用

    // ── 方式③ insert + 花括号（C++11）──
    m.insert({"date", 5});

    cout << "内容：" << endl;
    for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
        cout << "  " << it->first << " -> " << it->second << endl;

    cout << "此时 m[\"apple\"] = " << m["apple"] << "（没被 99 覆盖）" << endl;
    return 0;
}

看到什么算成功：

内容：
  apple -> 3
  banana -> 2
  cherry -> 1
  date -> 5
此时 m["apple"] = 3（没被 99 覆盖）

两条关键差别：

insert 的返回值也是 pair<iterator, bool>（和 13.2.1 的 set 一样）。所以"别覆盖已有的"这件事可以这样写： cpp auto r = m.insert({"apple", 99}); if (!r.second) cout << "apple 已经有了，值是 " << r.first->second << endl;

三、这一节最重要的坑：m[k] 会"偷偷建"

operator[] 的行为：键存在 → 返回它的值的引用；键不存在 → 插入一个"值默认构造"的新元素，再返回它的引用。

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

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

    cout << "开始 size = " << m.size() << endl;

    if (m["banana"] > 0) {              // ★ 只是想"看一眼"
        cout << "banana 有值" << endl;
    }
    cout << "问完 banana 之后 size = " << m.size() << "  ← 多了一个！" << endl;

    for (const auto &p : m) cout << "  " << p.first << " -> " << p.second << endl;

    // ★ 正确的"只想查询"写法：用 find
    map<string, int> n;
    n["apple"] = 3;
    size_t before = n.size();
    if (n.find("banana") != n.end()) cout << "banana 在" << endl;
    else                             cout << "banana 不在" << endl;
    cout << "用 find 查完之后 size 还是 " << n.size() << "（没变：" << before << "）" << endl;
    return 0;
}

看到什么算成功：

开始 size = 1
问完 banana 之后 size = 2  ← 多了一个！
  apple -> 3
  banana -> 0
banana 不在
用 find 查完之后 size 还是 1（没变：1）

这张输出的教训值得单独记一页：

m["banana"] 只要被求值，就会往容器里插一个 banana -> 0。 你只是想"看一眼"，容器却被改了。这是 map 第一大坑。

结论： - 要"取值"、且确定键一定存在 → 用 []（或者更稳的 at()，越界会抛异常） - 要"查在不在"，可能不存在 → 必须用 find（或 count） - 绝不能写 if (m[k] != 0) 来"判断有没有" —— 这等于每次都往里塞一个

顺带认识 at()：m.at("banana") 不会插入，键不存在时抛 out_of_range（和 13.1.1 vector::at 的分工一致：[] 快、at 安全）。

四、遍历与修改

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

int main() {
    map<string, int> m = {{"数学", 95}, {"语文", 88}, {"英语", 92}};

    // ── ① 遍历：三种写法 ─────────────────
    cout << "① 长类型：";
    for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
        cout << it->first << "=" << it->second << "  ";
    cout << endl;

    cout << "② auto：  ";
    for (auto it = m.begin(); it != m.end(); ++it)
        cout << it->first << "=" << it->second << "  ";
    cout << endl;

    cout << "③ 范围 for：";
    for (const auto &p : m)                       // ★ const 引用：不复制 pair
        cout << p.first << "=" << p.second << "  ";
    cout << endl;

    // ── ② 改"值"：随便改（值不是 const）──
    m["数学"] = 100;
    cout << "改完 数学：" << m["数学"] << endl;

    // ── ③ 改"键"：不行！键是 const ─────────
    // m.begin()->first = "物理";                 // ❌ 报 assignment of read-only
    //  正确做法：删了再插
    int v = m["语文"];
    m.erase("语文");
    m["语文（新）"] = v;
    cout << "改键后：";
    for (const auto &p : m) cout << p.first << "=" << p.second << "  ";
    cout << endl;

    // ── ④ 删 ─────────────────────────────
    m.erase("英语");                              // 按键删
    m.erase(m.begin());                           // 按迭代器删（删第一个）
    cout << "删两次后剩 " << m.size() << " 项" << endl;
    return 0;
}

看到什么算成功：

① 长类型：数学=95  英语=92  语文=88  
② auto：  数学=95  英语=92  语文=88  
③ 范围 for：数学=95  英语=92  语文=88  
改完 数学：100
改键后：数学=100  语文（新）=88  
删两次后剩 0 项

注意两点：

1. 输出顺序是"数学、英语、语文" —— 不是字典序？其实中文的排序按的是字节（UTF-8 编码），所以和"读音/笔画"无关。英文场景才是标准的字典序（apple < banana < cherry）。这一条在实盘处理中文时要知道：想按拼音排，得自己写比较器（把中文转拼音再比）。
2. it->first / it->second —— 分别是那个 pair 的两个成员。first 是键、second 是值，这个命名约定在 STL 里到处都是。C++17 之后可以写得更清楚：for (const auto &[name, score] : m)。

五、动手 Demo：词频统计（map 最经典的用法）

任务：统计一段英文里每个词出现几次，按词频从高到低输出前几名。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string text =
        "the quick brown fox jumps over the lazy dog "
        "the dog barks and the fox runs away";

    // ── ① 计数：map 的看家本领，一句 cnt[w]++ ──
    map<string, int> cnt;
    stringstream ss(text);
    string w;
    while (ss >> w) cnt[w]++;              // ★ 没有就建（值 0），再 +1

    cout << "共 " << cnt.size() << " 个不重复的词" << endl;

    // ── ② 按字典序输出（map 自带）──
    cout << "-- 按字典序 --" << endl;
    for (const auto &p : cnt)
        cout << "  " << p.first << " -> " << p.second << endl;

    // ── ③ 按"次数"排序：map 做不到，要搬到 vector 里 ──
    vector<pair<string, int>> v(cnt.begin(), cnt.end());   // ★ 从 map 复制到 vector
    sort(v.begin(), v.end(), [](const pair<string, int> &a, const pair<string, int> &b) {
        if (a.second != b.second) return a.second > b.second;   // 次数多的在前
        return a.first < b.first;                               // 次数相同按字典序
    });

    cout << "-- 按出现次数排序（前 3 名）--" << endl;
    for (size_t i = 0; i < v.size() && i < 3; i++)
        cout << "  " << i + 1 << ". " << v[i].first << "（" << v[i].second << " 次）" << endl;
    return 0;
}

看到什么算成功：

共 15 个不重复的词
-- 按字典序 --
  and -> 1
  away -> 1
  barks -> 1
  brown -> 1
  dog -> 2
  fox -> 2
  jumps -> 1
  lazy -> 1
  over -> 1
  quick -> 1
  runs -> 1
  the -> 5
  ...
-- 按出现次数排序（前 3 名）--
  1. the（5 次）
  2. dog（2 次）
  3. fox（2 次）

这个 Demo 把本章三条线连起来了：map（13.2.3）计数 → vector（13.1.1）搬出来 → sort + lambda（13.3.3）换排序规则。

为什么必须"搬到 vector"：map 只能按键排序，它没有一个"按值排序"的用法（因为它的有序性是"由键决定的"，是容器的骨架）。"按值排序"这种需求，标准做法就是"复制到 vector 再 sort"。 这是 map 最常被问到的问题之一。

30 秒实验

1. [] 偷偷插入：写 map<string,int> m; cout << m["x"] << endl; → 输出 0，且 m.size() 变成 1。这一句"读操作"改了容器。
2. insert 不覆盖：m.insert({"x", 99}); cout << m["x"]; → 如果 x 已存在，输出旧值（不被 99 覆盖）。
3. at 会抛异常：map<string,int> m; cout << m.at("nope"); → terminate called after throwing an instance of 'std::out_of_range'。对比 m["nope"] 的"静默插入"。
4. 键不能改：m.begin()->first = "y"; → assignment of read-only location（因为 first 是 const string）。
5. map 的迭代器是双向的：写 sort(m.begin(), m.end()); → 编译不过。它自己已经按 key 排好了。

常见误区

1. "m[k] 只是读一下"——键不存在时它会插入一个默认值。这是 map 最著名的坑。 查在不在必须用 find。
2. "m[k] 和 m.at(k) 一样"——不一样：[] 不存在就插入；at 不存在就抛 out_of_range。"确定存在"用 []，"不确定"用 at（想看异常）或 find（想自己处理）。
3. "insert 会覆盖旧值"——不会，静默失败。要覆盖用 m[k] = v;。insert 的这个特性正好用来实现"只在没有时才加"。
4. "map 元素里的键可以改"——first 是 const，编译不过。要改键：erase 再 insert。（"值" second 随便改。）
5. "map 可以按值排序"——不可以。它只有"按键有序"这一种秩序。要按值排，复制到 vector 再 sort（本节 Demo）。
6. "map 里放指针很省事"——要管释放：map 析构不会 delete 值里的指针。要么直接存对象（推荐），要么存智能指针。
7. "map 的 [] 要求值类型什么都能行"——要求"值类型能默认构造"（因为要造那个"默认值"）。如果 V 没有默认构造函数，就不能用 []，只能用 insert / emplace。
8. "遍历 map 时改它没关系"——插入会让迭代器失效；删除只让被删的那个失效。 别在遍历中 insert。 要改就先记下来，遍历完再改。
9. "map 处理中文也是按拼音/笔画排的"——是按字节（UTF-8）排的，与读音无关。要按拼音排，需要自己写比较器。

• ☐ 下一节（13.2.4 multimap 类模板）

相关笔记

• multiset 类模板 —— 上一节：允许重复的键集
• multimap 类模板 —— 下一节：一个键对应多个值
• set类模板（含实例02） —— map 就是 set 加一个值
• 排序算法 —— 按值排序要用的 sort + lambda
• 简单类模板 —— pair / value_type 的来历
• 构造函数 —— operator[] 依赖"值类型能默认构造"
• 🔷 C++基础 · 索引 —— 全课路线图