【C++】C++中的 set

C++中的 set

在 C++ 里，你可能经常要判断一个元素是否存在，或者需要一个“不重复”的集合。
这时候，std::set 就能起到这个作用。

很多人一开始会把它当成一个“去重的容器”，但 set 的设计比这复杂得多。今天我们就从原理、用法、性能和场景四个角度把它讲清楚。

1. set 是啥？

std::set 是 C++ STL 中的关联容器，存储一组 唯一的元素，并且自动排序。
它有几个核心特点：

• 元素唯一：不会存储重复值。
• 自动有序：内部会按照 < 运算符或自定义比较器排序。
• 复杂度 O(log n) ：查找、插入、删除的复杂度都是对数级别。

你可以把它看作是一个性能较为稳定的“有序、不重复的数组”。

2. 底层实现：红黑树

和 map 类似，set 的底层通常是 红黑树（一种平衡二叉搜索树）。

• 每个节点存一个元素（只存 key，没有 value）。
• 查找、插入、删除都是 O(log n) 。
• 中序遍历时，元素天然有序。

这就解释了：

• 为什么 set 插入后自动有序（因为树的性质）。
• 为什么它能保证元素唯一（插入时会先查找，如果已存在就拒绝）。

如果想要“无序集合”，C++ 还提供了 unordered_set（哈希表实现）。

3. 基本用法

举个例子：

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

int main() {
    set<int> s;

    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(3); // 重复元素不会插入

    for (int x : s) {
        cout << x << " "; // 1 2 3
    }

    if (s.find(2) != s.end()) {
        cout << "n2 存在于集合中n";
    }

    s.erase(1); // 删除元素
}

常用操作：

• insert(x)：插入元素（重复无效）。
• find(x)：查找元素，返回迭代器。
• erase(x)：删除元素。
• lower_bound(x) / upper_bound(x)：找到大于等于 / 大于 x 的最小元素。

4. 常见应用场景

1. 去重集合
   比如统计一篇文章里出现过的所有单词，set 就能保证唯一性和排序。
2. 有序查找
   比如需要快速找到“≥X 的最小值”，可以用 lower_bound。
3. 动态维护有序序列
   插入 / 删除元素的同时，还能保持整体有序，适合需要频繁更新的数据流。

5. 性能与替代方案

• 优点：

  • 自动有序，查找/插入/删除性能稳定。
  • 代码简洁，不需要手写平衡树。

• 缺点：

  • 内存开销大，每个节点需要额外存指针。
  • 常数性能较慢，远不如数组的 cache 友好。

• 替代选择：

  • 只需要快速查找、不关心顺序 → unordered_set。
  • 数据量不大、主要是读 → vector + sort + unique 可能更快。

6. 小结

• set 的特点： 唯一、有序集合，底层用红黑树实现。

• 优点：有序、功能全、查找插入删除稳定。

• 缺点：内存开销大，性能比哈希或数组差。

如果你理解了 map，set 就相当于只存“键”的版本。