第二十章节：关联式容器与红黑树

说实话，C++ 标准库里最让我觉得“嗯，这设计真聪明”的部分，就是关联式容器。你想想看，set、map 这些玩意儿，用起来就像是在操作一个自动排序的魔法盒子。我当年刚学的时候，总觉得它们跟 vector 差不多，直到有一次在项目里处理几十万条用户数据，用 vector 查找慢得让人抓狂，换成 set 后速度直接起飞——那一刻我才真正理解了什么叫“数据结构决定性能”。

set 和 multiset：简单但强大

set 说白了就是一个集合，里面的元素是唯一的，而且默认从小到大排好序。你往里面插数据，它自动帮你排好，查找也快。我个人的习惯是，只要需要“快速判断某个值存不存在”，而且不关心顺序，就用 set。

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {3, 1, 4, 1, 5, 9};
    // 重复的 1 会被忽略，最终集合里只有 {1, 3, 4, 5, 9}
    for (int x : s) {
        std::cout << x << " ";  // 输出：1 3 4 5 9
    }
    return 0;
}

注意看，插入重复的 1 并没有生效。这就是 set 的特性——自动去重。如果你需要允许重复元素，那就用 multiset。我在做日志分析时，经常用 multiset 来统计不同错误码出现的次数，非常方便。

map 和 multimap：键值对的利器

map 就是键值对的集合，每个键唯一，自动排序。说白了，它就是一个“字典”。你给一个键，它立刻给你对应的值。我做过一个配置管理系统，就是用 map<std::string, std::string> 来存储配置项，查找起来飞快。

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> ages;
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // 遍历时按键的字母顺序输出
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << std::endl;
    }
    return 0;
}

这里有个坑：如果你用 operator[] 访问一个不存在的键，它会自动插入一个默认值。我曾经因为这个 bug 排查了半天——明明只是想查一下，结果不小心把数据改了。所以，如果你只是想查找，建议用 find() 方法。

multimap 则允许一个键对应多个值。比如一个学生可以选修多门课程，用 multimap<std::string, std::string> 就很合适。不过说实话，我实际项目中用 multimap 的次数不多，更多时候我会用 map<Key, std::vector<Value>> 来替代，因为这样更直观。

红黑树简介：背后的功臣

你可能会好奇，这些容器为什么能这么快？答案就是——红黑树。它是一种自平衡的二叉查找树。说白了，它保证在最坏情况下，插入、删除、查找的时间复杂度都是 O(log n)。

红黑树的规则其实就几条：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 红色节点的子节点必须是黑色（不能有连续的红节点）。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

嗯，这些规则听起来有点绕，但目的只有一个：防止树退化成链表。我刚开始学的时候也觉得抽象，后来自己动手画了几次插入和旋转的过程，才真正理解。下面这张图展示了红黑树的基本结构：

你看，红色节点不会连续出现，而且从根到每个 NIL 叶子节点的黑色节点数量都是 2（根是黑色，加上每个路径上的一个黑色叶子）。这就是红黑树保持平衡的秘诀。

有序 vs 无序容器：怎么选？

C++11 引入了无序容器，比如 unordered_set、unordered_map。它们底层用的是哈希表，而不是红黑树。那么问题来了：什么时候用有序，什么时候用无序？

特性	有序容器 (set/map)	无序容器 (unordered_set/map)
底层结构	红黑树	哈希表
元素顺序	自动排序（默认升序）	无特定顺序
查找时间复杂度	O(log n)	平均 O(1)，最坏 O(n)
插入/删除	O(log n)	平均 O(1)，最坏 O(n)
内存占用	较低（只存元素）	较高（需要额外哈希表空间）
适用场景	需要有序遍历、范围查找	大量查找、不关心顺序

我个人经验是：如果你需要频繁进行范围查询（比如找出所有在 20 到 30 之间的元素），那必须用有序容器。如果只是做键值查找，比如根据用户 ID 查用户信息，那无序容器更快。我曾经在一个高并发服务里，把 map 换成 unordered_map，查询耗时直接降了一半。

好了，这一章的内容就到这里。红黑树虽然看起来复杂，但标准库已经帮我们封装好了，你只需要知道怎么用、什么时候用就行。至于底层细节，理解原理有助于你写出更高效的代码，但不必死磕。