在 C++ 标准模板库（STL）中，集合类容器是一类非常常用的数据结构，能够存储不重复元素，并提供高效的查找操作。其中最常用的两种是 set 与 unordered_set，分别基于不同的底层结构，适用于不同的场景。

一、set 基本用法

set 是基于红黑树（RB-tree）实现的有序集合。其主要特性包括：

• 自动去重
• 自动排序（升序）
• 查找/插入/删除复杂度为 $O(\log n)$
• 支持双向迭代器，可按顺序遍历

示例代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s1;

    s1.insert(5);
    s1.insert(2);
    s1.insert(8);
    s1.insert(5); // 不会插入重复元素

    // 有序输出
    for (auto &x : s1) {
        cout << x << " ";
    }
    cout << "\n";

    // 查找
    if (s1.find(2) != s1.end()) {
        cout << "找到了元素 2\n";
    }
    return 0;
}

输出示例

2 5 8
找到了元素 2

二、unordered_set 基本用法

unordered_set 基于哈希表（hash table）实现，是一种无序集合。其特性包括：

• 自动去重
• 元素无序排列
• 查找、插入、删除平均复杂度为 $O(1)$ 最坏情况下为 $O(n)$（哈希冲突严重时）

示例代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_set<int> uns1;

    uns1.insert(5);
    uns1.insert(2);
    uns1.insert(8);
    uns1.insert(5);

    // 无序输出
    for (auto &x : uns1) {
        cout << x << " ";
    }
    cout << "\n";

    // 查找
    if (uns1.find(8) != uns1.end()) {
        cout << "找到了元素 8\n";
    }
    return 0;
}

示例输出（顺序不固定）

8 2 5
找到了元素 8

三、常用操作总结

set_union 获取两个集合中的并集，并放入第三个集合中

erase() 在两类 set 中的复杂度不同：

• set.erase(x) 为 $O(\log n)$
• unordered_set.erase(x) 为平均 $O(1)$

四、set 与 unordered_set 对比

具体作用

• 若需输出从小到大的不重复数字 → 用 set
• 若需快速判断元素是否存在，如判重、快速查表 → 用 unordered_set