map / set 红黑树容器完全指南：关联式容器的用法与选型

在之前的 STL 之旅里，我们已经见过了 string、vector、list、deque 这些老朋友。它们有一个共同点：每个元素只是一个个孤零零的值，元素和元素之间、位置和位置之间没有什么"内在联系"。比如 vector<int> 里放了 {1, 3, 5}，你把 3 和 5 换一下位，它依然是一个合法的 vector——因为对顺序容器来说，元素之间天然"各自为政"，顺序只是存储位置而已。这类容器，标准库给它们起了一个很正式的名字，叫序列式容器。

但编程里有一类非常高频的需求，是序列式容器搞不定的：我要按某个"关键字"去查东西。典型场景——给你一个单词，查出它对应的中文解释；给你一个学号，查出这个学生的成绩；给你一段文本，问某个单词出现了几次。这些需求里，数据不再是"一个挨一个排队"的序列，而是"一个关键字映射一个值"的配对关系。实现这类需求的容器，就叫关联式容器。今天这篇文章要讲的 std::map 和 std::set，以及它们的多副本兄弟 multimap / multiset，都属于这个家族。

学完这篇文章，你会明白：set 是怎么做到"唯一且自动有序"的；map 是怎么把"键值对"玩出花的；operator[] 到底藏了多少坑；multimap / multiset 和它们的单例版有什么区别；以及最后，什么时候该用红黑树这套，什么时候反而该投靠 unordered_map。别急，一个个来。

什么是关联式容器

先从概念上把它和序列式容器区分清楚。你可以这样理解：

序列式容器，就像一队排队买票的人，大家按到达先后站成一排。队伍的位置没有特殊含义，第 3 个人和第 4 个人换一下，队伍还是那个队伍。逻辑结构是线性的，元素存放在哪里，就按顺序保存和访问到哪里。

关联式容器，更像一本新华字典或一份通讯录。里面的条目不是按"先进来"排的，而是按"谁是什么"排的——每条记录都有一个关键字（key），比如单词本身、姓名、学号。你查的时候不是"从头找到尾"，而是"按关键字直接定位"。它的逻辑结构通常是非线性的（典型就是一棵树），两个条目之间有严格的"谁大谁小"的次序关系。要是你把两个条目强行对调，整个结构就被破坏了——因为它内部的有序性质是通过元素间的比较关系维系的，不是靠"第几格"维系的。

用一句话对照就是：序列式容器按存储位置保存和访问元素，关联式容器按关键字保存和访问元素。 换句话说，序列式做的是"集合/数组/链表"，关联式做的是"查找表/映射表"。

这句话值得再咂摸一下，因为它决定了你写代码时的直觉。拿到一个需求，先问自己：这是一个"排队存取"的问题，还是一个"按名字找人"的问题？排队存取用 vector/list/deque，按名字找人用 map/set。举个生活化的例子：你有一个班级花名册，想知道"张三的出生日期"，这是查表——用 map；你想按学号顺序把全班学生的信息一条条打印出来，这还是查表的副产品（因为 map 天然有序，遍历即有序）——但如果你只是想把一堆数据"存完再遍历一遍"，并没有"按关键字马上定位"的需求，那用 vector 反而更省事。工具的选择始终取决于"你怎么访问它"。

关联式容器的核心，是一个叫做"关键字（key）"的概念。所谓关键字，就是"用来标识并定位一条记录的那个独一无二的东西"。字典里是单词，通讯录里是姓名/号码，数据库里是主键。正是有了关键字，我们才能把"查找"从 O(N) 的挨个比较，提升到树形结构的 O(logN)。

关联式容器不止 map 和 set。我们后面会提到的 unordered_map、unordered_set 也是关联式容器。按底层实现不同，可以分成两条线：

• 红黑树家族（有序）：set / multiset / map / multimap，遍历天然有序。
• 哈希表家族（无序）：unordered_set / unordered_multiset / unordered_map / unordered_multimap，C++11 起才进入标准库。

这一章我们只围绕红黑树这一支来深挖。在讲 set 之前，先花三十秒把底层的"红黑树"说清楚，免得后面提到时你心里没底。红黑树本质上是一棵平衡二叉搜索树。二叉搜索树的规则很简单：对任意一个节点，它左子树里所有节点都比它小，右子树里所有节点都比它大，于是任意一次查找都像二分——每走一步就能扔掉一半的候选。但它有个致命弱点：如果插入顺序碰巧是有序的（比如从小到大连续插入），树会退化成一条"歪脖子"链表，查找效率从 O(logN) 直接掉到 O(N)。红黑树通过给每个节点涂上红/黑两种颜色，并维护一套"变色 + 旋转"的规则，强行保证树的高度差在可控范围内——具体来说，红黑树保证"最长路径不超过最短路径的两倍"，从而把整棵树的高度稳定在 O(logN) 量级，增删查也因此稳定在 O(logN)。你现在不需要能手写红黑树，只需要记住三个结论：它是一棵平衡二叉搜索树、它的节点有红黑两色、它的增删查效率是 O(logN)。地基打好了，下面就能放心盖楼了。

set 的使用：唯一且有序

set 类的基本介绍

先看 std::set 的模板声明（官方文档见 https://legacy.cplusplus.com/reference/set/）：

template < class T,                // set::key_type，也就是元素本身的类型
           class Compare = less<T>,// set::key_compare，默认按小于比较，即升序
           class Alloc = allocator<T> // set::allocator_type，空间配置器
           > class set;

三个模板参数里，第一个 T 是存进去的元素类型，这是你必须指定的；第二个 Compare 是比较方式，默认 less<T> 就是按"小于"升序，想降序就传 greater<T>；第三个 Alloc 是内存分配器，一般用不到。课件里专门强调了一句：如果元素类型本身不支持小于比较，或者你想按自己的规则排序，就自己写一个仿函数传给第二个模板参数。什么场景会用到？比如你要存一个自定义的 struct Person，默认没有 operator<，直接让 set<Person> 编译是过不去的，这时就得自己写个比较器。在日常做题和开发里，绝大多数情况下我们"都不需要传后两个模板参数"，保持默认即可。

这里我把"仿函数"顺带解释一下，因为它是第二个模板参数的关键。所谓仿函数（functor），就是一个重载了 operator() 的类或结构体，它能让"对象"像"函数"一样被调用。less<T> 就是标准库预定义好的一个仿函数，内部等价于"a < b 返回 bool"。你用 set<int> 时，Compare 就默认是 less<int>，红黑树在比较两个元素时就调用 less<int>()(a, b)，也就是判断 a < b。想降序就换 greater<int>，判断依据变成 a > b。你自己写的比较器只要永远满足三条性质——严格弱序（反对称、传递、不可比较的对象被视为等价）——就能被红黑树正确使用。写一个用于 struct Person 的比较器其实很简单：

#include <iostream>
#include <set>
#include <string>
using namespace std;
 
struct Person
{
    string name;
    int age;
};
 
// 自定义比较器：希望 set 里按"年龄"升序排序
// 这样就不需要给 Person 重载 operator< 了
struct CmpByAge
{
    bool operator()(const Person& a, const Person& b) const
    {
        return a.age < b.age;
    }
};
 
