8. std::set / std::multiset 详解：红黑树实现原理、有序性、查找效率、自定义比较器

好，咱们今天来聊聊 std::set 和 std::multiset。这两个容器，说白了就是「有序集合」和「有序多重集合」。你想想看，如果你需要维护一堆不重复的、并且随时能按顺序遍历的数据，那 std::set 就是你的首选。而 std::multiset 呢，它允许元素重复，其他特性基本一样。

我个人习惯把这两个容器叫做「红黑树兄弟」。为什么？因为它们的底层实现，就是一棵红黑树。嗯，这里要注意，C++ 标准并没有强制要求必须用红黑树，但几乎所有主流编译器（GCC、Clang、MSVC）都是这么干的。所以咱们就按红黑树来理解，准没错。

8.1 红黑树实现原理：为什么它这么快？

红黑树，本质上是一棵自平衡的二叉搜索树。它通过给每个节点涂上红色或黑色，并遵守一套规则，来保证树的高度始终保持在 O(log n) 左右。

规则其实就五条，我简单列一下：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色的。
• 所有叶子节点（NIL 节点）都是黑色的。
• 如果一个节点是红色的，那么它的两个子节点都是黑色的（不能有连续的红节点）。
• 从任意节点到其每个叶子节点的所有路径，都包含相同数量的黑色节点。

这五条规则，保证了红黑树最坏情况下的查找、插入、删除操作，时间复杂度都是 O(log n)。我在项目中遇到过几次因为数据量暴增导致性能瓶颈的情况，最后发现是用了 std::vector 做频繁插入和查找。换成 std::set 之后，性能直接起飞。说白了，红黑树的平衡性就是它的命根子。

下面这张图，是我画的一个红黑树结构示意图，你可以直观感受一下：

8.2 有序性：遍历就是从小到大

红黑树的中序遍历，天然就是有序的。所以 std::set 和 std::multiset 的迭代器，按 ++ 操作走一遍，得到的就是升序序列。这一点在项目中非常实用。我记得有一次需要实时展示排行榜数据，直接用 std::set 存分数，然后从 rbegin() 开始遍历，降序输出，代码简洁到不行。

8.3 查找效率：O(log n) 的底气

查找是 std::set 的看家本领。它提供了 find()、count()、lower_bound()、upper_bound()、equal_range() 这些成员函数。它们的底层都是红黑树的查找操作，时间复杂度 O(log n)。

我对比过 std::set 和 std::unordered_set 的查找性能。在数据量小于 1000 时，两者差距不大。但数据量到了 10 万以上，std::unordered_set 的哈希冲突开始显现，而 std::set 依然稳如老狗。当然，如果你对顺序没要求，std::unordered_set 的平均性能还是更好的。但如果你需要「有序查找」或者「范围查询」，那 std::set 就是唯一的选择。

下面这个表格，是我整理的常用查找操作对比：

8.4 自定义比较器：让 set 按你的规则排序

默认情况下，std::set 使用 std::less<T> 作为比较器，也就是升序。但实际项目中，我们经常需要自定义排序规则。比如按字符串长度排序，或者按结构体的某个字段排序。

自定义比较器有两种方式：

1. 函数对象（仿函数）：定义一个类，重载 operator()。
2. Lambda 表达式：C++11 之后，可以用 lambda 作为比较器，但要注意类型推导。

我个人更推荐用函数对象，因为可读性更好，而且可以复用。下面是一个例子：

#include <iostream>
#include <set>
#include <string>

// 自定义比较器：按字符串长度升序
struct CompareByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) {
            return a.size() < b.size();
        }
        return a < b; // 长度相同时，按字典序
    }
};

int main() {
    std::set<std::string, CompareByLength> words;
    
    words.insert("apple");
    words.insert("banana");
    words.insert("kiwi");
    words.insert("pear");
    words.insert("grape");
    
    for (const auto& w : words) {
        std::cout << w << " (" << w.size() << ")\n";
    }
    // 输出：
    // pear (4)
    // apple (5)
    // grape (5)
    // kiwi (4)  -- 等等，这里有问题！
    return 0;
}

另外，如果你用 lambda，写法是这样的：

auto cmp = [](const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
};
std::set<std::string, decltype(cmp)> words(cmp);

嗯，这里要注意，lambda 作为比较器时，必须把 lambda 实例传给 set 的构造函数，否则编译不过。

8.5 std::multiset：允许重复的 set

std::multiset 和 std::set 几乎一模一样，唯一的区别就是它允许插入重复元素。它的 count() 函数返回的是实际元素个数，而 equal_range() 返回的区间包含了所有重复元素。

我在项目中用过 std::multiset 来处理「多优先级任务队列」。每个任务有一个优先级，相同优先级的任务可以同时存在。用 std::multiset 存任务，然后按优先级顺序取出，非常方便。

不过要提醒你一句：std::multiset 的 erase(key) 会删除所有等于 key 的元素。如果你只想删一个，得用 erase(iterator)。我曾经踩过这个坑，一次删掉了所有相同优先级的任务，导致系统直接空转了一分钟。

好了，关于 std::set 和 std::multiset 的核心内容，就聊到这里。记住，红黑树不是魔法，它只是一套聪明的规则。理解了规则，你就能驾驭它。