std::map / std::set（红黑树）

一、概念与底层

• std::map：关联式容器，键值对 <K, V>，按键升序存储。
• std::set：只存 key，无 value，也升序。
• multimap / multiset：允许重复键。
• 底层实现：红黑树（Red-Black Tree，自平衡二叉搜索树），libstdc++ 中是一个带哨兵的 _Rb_tree。

特点：

• 查找/插入/删除平均与最坏均为 O(log n)（树高被红黑树约束在 ~2log(n+1)）。
• 有序遍历（中序遍历升序）。
• 没有 operator[] 的 set；map 的 operator[] 在 key 不存在时会默认构造插入（重要副作用）。

二、红黑树 vs AVL 树（为什么用红黑树）

维度	红黑树	AVL 树
平衡标准	最长路径 ≤ 2×最短路径	左右子树高度差 ≤1（更严格）
树高	≤ 2log(n+1)，略高	≈ 1.44log(n+2)，更低
插入/删除旋转	最多 O(1)（至多几次旋转 + 变色）	可能 O(log n) 多次旋转
查找	略慢（树略高）	略快
适用	写多读少/频繁增删（STL 用它）	读多写少，如内核、数据库索引（较少用作通用容器）

结论：STL 用红黑树是因为要兼顾插入删除与查找；AVL 查找更快但要频繁旋转保持严格平衡，插入删除代价高。

三、高频问答

Q1. map 的 operator[] 与 at / insert 区别？

m["key"];          // key 不存在 => 插入一个默认值(如0)，返回引用。有插入副作用！
m.at("key");       // key 不存在 => 抛 out_of_range 异常 ✅ 安全读取
m.insert({"k",1}); // 已存在则不覆盖（返回 pair<iterator,bool>）

• 只想查询不要副作用：用 find 或 at；
• operator[] 无法区分「已存在」与「刚插入」；
• insert_or_assign（C++17）：存在则覆盖，不存在则插入。

Q2. map 迭代器遍历是升序吗？

是。红黑树中序遍历输出升序。所以 map 天然有序，常被当作「有序字典」。

Q3. map 的插入/删除会使迭代器失效吗？

• map::insert / erase 不使其它迭代器失效（红黑树的旋转只动结构内部指针，不搬动已分配节点的数据）。被 erase 的节点迭代器失效；erase 返回下一个迭代器。
• 这是 map 相对 vector 的一大优点。

Q4. map 的 key 为什么不能是自定义任意类型？

key 必须可比较：默认用 operator<（std::less），因此自定义类型需提供 operator<（重载小于号），或用自定义比较器传入模板参数。

结合会问：为什么 map 需要 < 而不需要 ==？—— 红黑树排序/查找只依赖严格弱序 <，用 !(a<b) && !(b<a) 判等。

Q5. map 与 unordered_map 选型？

见 unordered_map.md 对比表。核心：要有序/红黑树稳定 O(logn) → map；只要 O(1) 平均、不需要序 → unordered_map。

四、代码示例：自定义 key 需要 operator<

struct Person {
    std::string name;
    int age;
    bool operator<(const Person& o) const {
        if (name != o.name) return name < o.name;
        return age < o.age;
    }
};
std::map<Person, int> m;   // 可用

五、面试追问点汇总

1. 红黑树的性质（5 条）能背出来吗？
   • ① 节点是红/黑；② 根是黑；③ 叶子（NIL）是黑；④ 红节点的孩子都是黑（无连续两红）；⑤ 任一节点到其叶子的所有路径含相同数量黑节点。
2. 红黑树最坏树高是多少？—— 2·log₂(n+1)。
3. map、set、multimap、multiset 底层都是红黑树，仅 key 是否唯一、value 是否存在不同。
4. 为什么 map<K,V> 用键值对但底层节点实际是 _Rb_tree_node<pair<const K,V>>？—— const K 保证 key 不可改，防止破坏有序性。