int main()
{
    set<Person, CmpByAge> group;
    group.insert({"小明", 20});
    group.insert({"小红", 18});
    group.insert({"小刚", 22});
 
    for (const auto& p : group)
    {
        cout << p.name << " " << p.age << endl;
        // 输出（按年龄升序）：
        // 小红 18
        // 小明 20
        // 小刚 22
    }
    return 0;
}

注意上面这段代码里有个必须想明白的点：set<Person> 里的元素，唯一性判断也是走同一个比较器的。两个 Person 只要"年龄相等"，就被视为同一个元素，第二次插入会被静默丢弃——哪怕它俩姓名不同。这是关联式容器一个微妙但极其重要的语义："相等"的定义，完全由你给的比较器说了算。以后你踩"哎我怎么插不进两个东西"的坑，多半就栽在这。在 C++14 及以后，std::less<> / std::greater<> 还支持了"透明"的菱形模板写法（也就是 set<int, std::less<>>），它允许你用和 key 不同类型的东西去查找（即异构查找），这在后面讲到查找时会有用武之地。

set 有两个极易被忽略却极其重要的特性，请务必刻进脑子里：

第一，元素唯一。 同一个值最多存一份，重复插入会被静默丢弃。这正好可以拿来"去重"。

第二，遍历有序。 set 底层是红黑树，而迭代器遍历走的是搜索树的中序遍历（左子树 → 根 → 右子树），所以从 begin() 一路走到 end()，元素天然是升序的。换句话说——你插入的时候乱序插，取出来的时候它是排好序的，连排序的代码都省了。这两个特性叠加，就是经典三字诀：去重 + 排序。

"中序遍历"这个词值得稍微展开，因为它解释了"为什么 set 遍历一定有序"。中序遍历的规则是：先访问左子树、再访问根、最后访问右子树。回想二叉搜索树的性质——左子树都比根小、右子树都比根大——那么一个节点在遍历中"正好出现在所有比它小的元素之后、所有比它大的元素之前"，全树走完，自然就是严格的从小到大。而且这不只是"看起来有序"：你游标每向前 ++ 一步并解引用得到的元素，一定比上一步拿到的元素更大——也就是每一步上"新元素 > 旧元素"都严格成立，和数学里的"全序关系"一一对应。反向迭代器 rbegin() 到 rend() 就正好倒过来，是降序。

下面立刻用代码验证，这比背文档有用十倍：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    set<int> s;                 // 定义一个空 set，存 int，默认升序
 
    s.insert(5);                // 插入 5
    s.insert(2);                // 插入 2
    s.insert(7);                // 插入 7
    s.insert(5);                // 重复插入 5，插入失败，被静默丢弃
 
    // 用正迭代器遍历，底层走中序，输出一定是有序的
    auto it = s.begin();
    while (it != s.end())
    {
        // *it = 1;             // 这一行编译会报错！set 的元素是只读的（原因见下）
        cout << *it << " ";     // 输出：2 5 7
        ++it;
    }
    cout << endl;
 
    // 再插入一段 initializer_list，其中 2 和 8 已存在（2 存在，8 不存在）
    s.insert({2, 8, 3, 9});
    for (auto e : s)            // 支持范围 for，本质也是迭代器遍历
    {
        cout << e << " ";       // 输出：2 3 5 7 8 9
    }
    cout << endl;
 
    // string 也一样：按"字典序"（逐个比较 ASCII/编码）自动排序
    set<string> strset = {"sort", "insert", "add"};
    for (auto& e : strset)
    {
        cout << e << " ";       // 输出：add insert sort
    }
    cout << endl;
    return 0;
}

如果想倒过来要降序呢？只需在模板时把比较器换成 greater<int>。加一行就够：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    set<int, greater<int>> s = {4, 2, 7, 2, 8, 5, 9};  // 升序比较器换成大于
    for (auto e : s)
    {
        cout << e << " ";       // 降序：9 8 7 5 4 2
    }
    cout << endl;
    return 0;
}

注意上面被注释掉的那一行 *it = 1;。我来解释为什么它编译不过：set 里存的是"关键字"，而关键字直接决定了红黑树的形态（哪个节点往左走、哪个往右走全靠它）。如果你能随便改一个元素的值，就可能破坏"左小右大"的次序，整棵树的结构就崩了。所以标准库干脆釜底抽薪——set 无论用普通迭代器还是 const 迭代器，指向的元素都是只读的，类型上是 iterator -> a bidirectional iterator to const value_type。换句话说，"const 化"的不是迭代器本身，而是它解引用出来的元素。你可以在 VS 里试一下，会得到一个形如 error C3892: "it": 不能给常量赋值 的编译错误，报错点正是这里。

顺带强调"双向迭代器"（bidirectional iterator）这个说法：set 的迭代器只能 ++（前进）和 --（后退），不能做 it + 3 这种随机跳转——因为树节点在内存里不是连续排列的，没有"第几个"的概念，只能沿着前驱/后继链接走。这跟 vector 的随机访问迭代器（random access iterator，可以 it + n、it[n]）形成了鲜明对比。所以 set 不能像 vector 那样按下标访问，也没有排序算法里的 sort 可用（std::sort 要求随机访问迭代器）。这一点后面聊到"能用哪些算法"时还会反复出现。

反向迭代器

set 不仅支持正向迭代，还支持反向迭代。rbegin() 指向"最后一个元素"、rend() 指向"第一个元素之前"，把反向迭代器从 rbegin() 一路走到 rend()，正好是从大到小的降序遍历：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    set<int> s = {4, 2, 7, 2, 8, 5, 9};   // 列表构造，重复的 2 只保留一个
    for (auto e : s)
        cout << e << " ";                 // 升序：2 4 5 7 8 9
    cout << endl;
 
    // 反向迭代：rbegin 是最后一个，每次 ++ 往前移动，故为降序
    for (auto rit = s.rbegin(); rit != s.rend(); ++rit)
    {
        cout << *rit << " ";              // 降序：9 8 7 5 4 2
    }
    cout << endl;
    return 0;
}

这里顺带引入一个重要的构造方式：initializer_list 构造，也就是 set<int> s = {4, 2, 7, 2, ...} 这种用花括号直接给初值的写法，C++11 起可用，非常直观。set 的构造总共就关注几类：无参默认构造、迭代器区间构造（set<int> s(v.begin(), v.end())）、拷贝构造、以及上面这种 initializer_list 构造。

迭代器区间构造特别值得多说一句，因为它是一个"让 set 去做第一遍去重+排序"的捷径：把一个 vector 或别的容器整体丢给 set 的构造器，set 会边插入边去重边排序，一次就得到一个有序且无重复的集合。后面讲力扣 349 求交集时正好用上它。

set 的增删查：insert / erase / find / count

讲几个 set 最核心的操作接口。先看插入：

• pair<iterator,bool> insert(const value_type& val)：插入单个元素。如果值已存在，插入失败，返回的 pair 中 second 为 false；插入成功则 second 为 true，first 总是指向该元素所在迭代器。
• void insert(initializer_list<value_type> il)：一次性插入一串，已存在的自动被跳过。
• template<class InputIterator> void insert(first, last)：把一个迭代器区间的元素整体插入，同样会自动去重。

