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

1. 什么是 std::unordered_set？

• std::unordered_set 是 C++ STL（标准模板库）中的一个关联容器。

• 特点：

• 元素唯一（没有重复元素）。

• 元素无序（元素的排列顺序是不可预测的）。

• 采用哈希表（Hash Table）实现。

• 插入、查找、删除的平均时间复杂度是 O(1)（常数时间，非常快！）。

总结一句话就是：

unordered_set 提供了比 set 更快的查找速度，但元素没有顺序。

 2. 底层原理

• 使用了 哈希表（Hash Table）结构。

• 每个元素通过哈希函数（std::hash）映射到一个桶（bucket）中。

• 桶内的元素通常使用链表（或者链表加小规模树）存储，解决哈希冲突（叫做拉链法，Chaining）。

• 插入元素时：

• 先通过哈希函数找到应该放入的桶。

• 如果该桶已有其他元素（冲突），则加在链表后面。

• 查找元素时：

• 也是先通过哈希找到桶，再遍历桶内元素。

3. 头文件和基本定义

#include <unordered_set>

std::unordered_set<int> us;
std::unordered_set<std::string> mySet;

4. 常用操作总结表

 5. 示例代码

插入和遍历元素：

#include <iostream>
#include <unordered_set>

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

    us.insert(3);
    us.insert(1);
    us.insert(7);
    us.insert(1); // 插入失败，1已存在

    for (int x : us) {
        std::cout << x << " ";
    }
    // 输出顺序不确定，比如可能是：7 1 3
}

查找元素：

if (us.find(3) != us.end()) {
    std::cout << "Found 3!" << std::endl;
}

if (us.count(4) == 0) {
    std::cout << "4 not found" << std::endl;
}

查看哈希表信息：

std::cout << "Number of buckets: " << us.bucket_count() << std::endl;
std::cout << "Load factor: " << us.load_factor() << std::endl;

调整桶数量（减少冲突，优化性能）：

us.rehash(100); // 至少100个桶

6. unordered_set 和 set 的区别

如果你只是需要快速存取，unordered_set一般更优！

7. unordered_set 的性能细节

• 平均复杂度：O(1)

• 最坏复杂度：O(n)，当很多元素哈希到同一个桶（哈希冲突严重）时。

• 负载因子 load_factor：

• 等于：元素数量 / 桶数量

• 当负载因子超过一定阈值时（比如1.0），容器会自动扩容（rehash），保证 O(1) 性能。

• 哈希函数：

• 默认对基础类型（int, string等）使用标准哈希函数。

• 自定义类型需要自己提供哈希函数和相等比较器。

8. 注意事项

• 元素是唯一的，和 set 一样，不允许有重复元素。

• 元素无序，所以不能通过顺序访问。

• 元素值不能被修改，因为修改可能破坏哈希值导致定位失败。

• 插入复杂对象（比如结构体）时，要提供哈希函数和相等比较器。

 9. 自定义类型示例（自定义哈希函数）

如果你要存一个自定义结构体，比如 Point(x, y)，需要自己定义哈希和比较器：

#include <unordered_set>

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({2, 3});
}

小结