关联容器

Set

set 是 C++ 标准模板库（STL）中的一种关联容器，定义在 <set> 头文件中。它是一个有序的集合，用于存储唯一元素，即不允许重复值。set 的底层实现通常基于红黑树（一种自平衡二叉搜索树），这使得它能够高效地支持插入、删除和查找操作，同时保持元素的有序性（默认按升序排列）。

set 的 key 是模板 T 对应的类型对象，value 是 set 中是否存在这个类型的对象，即 true 或者 false。

set 具有唯一性，每个对象在 set 中只出现一次，重复出现的对象会被自动忽略。set 具有有序性，对象是可比较的，按照特定的比较规则（默认是 < ）自动排序。同时 set 具有不可修改性，通过迭代器访问对象是只读的，即只能读取 set 中的对象，而不能直接修改该对象（只能通过删除后重新插入的方式进行类似对象的修改操作）

set 以上的性质或者其他的性质都是由 set 底层的实现方式决定的，set 底层是通过红黑树实现的，所以 set 的性质本质上依赖红黑树的性质。

红黑树

感兴趣的朋友可以参考红黑树，红黑树权衡了 AVL 树严格的平衡性导致的插入和删除操作进行多次自旋的维护成本和普通 BST 的不平衡性导致插入和删除操作将树退化为类链表结构增加时间复杂度的问题。

红黑树的五条性质

节点颜色：每个节点是红色或黑色。
根节点黑色：根始终是黑色。
红色节点约束：红色节点的子节点必须是黑色（不允许连续红色）。
黑色路径等价：从根到每个叶子（NIL）的路径上，黑色节点数相同。
叶子节点黑色：所有空节点（NIL）视为黑色。

通过以上五个性质可以确保树的高度不超过 2 * log(n+1)，从而保证操作时间复杂度为 O(log n)。

证明树高 ℎ ≤ 2⋅log(𝑛+1)

n 是树中的节点总数，黑高 bh 由性质 4 决定所有路径上的 bh 是相等的。性质 3 的作用是用来限制任意一条路径上结点的高度保持相对的平衡，因为红色节点的子节点必须是黑色，这意味着路径上不可能有连续的两个红色节点，因此从根到任意的 NIL 的路径上，红色和黑色节点最多交替出现，这可以得到一条路径上的红色节点数 r 最多等于黑色节点数 b，最极端的情况是黑红交替，最长路径为 r = b

结论1：树高 h 是路径上的总节点数（不含 NIL），即 h=r+b，且 r≤b。

性质 4 保证从根节点到每个 NIL 节点的黑色节点数相等，都为 bh，对于任意路径，黑色节点 b = bh，而红色节点数 r 取决于具体的路径。

结论2：最短路径全为黑色节点，h = bh；最长路径黑红交替，r = bh，h = 2⋅bh。

一棵红黑树的最小节点数出现在所有路径都只有黑色节点，即一颗高度为 bh 的完全二叉树

n≥1+2+2^2+⋯+2^(bh−1) =2^bh −1

因此可以得到

log(n+1) ≥ bh (以 2 为底的对数)

而 h = r+b ≤ bh+bh = 2⋅bh，（因为 r ≤ bh）

最短路径 h=bh，而这里考虑最大高度，即

h ≤ 2⋅bh

可以得到 h ≤ 2⋅log(n+1)

由于红黑树的依赖树高 h ≤ 2⋅log(n+1)，所以操作的时间复杂度均为 O(log n)

因此 set 的设计用于解决高效查找，需要快速判断某个元素是否存在（如去重或成员检查），时间复杂度为 O(log n)。满足 BST 的性质自动排序，当需要维护一个有序的数据集合时，无需手动排序。去重需求，在数据处理中，经常需要消除重复项，set 或者说 BST 天然支持这一点。但是基于树的性质，牺牲了随机访问的的能力。

如何使用 Set ?

基本操作

#include <iostream>
#include <set>
using namespace std;

int main() {
    // 创建一个默认升序的 set
    set<int> s;

    // 插入元素
    s.insert(5);  // O(log n)
    s.insert(2);
    s.insert(8);
    s.insert(5);  // 重复元素会被忽略

    // 遍历元素（自动按升序排列）
    for (int val : s) {
        cout << val << " ";  // 输出: 2 5 8
    }
    cout << endl;

    // 查找元素
    if (s.find(5) != s.end()) {  // O(log n)
        cout << "5 exists in set" << endl;
    }

    // 删除元素
    s.erase(2);  // O(log n)

    // 检查大小和是否为空
    cout << "Size: " << s.size() << endl;  // 输出: 2
    cout << "Empty: " << (s.empty() ? "Yes" : "No") << endl;  // 输出: No

    return 0;
}

自定义排序，默认情况下，set 使用 < 进行升序排序，也就是二叉树的中序遍历方式。如果需要自定义排序，可以传入比较器，比如：

#include <iostream>
#include <set>
using namespace std;

int main() {
    // 降序排序的 set
    set<int, greater<int>> s;  // greater<int> 表示降序
    s.insert(5);
    s.insert(2);
    s.insert(8);

    for (int val : s) {
        cout << val << " ";  // 输出: 8 5 2
    }
    cout << endl;

    return 0;
}

而对于自定义结构体或者类，需要定义比较规则：

#include <iostream>
#include <set>
using namespace std;

struct Person {
    string name;
    int age;
    bool operator<(const Person& other) const {  // 必须定义 < 运算符
        return age < other.age;  // 按年龄升序
    }
};

int main() {
    set<Person> s;
    s.insert({"Alice", 25});
    s.insert({"Bob", 30});
    s.insert({"Alice", 25});  // 重复元素被忽略

    for (const Person& p : s) {
        cout << p.name << " " << p.age << endl;  // 输出: Alice 25, Bob 30
    }

    return 0;
}

详细的操作参考 set

总结 C++ 容器

关联容器

Set

红黑树

红黑树的五条性质

如何使用 Set ?