insert 的单元素版本还有一个被很多人忽略的重载：insert(hint, val)，hint 是一个"提示位置"的迭代器。如果你恰好知道新元素应该插在 hint 附近，给它一个正确的提示，插入的查找过程会从 O(logN) 优化到接近 O(1)（均摊）。这在"连续插入一段本来就有序"的序列时，能带来不小的性能收益。面试如果问到"如何批量高效地往 set 里灌一个有序序列"，答案常常就是"带上 hint"。

再看查找与删除，以及两个很容易混淆的取边界接口：

有两个关于查找效率的点特别值得强调。第一个：set 自带的成员函数 find 走的是红黑树查找，复杂度 O(logN)；而如果用算法库里的 std::find(s.begin(), s.end(), x)，它是在一段线性序列里挨个比较，复杂度是 O(N)。同样是"找"，差了整整一个量级——所以查 set 一定要用成员函数版本的 find。这个坑的隐蔽之处在于：两种 find 你用 s.find() 写了都对，但一旦你手滑写成 find(s.begin(), s.end(), x)（不带对象名，直接调算法库），编译器照样能编过，只是性能悄悄变 O(N) 了。第二个：count 在 set/map（不重复的容器）里永远只返回 0 或 1，于是很多人把它当"是否存在"的快速判断用，写 if (s.count(x)) ——这也是一种完全合法的惯用法，而且同样走红黑树、O(logN) 复杂度，和 find 效率一致。不过在 C++20 里官方更推荐用成员函数 contains(x)（直接返回 bool，语义更清晰），你的编译器如果支持 C++20，可以优先考虑它。三者对比：find 适合"我要拿到那个元素并继续操作"；count/contains 适合"我只想知道在不在"（contains 只在 C++20 存在，老代码用 count）。

关于 erase，还有一个必须提的迭代器失效话题。顺序容器（vector 等）删除元素后，指针和迭代器常常"失效"（指向了错误的位置）；但红黑树的节点是独立分配在堆上的，删除某个节点只影响它自己。所以：用 erase(位置迭代器) 删除一个 set 的元素时，只有指向被删元素的迭代器失效；指向其他元素的迭代器、以及所有指向剩余元素的引用和指针，一律继续保持有效。 这也是为什么在遍历中删除 set 元素比遍历中删除 vector 元素安全得多。但要注意一点：erase 返回的是被删元素的下一个迭代器（对 set 而言是这样的），如果你在循环里写了 ++it 去推进，务必先取好下一个位置，或者直接利用返回值；删除本身并不破坏循环结构，因为树会自平衡。

下面用一个尽量完整的程序，把增删查和取边界的典型用法串起来。这次我保留了课件里"读入 x 再操作"的思路，但为了让程序能独立、无输入也能跑完，我们直接给 x 赋值：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    set<int> s = {4, 2, 7, 2, 8, 5, 9};   // 去重后实际是 {2,4,5,7,8,9}
    for (auto e : s)
        cout << e << " ";                 // 2 4 5 7 8 9
    cout << endl;
 
    // 删除最小值：删除 begin() 位置，也就是整个 set 最小的那个元素
    s.erase(s.begin());                   // 删掉 2
    for (auto e : s)
        cout << e << " ";                 // 4 5 7 8 9
    cout << endl;
 
    // 按值删除：erase(值) 返回删除个数（set 里要么 0 要么 1）
    int num = s.erase(7);                 // 7 存在，返回 1
    if (num == 0)
        cout << "7 不存在！" << endl;
    for (auto e : s)
        cout << e << " ";                 // 4 5 8 9
    cout << endl;
 
    // 先 find 再按迭代器删：标准三步走
    int x = 8;
    auto pos = s.find(x);
    if (pos != s.end())
        s.erase(pos);                     // 找到才敢删，避免对 end() 解引用
    else
        cout << x << " 不存在！" << endl;
    for (auto e : s)
        cout << e << " ";                 // 4 5 9
    cout << endl;
 
    // 用 count 快速判断"在不在"
    if (s.count(x))                       // x = 8 已被删掉，count 返回 0
        cout << "8 在！" << endl;
    else
        cout << "8 不存在！" << endl;
    return 0;
}

请你一定重视上面那个 if (pos != s.end()) 的判断。对 end() 解引用是未定义行为，它是引用悬空、读野地址、程序崩溃的原罪之一。所以凡是 "find 后再操作返回的迭代器"，都务必要先判空。这条铁律在 map 的 find、lower_bound 里同样适用。

lower_bound 与 upper_bound：拿走一段区间

lower_bound 和 upper_bound 一起用，常常能优雅地实现"删除一整段范围的值"。它们的语义是查找边界：lower_bound(val) 返回第一个 大于等于 val 的位置，upper_bound(val) 返回第一个 大于 val 的位置。想象你在溶液中插入 val，它会落在哪个位置：lower_bound 是它"该插进去时的 >= 起点"，upper_bound 是它"该插进去后的 > 终点"——两者夹出来的 [lower, upper) 正好是所有 等于 val 的元素区间（在 multiset 里尤其有用）。正因为这种"左闭右开"的语义，你才能用它优雅地划走一整段。看下面这个例子：我们想让 set 里最终只剩 10 20 30 40 50 60 70 80 90 中"30 到 60 之外"的部分，也就是删掉 [30, 60] 这一整段：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    std::set<int> myset;
    for (int i = 1; i < 10; i++)
        myset.insert(i * 10);             // 插入 10 20 30 40 50 60 70 80 90
    for (auto e : myset)
        cout << e << " ";                 // 10 20 30 40 50 60 70 80 90
    cout << endl;
 
    // lower_bound(30)：返回第一个 >=30 的迭代器（指向 30）
    auto itlow = myset.lower_bound(30);
    // upper_bound(60)：返回第一个 >60 的迭代器（指向 70）
    auto itup = myset.upper_bound(60);
    // 删除 [itlow, itup)，即 [30, 70) 里的 30 40 50 60
    myset.erase(itlow, itup);
 
    for (auto e : myset)
        cout << e << " ";                 // 10 20 70 80 90
    cout << endl;
    return 0;
}

注意这里区间是左闭右开的：它把 30 删了，把 60 也删了（[30, 60] 全含），但 70 因为 upper_bound(60) 是"第一个大于 60 的元素"而幸免。这个"左闭右开"语义和 STL 的迭代器区间习惯完全一致（[first, last) 永远不含 last），理解后就不会钻牛角尖了。请你务必记住 lower_bound 与 upper_bound 的微妙差别：前者含等于，后者不含等于。这一字之差，就是删除范围封口与不封口的区别。

set 还提供了 equal_range(val)，它把 lower_bound 和 upper_bound 打包成一个 pair<iterator,iterator> 返回，也就是"所有值等于 val 的区间"。在 set（唯一）里这个区间要么空要么只有一个元素；但它在 multiset 里才是真正发光的地方——那正是下一节的主角。

multiset：允许重复

multiset 和 set 长得几乎一模一样，唯一的本质区别就三个字：允许重复。有了重复，那套围绕"唯一性"设计出来的接口行为就会跟着变，这是最容易踩坑的地方。我们在接口层面逐一对照：

