unordered_set

std::unordered_set 是 C++11 引入的无序关联容器，基于哈希表实现，用于存储不重复的元素。它将查找、插入、删除的时间复杂度降到平均 O(1)，但不保证元素有序。

和 std::set 的核心区别：无序但更快。

头文件与基本特征

#include <unordered_set>

特征	说明
元素是否重复	不允许重复
顺序	无序（迭代顺序由哈希桶决定）
底层结构	哈希表
查找/插入/删除	平均 O(1)，最坏 O(n)

基本用法

#include <iostream>
#include <unordered_set>

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

    s.insert(30);
    s.insert(10);
    s.insert(20);
    s.insert(10);  // 重复，插入失败

    for (std::unordered_set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << ' ';
    }
    // 输出顺序不保证

    return 0;
}

常用接口

接口	作用
insert(x)	插入元素，返回 pair<iterator, bool>
erase(x)	删除元素
find(x)	查找，返回迭代器或 end()
count(x)	判断是否存在（0 或 1）
size()	元素数量
bucket_count() / load_factor()	桶数量与负载因子
rehash(n) / reserve(n)	调整桶容量

使用注意

1. 不保证遍历顺序，不要依赖。
2. 已知数据量时提前 reserve(n)，减少 rehash 开销。
3. 自定义类型作键需提供哈希函数和相等比较。
4. 最坏情况可能退化到 O(n)，对顺序有要求时用 set。

小结

std::unordered_set 适合"元素唯一 + 快速查找"的场景。和 set 的选型权衡和 unordered_map vs map 一致：需要有序用 set，追求速度用 unordered_set。