详细系统讲解 C++ 中的 std::set。我会按照概念→实现原理→常用操作→性能特点→例子→注意事项这种顺序，一步步带你掌握它！

1. 什么是 std::set？

• std::set 是 C++ STL（标准模板库）里的一个关联容器（Associative Container）。

• 特点：

• 元素自动排序（默认按从小到大升序排列）。

• 元素唯一（集合中不能有重复元素）。

• 本质上，它是用一棵红黑树（Red-Black Tree）实现的。

• 插入、查找、删除操作的时间复杂度是 O(log n)。

 2. 底层原理

• 红黑树是一种自平衡的二叉搜索树（Binary Search Tree）。

• 插入或删除节点时，树会自动进行旋转或变色，保持近似平衡。

• 红黑树保证最长路径不会超过最短路径的2倍，保证了 O(log n) 的操作性能。

所以 std::set 的核心特性有：

• 元素自动按排序规则排列（默认 operator<）。

• 操作（插入/查找/删除）都在对数时间完成。

3. 头文件和基本定义

#include <set>

std::set<int> s;
std::set<std::string> mySet;

4. 常用操作总结表

5. 示例代码

基本插入和遍历：

#include <iostream>
#include <set>

int main() {
    std::set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(5); // 5已经存在，插入无效

    // 遍历：默认升序
    for (int x : s) {
        std::cout << x << " ";
    }
    // 输出：2 5 8
}

查找和删除元素：

if (s.find(5) != s.end()) {
    std::cout << "5 found" << std::endl;
}

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

使用 lower_bound 和 upper_bound：

auto it = s.lower_bound(5); // 找到第一个 >= 5 的元素
if (it != s.end()) {
    std::cout << "Lower bound of 5: " << *it << std::endl;
}

auto it2 = s.upper_bound(5); // 找到第一个 > 5 的元素
if (it2 != s.end()) {
    std::cout << "Upper bound of 5: " << *it2 << std::endl;
}

6. set 和 multiset 的区别

示例：

std::multiset<int> ms;
ms.insert(5);
ms.insert(5); // 成功插入第二个5

7. std::set 和 std::unordered_set 的区别

总结一句话：

如果需要有序，用 set；如果只关心快速查找/插入，用 unordered_set。

8. 注意事项

• 默认按 < 排序，可以自定义比较函数，比如按降序排列。

• 元素值不可修改！（因为改变值会破坏红黑树结构）。

• 插入重复元素无效，且不会抛异常。

9. 自定义排序示例（降序）

std::set<int, std::greater<int>> s;
s.insert(5);
s.insert(2);
s.insert(8);

// 输出：8 5 2
for (auto x : s) {
    std::cout << x << " ";
}

也可以用自定义 struct 作为比较器：

struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 降序
    }
};

std::set<int, Compare> s;

小结