• 遍历：set 去重 + 升序；multiset 只排序、不去重。插入 {4,2,7,2,4,8,4,5,4,9} 后，set 会收成 {2,4,5,7,8,9}，而 multiset 会老实排成 {2,4,4,4,4,5,7,8,9}——4 和 2 各留了几份就是几份。插入的"第几份"是按中序遍历次序排的，重复值彼此相邻。
• find：在 set 里找到唯一那一个；在 multiset 里重复值有好几个，find 返回的是中序遍历遇到的第一个，不是任意一个（虽然重复值彼此相等，但它确实是最左侧那个）。想拿到"下一个"就去 ++ 它，再用循环把连续相等的都找出来。
• count：set 里是 0 或 1；multiset 里返回真实的重复个数。
• erase(值)：set 里删一个；multiset 里会把所有等于该值的元素全部删光，返回值是被删掉的个数。这一点最容易让人措手不及——你可能只想删一个，结果整个值全没了。如果只想删重复中的"一个"，请用 find 拿到迭代器再用 erase(位置迭代器)。

下面这段代码，把上面每一条都现场验证一遍：

#include <iostream>
#include <set>
using namespace std;
 
int main()
{
    // multiset：排序但是不去重
    multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    for (auto e : s)
        cout << e << " ";                 // 输出：2 2 4 4 4 4 5 7 8 9
    cout << endl;
 
    // 用 find 找到的只是"中序的第一个 4"
    auto pos = s.find(4);
    while (pos != s.end() && *pos == 4)   // 从第一个 4 往后把连续等值的都打出来
    {
        cout << *pos << " ";              // 输出：4 4 4 4
        ++pos;
    }
    cout << endl;
 
    // count 返回真实个数
    cout << s.count(2) << endl;           // 输出：2
 
    // erase(值) 会删除所有该值
    s.erase(4);                           // 四个 4 全没了
    for (auto e : s)
        cout << e << " ";                 // 输出：2 2 5 7 8 9
    cout << endl;
 
    // 只想删重复中的"一个"怎么办？用 find + 迭代器删除
    auto it = s.find(2);                  // 指向第一个 2
    if (it != s.end())
        s.erase(it);                      // 只删掉这一个 2
    for (auto e : s)
        cout << e << " ";                 // 输出：2 5 7 8 9
    cout << endl;
    return 0;
}

所以如果你需要的是"可重复的多重集合"，就用 multiset；如果只是想要"去重 + 排序"，set 就够了，别多建一个 multiset 给自己挖重复元素的坑。给错了词，行为全变，底层同一棵树。 记住：multi 前缀只改"能不能重复"这一件事，其余（有序、红黑树、O(logN)）一概不变。

map 的使用：key-value 键值对

set 处理的是"一个关键字"的纯搜索场景，而 map 处理的是"关键字映射到值"的 key/value 搜索场景。打个比方：set<int> 是一份"数字名单"，只能回答"某数字在不在名单里"；map<string,int> 是一份"单词 -> 出现次数"的对照表，不仅能回答"在不在"，还能告诉你"它对应的值是多少"。

先把它们的关系用一句话钉死：set 是只有 key 的 map，map 是 key 上多了个 value 的 set。 底层同是红黑树，差别只在节点里多存了一个 value。如果你已经把前面的 set 吃透，map 的一半你已经会了——剩下的一半，全跟"那个 value 和它的访问方式"有关。

先看模板声明（官方文档见 https://legacy.cplusplus.com/reference/map/）：

template < class Key,                       // map::key_type，关键字类型
           class T,                         // map::mapped_type，映射值类型
           class Compare = less<Key>,       // map::key_compare，默认按 key 升序
           class Alloc = allocator<pair<const Key,T>> > // 空间配置器
           > class map;

注意几个英文名容易绕晕的地方：Key 是关键字类型（叫 key_type），T 是映射值类型（官方叫 mapped_type，不过日常口头我们还是讲它叫"value"）；而我们下面马上要讲的 value_type，指的是红黑树节点里真正存的那一整个键值对，也就是 pair<const Key, T>。这三者的关系搞清楚了，后面看 map 的各种接口就顺了。一句口诀：key 定排序、value 定内容、pair 是个整体。 map 的红黑树在比较两个节点时，只用节点的 key 去比较；所以"排序依据"是 Key，"可修改或承载业务"的是 T。

前置知识：pair 是什么

map 的元素是"关键字 + 值"的组合，标准库用一个叫 std::pair 的小工具把这两个东西打包在一起。pair 就是"一对值"的意思，它有两个成员：first 和 second。它的简化定义大致长这样：

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;           // 第一个元素
    T2 second;          // 第二个元素
 
    pair() : first(T1()), second(T2()) {}        // 默认构造会做零初始化
    pair(const T1& a, const T2& b) : first(a), second(b) {} // 两参构造
};

pair 本身无所属，它可以被 vector<pair<string,int>>、priority_queue 等所有容器使用，是 C++ 里极其常见的一种"装两个相关数据"的工具。对应的还有一个全局工厂函数 make_pair(x, y)，后面插入 map 时会用到——它最大的好处是能自动推导类型，你不用手写 pair<string,string>，直接 make_pair("sort","排序") 就返回一个 pair<const char*, const char*>，再被隐式转换成容器需要的类型。map 底层红黑树节点里存的数据，类型就是 pair<const Key, T>——注意 Key 前面有个 const，这和 set 里元素只读是同一个道理：key 是树的排序依据，绝不能改。

另外提前给你一个锦上添花的特性：结构化绑定（structured binding，C++17 起）。遍历 map 时，与其用 e.first / e.second 去抠 pair 的成员，不如直接在语句里声明两个名字，编译器自动帮你拆包：

for (const auto& [key, value] : dict)
{
    cout << key << ":" << value << endl;
}

[key, value] 就是结构化绑定声明，它等价于"把每个元素（一个 pair）的 first 绑到 key、second 绑到 value"。这是 C++17 以后的推荐写法，代码瞬间清爽一个量级。注意：它只改变"取访方式"，不改变底层仍是 pair 的事实；如果你要在遍历中修改 value，请写成 auto& [key, value]，但千万别把 key 也取成可修改的引用——key 是 const，改了是要出大事的。

这里我还想多讲一个符号层面的坑：迭代器的 ->。map 的迭代器解引用（*it）得到 pair<const Key, T> 这个对象，it->first 等价于 (*(it)).first。为什么 it->first 能直接访问成员？因为迭代器的 operator-> 返回的是指向 pair 的指针，然后编译器再用一次 -> 去解指针取 first——也就是 it->first 其实经历了两次箭头：第一次是迭代器的重载 -> 拿到 pair 地址，第二次是内置 -> 取成员。这也是"省略了一个 ->"的原因。写多了你会习惯，但知道底层是什么，报错时就不会懵。

map 的几种构造与插入方式

map 的构造和 set 高度相似：无参默认构造、迭代器区间构造、拷贝构造、initializer_list 构造。但插入就有点讲究了——因为它要插入的是"键值对"，你得先学会构造一个 pair。这里一共有四种常用写法，从生疏到顺手，逐一看一遍：

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // initializer_list 构造：每一组花括号都是一个"键值对"
    map<string, string> dict = {
        {"left", "左边"},
        {"right", "右边"},
        {"insert", "插入"},
        {"string", "字符串"}
    };
 
    // 迭代遍历：it 指向的是 pair，it->first 取 key，it->second 取 value
    for (const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
        // 按 key 升序输出：insert/left/right/string
    }
    cout << endl;
 
    // ---------- 四种插入方式对比 ----------
    // 方式一：先建好一个 pair 对象，再插入
    pair<string, string> kv1("first", "第一个");
    dict.insert(kv1);
 
    // 方式二：临时构造一个匿名 pair 对象
    dict.insert(pair<string, string>("second", "第二个"));
 
    // 方式三：用工厂函数 make_pair（会自动推导类型）
    dict.insert(make_pair("sort", "排序"));
 
    // 方式四：initializer_list 形式，最简洁，C++11 起支持
    dict.insert({"auto", "自动的"});
 
    // 注意：key 已存在则插入失败，value 不同也一样失败
    dict.insert({"left", "左边，剩余"});   // "left" 已存在，这行不会更新它
 
    // 再遍历一遍，验证上面这些 key 都进去了
    for (const auto& e : dict)
    {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

请务必注意最后那一条注释背后的语义：map::insert 永远不会修改已经存在的 key 对应的 value。就算你写 dict.insert({"left", "左边，剩余"})，只要 "left" 已经在 map 里，这一行就静默失败，"left" 的 value 仍是原来的 "左边"，不会被覆盖。这一点和 map["left"] = "新值" 是截然不同的——后者是修改，前者是"我只想在没有时才插入"。想清楚你的意图，是"存在就跳过"还是"存在也覆盖"，再决定用哪个。这是 insert 与 operator[] 最本质的角色分工。

仔细看看 insert 的返回值

map 的插入接口是 pair<iterator,bool> insert(const value_type& val)，这里一口气出现了两个 pair，很多人一眼就懵。我拆开讲：

• 第一个 pair 是参数 val 的类型，也就是红黑树节点里存的 pair<const Key, T>，它表示"我要插入的这个键值对"，来自上面所说的几种写法。
• 第二个 pair 是 insert 的返回值 pair<iterator, bool>。它的 first 是一个迭代器，second 是一个 bool。

这两个 pair 的职责完全不同，千万别混。关于返回值的 pair<iterator,bool> 到底是什么意思，写清楚就是：无论插入成功还是失败，返回 pair 的 first 一定指向"这个 key 最终所在的节点迭代器"；second 告诉你这次到底插没插进去——插进去了是 true，发现 key 已存在（哪怕 value 不同）就插失败，是 false。

这条信息里藏着两个宝藏。第一个，既然 first 在你需要的位置，你就可以"插入后立刻接着用返回的迭代器去操作"，不必再 find 一次。第二个，也是最关键的——insert 失败时，它充当了一次"查找"。因为它返回的迭代器照样指向那个已存在的 key 的节点。正是这个"insert 失败 = 免费查找"的特性，让标准库得以实现下面要讲的 operator[]。这句话是理解 operator[] 的钥匙，我们先记住它，马上就能用上。

查找与修改：通过迭代器改 value

map 查 key 的接口和 set 查值几乎一模一样（find / count / erase / lower_bound / upper_bound），要声明的是：map 的这些接口只按 key 查，不看 value。唯一差别是map 用 key 来查，而且 find 返回的迭代器不仅能确认 key 在不在，还能通过 it->second 修改映射值。课件里有一个经典示范——统计一堆水果各出现了几次，先用"find + 迭代器"这种最直白的方式写：

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;
 
    for (const auto& str : arr)
    {
        // 1、先查这个水果在不在
        auto ret = countMap.find(str);
        if (ret == countMap.end())
        {
            // 2a、不在：第一次出现，插入 {水果, 1}
            countMap.insert({str, 1});
        }
        else
        {
            // 2b、在：把查到的节点里对应次数 +1
            ret->second++;
        }
    }
 
    for (const auto& e : countMap)
    {
        cout << e.first << ":" << e.second << endl;
        // 按 key 升序输出（此处按中文字符编码序）：
        // 西瓜:3  苹果:6  香蕉:2
    }
    return 0;
}

这段逻辑完全正确，但你能感觉到它有点麻烦：既要 find，又要判断在不在，还要分别处理"插入"和"自增"。注意上面 ret->second++ 这行——它之所以合法，是因为普通迭代器解引用得到的 pair 里，second（value）不是 const 的，可以原地修改；而 first（key）是 const 的，改它编译就报错。map 其实给了我们一个偷懒神器——operator[]，下一节细讲。

operator[] 的访问与坑（自动插入默认值）

先抛结论：map 的 operator[]（方括号语法）是一个"一箭三雕"的复合接口，它同时具备 插值、查值、改值 三种能力，但代价是——如果你用不存在的关键字去访问，它会静默地插入一个"默认值"节点。 这是使用 map 最容易踩的坑，也是它最强大的地方。

要理解它，最好的方式是直接看它的标准实现逻辑。文档给出 operator[] 的内部道理大致是这样的：它内部其实就是调了一下 insert，利用了我们上一节那句话——"插入失败时，返回的迭代器也会指向该 key 所在的节点"。

// 概念示意：operator[] 的实际行为等价于下面的逻辑
mapped_type& operator[](const key_type& k)
{
    // 用 {k, 默认值} 去 insert
    // 1、k 不在 map 中：insert 会真的插入这个 {k, 默认值}，
    //    返回的迭代器指向新插入节点
    // 2、k 已经在 map 中：insert 失败（告诉它"已经有了"），
    //    但返回的迭代器照样指向已存在的那个节点
    pair<iterator, bool> ret = insert({k, mapped_type()});
    iterator it = ret.first;      // 无论哪种情况，it 都指向 k 所在节点
    return it->second;            // 返回节点里 mapped_type 值的引用
}

（上面是概念示意代码，标准库真实实现的写法是 return (*((this->insert(std::make_pair(k, mapped_type()))) .first)).second;，思路完全一致。）

先解释那个 mapped_type()：这是"默认构造"。对 int 它得到 0，对 string 它得到一个空字符串，对 double 得到 0.0——它就是"这个类型的零初始值"。所以每次 map["新key"] 触发的自动插入，插入的都是这个默认值。再解释返回类型 mapped_type&：operator[] 返回的是一个引用，所以你可以直接对它赋值 m["a"] = 1，也可以直接读它 cout << m["a"]，还可以直接自增 m["a"]++。引用是"能改"的物质基础。

看到这里你就明白 operator[] 的全部秘密了：它永远先保证"这个 key 节点存在"，然后返回该节点 value 的引用。 于是不同场景表现如下：

• dict["insert"]; —— key "insert" 不存在，于是先插入了 {"insert", string()}，value 是空字符串的默认值，返回它的引用。这里产生了副作用：map 里凭空多了一个空字符串节点。
• dict["left"] = "左边"; —— key 不存在，插入 {"left", 空串}，然后把返回的引用赋值成 "左边"。这是"插入 + 修改"二合一。
• dict["left"] = "左边、剩余"; —— key 已存在，直接修改它的 value。这是纯"修改"。
• cout << dict["left"]; —— key 已存在，拿到 value 读取。这是纯"查找"。

用上面这几条把 operator[] 的行为验证一遍，胜过看十段文档：

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));   // 先手动插一个
 
    // key 不存在 -> 插入 {"insert", 默认空串}，value 为空
    dict["insert"];
    // 插入 + 修改：先插 {"left", 空串}，再把空串改成 "左边"
    dict["left"] = "左边";
    // 修改：key 已存在，直接覆盖 value
    dict["left"] = "左边、剩余";
    // 查找：key 已存在，读取 value
    cout << dict["left"] << endl;             // 输出：左边、剩余
 
    // 注意：这里"insert"对应的 value 是空字符串，说明访问即插入产生了默认节点
    cout << "[" << dict["insert"] << "]" << endl; // 输出：[]
    return 0;
}

注意上面 dict["insert"]; 之后我立刻再 dict["insert"]——第二次访问时 key 已经在了，不会重复插入。你可以在中间用 dict.size() 打印验证：第一次 [] 之后 size 从 1（只有 sort）变成 2（多了 insert）。

这里的坑在哪？用 operator[] 去"查询"一个可能不存在的 key，是有副作用的——它会把不存在的 key 连带一个默认值插进 map。经典翻车现场就是：本来想查一个词在不在字典里就 if (m[key])，结果凭空给自己 map 塞了一堆空条目。等你想遍历这个 map 时，会惊讶地发现里面多了无数个 value 为默认值的"幽灵节点"。所以：纯粹只想"查在不在 / 读 value"，绝对不要用 []。

那"只读不写、不存在也不该插入"到底用什么？两个正解：

• if (m.count(key)) 或 if (m.contains(key))（C++20）——只判在不在，不插入。
• auto it = m.find(key); if (it != m.end()) use(it->second);——想拿到 value 改就用它；find 绝不会插入。

如果你既想"安全读回 value"，又不想用 find 那一长串，C++11 起还有个成员函数 at(key) 专门干这个：它像 [] 一样返回 value 的引用，但当 key 不存在时不会插入默认值，而是抛出一个 std::out_of_range 异常。它和 [] 的分工是一体两面：[] 亲近"我要写"，at 亲近"我要读且接受异常"。面向高频读取、且 key 应当存在的场景，at 是比 [] 更安全的选择。不过要注意：用 at 时得准备好 try/catch，否则 key 一不存在程序就抛异常退出。

当然，反过来，利用它的自动插入默认值，operator[] 在"统计次数"这类场景里就是神器。把上节那个水果统计用 [] 重写，简洁得让人想鼓掌：

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;
 
    for (const auto& str : arr)
    {
        // key 不存在：先插入 {str, 0}，再把返回的引用 ++ 成 1，即"第一次出现算 1 次"
        // key 存在：  直接对已有次数 ++
        countMap[str]++;
    }
 
    for (const auto& e : countMap)
    {
        cout << e.first << ":" << e.second << endl;  // 西瓜:3 苹果:6 香蕉:2
    }
    return 0;
}

仅仅一行 countMap[str]++，就同时完成了"查找 + 插入默认值 + 自增"，把 find 那一大坨对比得明明白白。为什么第一次出现是 1 而不是 1 以下？因为 countMap[str] 第一次执行，先插入 {str, 0}（int 的默认值 0），返回 0 的引用，++ 之后变成 1。原有的"find 四行写法"在这里被压成一行。这就是为什么大家统计词频时几乎都用 []。

需要交代一句版本差异：operator[] 从早期 C++ 就有；而它配合 initializer_list（也就是 {key, value} 这种花括号写法）是在 C++11 引入的。如果你的编译器老到不支持 C++11（比如某些古董嵌入式环境），请改用 make_pair 或直接构造 pair。

到底哪些能改、哪些不能改？

把刚才讲到的规律总结成一张小表，做题面试时对照着用：

multimap：允许 key 重复

multimap 是 map 允许 key 重复的版本，行为差异和 multiset 之于 set 一模一样：find 返回中序遍历遇到的那个 key 的第一个匹配；count 返回该 key 出现的次数；count/erase(值) 会作用于所有匹配。erase(值) 同样是"把所有匹配的 key 对应的节点全删光"，返回被删的个数；想只删一个就 find 后 erase(位置)。其余的构造、遍历、lower_bound/upper_bound 也完全照搬。这里就不再重复代码了，只有一个新增的坑必须单独点名：

multimap 不支持 operator[]。 理由很直白：operator[] 的核心能力是"返回某个 key 对应 value 的引用，好让你改它"。可一旦允许 key 重复，同一个 key 可能对应好几个 value，m[key] 返回值到底该返回哪一个？根本无法确定。所以 multimap 干脆没有 []。这一点和 map 形成鲜明对照——想用 [] 就必须保证 key 唯一，那就得用 map。

这背后是一个值得记住的工程直觉：方括号语法 [] 的语义里暗含了"这个位置唯一"的前提，一旦容器允许重复，"到底是哪一个"就变成无解的问题。所以凡是"允许重复"的容器，都要用迭代器区间而非裸下标来访问，这在 multimap 这里体现得最彻底。

那么，在 multimap 里想拿到"某个 key 的全部 value"，该怎么办？这正是 equal_range(key) 发光的地方。它直接返回一个 pair<iterator,iterator>——first 就是 lower_bound(key)，second 就是 upper_bound(key)，两者夹起来正好是"所有 key 等于它的节点"区间。配合它，你甚至能安全地循环删除（标准做法是在循环里对 erase 前的迭代器手动 ++，或直接 m.erase(range.first, range.second) 一把梭，因为 erase 区间重载接受两个合法的迭代器）。

#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main()
{
    // 一个 key 对应多个 value：一个人可能有多部联系方式
    multimap<string, string> book = {
        {"张三", "138xxx"},
        {"李四", "139xxx"},
        {"张三", "010-8888"}     // 允许 key 重复，两个张三都保留
    };
 
    // 输出某个 key 的所有 value —— 用 equal_range 圈定区间
    string name = "张三";
    auto range = book.equal_range(name);
    for (auto it = range.first; it != range.second; ++it)
    {
        cout << it->first << " -> " << it->second << endl;
        // 输出：张三 -> 138xxx   张三 -> 010-8888
    }
 
    // count = 重复个数
    cout << book.count("张三") << endl;   // 输出：2
 
    // 也用 lower_bound / upper_bound 手工圈出同一段，验证二者一致
    auto lb = book.lower_bound(name);
    auto ub = book.upper_bound(name);
    cout << "equal_range 与 lower/upper_bound 结果一致：" 
         << (range.first == lb && range.second == ub ? "是" : "否") << endl;
 
    // 删除某个 key 的全部匹配：equal_range 区间接 erase
    book.erase(range.first, range.second);
    cout << "删除后张三条目数：" << book.count("张三") << endl;  // 输出：0
    return 0;
}

lower_bound(key)、upper_bound(key)、equal_range(key) 三者，是访问"可重复 key"的三大法宝：前两个给你一个可以自己掌控的半开区间，第三个直接把你想要的区间装进一个 pair。凡是"要把重复 key 一网打尽"的需求，都逃不出这三兄弟。

一些 OJ / 笔试常见用法

做好了理论铺垫，来看看 map / set 在真实题目里是怎么"降维打击"的。这里挑四个最典型的场景，也只讲思路和核心代码——这些题你自己在力扣上搜题号也能找到。下面所有代码块我都尽量写成"贴进 main 就能独立编译跑通"的样子（力扣代码里的输入结构、Node 结构也一并给出），你拿到本地一跑就能看到结果。

场景一：set 用来判重 / 求交集

既然 set 自带"去重 + 有序"，那么求两个数组的交集，可以先把两个数组都扔进 set，得到两个有序无重复的集合，然后用"双指针"从头比较：小的那个往前动，相等就是交集。这就是力扣 349 两个数组的交集的经典解法：

#include <vector>
#include <set>
#include <iostream>
using namespace std;
 
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 迭代器区间构造：一次完成"去重 + 排序"
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        vector<int> ret;
 
        // 因为两个 set 都升序，用双指针从开头比
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        while (it1 != s1.end() && it2 != s2.end())
        {
            if (*it1 < *it2)        // 谁小谁往前，以逼近相等
                ++it1;
            else if (*it1 > *it2)
                ++it2;
            else                    // 相等就是交集
            {
                ret.push_back(*it1);
                ++it1;
                ++it2;
            }
        }
        return ret;
    }
};
 
int main()
{
    vector<int> a = {1, 2, 2, 1};
    vector<int> b = {2, 2};
    Solution sol;
    vector<int> r = sol.intersection(a, b);
    for (int x : r)
        cout << x << " ";           // 输出：2
    cout << endl;
    return 0;
}

这道题的巧思在于：它利用的是 set 的"有序"而不是"去重"。因为两个集合有序，才能用 O(N) 的双指针扫出交集；若用 vector 而先不排序，就得 O(N·M) 的暴力嵌套循环。set 帮你把"去重 + 排序"一步到位，剩下的就是一次线性扫描。键盘上的双指针逻辑也值得背下来：谁小谁走、相等收下一个，这是"两个有序序列求共有区间"的通用模板。

场景二：set 判重实现"环形链表检测"

环形链表那题，数据结构初阶通常用"快慢指针"加数学证明，烦人得很。但用 set 记录"访问过哪些节点"，就变成一件小事：每走到一个节点，尝试把它插进 set，如果 insert 返回的 second 是 false，说明这个节点之前已经访问过——那它就是环的入口。你看，一道要证明半天的题被 set 一行判重就点破了：

#include <set>
#include <iostream>
using namespace std;
 
struct ListNode {           // LeetCode 环境自带，这里补上以便独立编译
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        set<ListNode*> s;              // 记录访问过的节点指针
        ListNode* cur = head;
        while (cur)
        {
            auto ret = s.insert(cur);  // 尝试插入
            if (ret.second == false)   // 插不进去 = 已经见过 = 环入口
                return cur;
            cur = cur->next;
        }
        return nullptr;                // 走到头 = 无环
    }
};
 
int main()
{
    // 构造一个带环的链表：1 -> 2 -> 3 -> 2（回到第二个节点）
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    n1->next = n2; n2->next = n3; n3->next = n2;  // 成环，入口是 n2
 
    Solution sol;
    ListNode* entry = sol.detectCycle(n1);
    cout << "环入口节点值：" << entry->val << endl;   // 输出：2
    return 0;
}

这里 set<ListNode*> 存的是"指针"，只需比较指针地址即可确定节点是否访问过，完全不需要给 ListNode 写比较器（内置指针类型天然支持 <）。这个"边走边 insert、插不进去就是重复"的套路，是 set 判重最经典的应用，也是"去重 + 存在性查询"的组合拳。它的代价是额外的 O(N) 空间，但换来了证明简单、实现直观——在笔试现场，长度换稳定性常常是划算的。

场景三：map 建映射，秒杀"随机链表复制"

复制带随机指针的链表，初阶做法是"在每两个原节点中间插入拷贝节点"，麻烦。但用 map 把"原节点指针 -> 拷贝节点指针"建立映射关系，复制随机指针就只是查一下表的事：先遍历一遍建好每个原节点的拷贝，并用 nodeMap[cur] = copy 记录对应关系；第二遍复制 random 时，直接 nodeMap[cur->random] 就能拿到该随机指针所指原节点对应的拷贝节点。

#include <map>
#include <iostream>
using namespace std;
 
class Node {                 // LeetCode 环境自带，这里补上以便独立编译
public:
    int val;
    Node *next;
    Node *random;
    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};
 
class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;     // 原节点 -> 拷贝节点的映射
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
 
        // 第一遍：复制每个节点，并记录原节点与拷贝节点的映射
        Node* cur = head;
        while (cur)
        {
            if (copytail == nullptr)
                copyhead = copytail = new Node(cur->val);
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            nodeMap[cur] = copytail;   // 原节点和拷贝节点建立 kv 关系
            cur = cur->next;
        }
 
        // 第二遍：根据映射搞定 random 指针
        cur = head;
        Node* copy = copyhead;
        while (cur)
        {
            // random 为空就置空，否则从表中查出对应的拷贝节点
            copy->random = (cur->random == nullptr) ? nullptr : nodeMap[cur->random];
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};
 
int main()
{
    // 构造一个 1 -> 2，且 2 的 random 指向 1
    Node* a = new Node(1);
    Node* b = new Node(2);
    a->next = b; a->random = b;
    b->random = a;
 
    Solution sol;
    Node* h = sol.copyRandomList(a);
    cout << "拷贝头节点值：" << h->val << endl;                       // 1
    cout << "拷贝头节点 random 指向的值：" << h->random->val << endl; // 2
    return 0;
}

注意这里用到了 nodeMap[cur] = copytail，正因为 key（节点指针）都互不相同且只访问一次，用 [] 是安全且高效的——它不会像"查询未知 key"那样误插默认值，因为每个 key 都是新的、本来就该插入。这个"用 map 做对象之间的重定向映射"的思路，在复制图、克隆树这类"在旧结构上建立等价新结构"的题目中反复出现，本质都是把"难直连的关系"转化为"一次 O(logN) 查表"。

场景四：map 统计 + topK，搞定"前 K 个高频单词"

这是课件 §3.11 的题（力扣 692）。需求是：先统计每个单词出现次数，再按"次数从高到低"排序，且次数相同时按字典序排，最后取前 K 个。map 本身就按 key（单词）升序存，所以遍历 map 时，次数相同的单词天然已经满足"字典序小的在前"——我们要做的，只是让排序算法在比较时优先比次数、次数相同时保持字典序。

这里有两个容易踩的地方。第一，std::sort 底层是不稳定的快速排序，相等的元素可能会互换位置，破坏 map 原本的字典序；所以方案一要用稳定排序 stable_sort（它保证相等元素保持原相对顺序，原顺序正好是字典序）。第二，仿函数里把两个规则用 || 连起来：x.second > y.second || (x.second == y.second && x.first < y.first)——先比次数（高的在前即降序），次数相同时再比单词（小的在前即字典序）。看不懂这个比较式？记住它表达的就是题目的完整排序要求。

#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
 
class Solution {
public:
    // 自定义了"次数大优先，次数相同字典序小优先"的比较器
    struct Compare
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const
        {
            if (x.second != y.second)
                return x.second > y.second;                     // 次数降序
            return x.first < y.first;                           // 次数相同，字典序升序
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1、map 统计次数，顺带按单词升序存好
        map<string, int> countMap;
        for (auto& e : words)
            countMap[e]++;
 
        // 2、把 map 内容倒进 vector，方便排序
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
 
        // 3、稳定排序：次数降序，次数相同保持 map 原本的字典序
        stable_sort(v.begin(), v.end(), Compare());
 
        // 4、取前 k 个
        vector<string> strV;
        for (int i = 0; i < k && i < (int)v.size(); ++i)
            strV.push_back(v[i].first);
        return strV;
    }
};
 
int main()
{
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
    Solution sol;
    vector<string> r = sol.topKFrequent(words, 2);
    for (auto& s : r)
        cout << s << " ";                // 输出：i love（都出现 2 次，字典序 i 在 love 前）
    cout << endl;
    return 0;
}

如果你不想依赖"stable 保序"这个巧技，还有更稳妥的第二条路：在比较器里直接同时把两条规则写全（即上面 Compare 那种写法），这时候用不稳定排序 sort 也不会错，因为"次数相同时谁字典序小"已经由比较器显式决定了，和原顺序无关。两条路都通，但请一定想清楚"为什么"：stable_sort 靠的是"保住原字典序"，全规则比较器靠的是"自己显式比较字典序"。前者依赖 map 的有序性，后者自己把规则写死——面试官更爱听到你讲清这两者的差别。

上面四道题，四道都是"别的法子又长又绕，set/map 一行点破"的典型：交集靠 set 有序、判环靠 set 唯一、复制链靠 map 映射、topK 靠 map 有序 + 仿函数排序。这正体现了关联式容器在实战中的价值——它们把"排序""去重""映射""分组"这些高频能力直接做进了容器里，你要做的只是把数据喂进去、再把结果拿过来。

底层红黑树与选型：什么时候用 map/set，什么时候用 unordered_map/unordered_set

如果你已经认真读完上面所有内容，应该已经有了一个基本判断：map / set 的卖点是"有序"。它们底层是红黑树，所有操作（查、插、删）都是 O(logN)，而且遍历天然有序，还能随时取出最大（rbegin()）最小（begin()）值。这一套对"需要有序遍历、需要范围查询（lower_bound/upper_bound 取区间）、需要频繁取极值"的场景非常合适。回想红黑树本身的约束——"最长路径不超过最短路径两倍"——它把树的高度锁死在 O(logN)，所以任何单次操作都不会出现"某一次特别慢"的情况，这是它稳定性好的根源。

但很多时候我们其实根本不在乎顺序，只在乎"查得快"。比如哈希表（哈希 bucket）通常均摊 O(1) 的查找。于是从 C++11 开始，标准库正式引入了 unordered_map / unordered_set（以及它们的 multiset 变体），底层是哈希表，查找、插入、删除的平均复杂度是 O(1)，但不保证任何顺序，遍历输出是乱序的。

这里把"哈希表为什么 O(1)"也交代清楚，你和面试官聊起来才有底气。哈希表的核心是一个"哈希函数"：它把一个 key 经过计算映射成一个数组下标。查找时把 key 一哈希，直接定位到那个槽位，该走了就当场返回——没有"一棵树要一层层走下去"的开销。但天下没有免费的午餐：两个不同 key 可能算出同一个下标（称为哈希冲突），此时要用"链地址法"把冲突的元素串成一个同下标的小链表，查找就要在这个小链表里线性找。冲突越严重，小链表越长，表现就越差——最坏情况所有 key 撞到同一个槽，退化成一条 O(N) 链表，这正是上表里"最坏 O(N)"的来源。为了抑制冲突，表快满时还会触发扩容（rehash）：把桶的数量翻倍、把所有元素重新摆放一遍，这一下是 O(N) 的整体开销。

怎么选？给你张对照表，碰到问题直接套：

"对 key 的要求"这一行要单独展开说。红黑树需要的只是"任意两个 key 比大小"（默认右 less<Key>，即要求 Key 有 operator< 或你给比较器）。哈希表需要的是两样东西：一个能把 key 换算成整数的哈希函数（默认用 std::hash<Key>），以及一个判断"两个 key 是否相等"的相等比较（默认用 operator==）。内置类型（int、double、指针、std::string 等）这两样都有，直接用没任何问题；但你自定义的 struct 若想塞进 unordered_map，就得自己提供哈希和 operator== 了——这也是自定义类型在哈希容器里比红黑树容器更麻烦的地方。

选择建议也很朴素：

• 如果你的业务需要有序遍历、需要频繁取最大最小、需要范围查询、需要求前 k 个且依赖有序，用 map / set。
• 如果你只需要"快速在不在 / 快速取值"，对顺序毫无要求（统计词频、判重、查字典……绝大多数用例都属于这类），用 unordered_map / unordered_set，它们通常更快。
• 数据量很小（比如几百个）时，两者差异可忽略，用哪个全看心情；数据量大且对实时性敏感时，才值得为"哈希 vs 红黑树"的常数差异较真。

还要补一个面试常问的稳定性点：哈希表在冲突严重或需要扩容 rehash（哈希表装满了要把桶的数量翻倍并重新分配所有元素）时，单次操作可能退化成 O(N)；而红黑树每次操作都雷打不动 O(logN)，稳定性极好，不会出现某一个操作突然卡顿。在实时性 / 安全敏感的场景（比如操作系统内核、高性能交易系统），这个"稳定"往往比"平均快"更重要。这也解释了为什么很多讲究可靠性的项目宁愿用表现"平庸但稳定"的红黑树，也不用"平均极快但偶发尖峰"的哈希表。

最后，关于"各种集合如何记"的一件事：整个家族其实是两组对照，每组四个兄弟——有序组（红黑树）：set / multiset / map / multimap；无序组（哈希）：unordered_set / unordered_multiset / unordered_map / unordered_multimap。你只要抓住三条轴：唯一的（不带 multi）还是可重复的（带 multi）、key-value 的（map）还是只有 key 的（set）、有序的（不带 unordered）还是无序的（带 unordered），就再也不会把它们搞混。三条轴 × 每个容器，一共 2×2×2 种组合全给你铺满了——STL 的命名其实极其规整，规律找到了，八个名字就是一套拼图。

看到这里，关于 map 和 set 的用法主线已经完整走了一遍。我们从"序列式 vs 关联式"的底层认知出发，先吃了 set 的去重和有序，再讲了 map 的键值对设计，中间亲手验证了 insert 的返回值、拆解了 operator[] 自动插默认值的那几个坑，也把 multiset / multimap 允许重复带来的接口行为差异捋了一遍，最后用四道题感受了它们在实战里的威力，并在红黑树 vs 哈希的对比里学会了"按需选型"。

如果你打算在笔试面试里活用它们，请格外记住这几个"考点钉子"：

• set/map 的 key 都是只读的——set 元素、map 的 key 都不能改，否则破坏红黑树结构。
• 查 set/map 用成员 find 是 O(logN)，算法库 std::find 是 O(N)；count/contains（C++20）也能快速判在不在。
• insert 返回 pair<iterator,bool>，first 永远指向该 key 所在节点，second 表示是否新插入；multimap/multiset 里 find 返回中序第一个、erase(值) 全删。
• operator[] 访问不存在的 key 会产生副作用（自动插入默认值）；只读请用 find/count/at。
• 想要 key 唯一才能用 []，所以 multimap 没有 []；重复 key 的区间访问要依靠 lower_bound/upper_bound/equal_range。
• C++11 之后你才能写 initializer_list、{key, value} 插入、at()，并开始使用 unordered 家族；C++14 有透明比较器；C++17 有结构化绑定；C++20 有 contains。版本差异记牢，老编译器前才不会翻车。

下一课，我们大概率会钻进红黑树底层去看看这棵"树"，再对照着看那张 unordered 哈希"表"的内部架构——把关联式容器的最后一层窗户纸捅破。掌握了外层接口，内层的设计意图你已能猜个八九不离十了。