C++如何使用unordered_set进行快速查找-C++-PHP中文网

unordered_set查找比set快在平均时间复杂度为o(1)，而set为稳定o(log n)；关键前提是哈希函数合理且负载因子不过高，且不依赖有序性。

c++如何使用unordered_set进行快速查找

unordered_set 查找比 set 快在哪？

关键不是“快”，而是“平均 O(1)”，前提是哈希函数合理、负载因子不过高。它不排序，只管存和查；而 set 是红黑树，稳定 O(log n)，但每次查找都要比较键大小。如果你只关心“这个值在不在”，且不依赖顺序，unordered_set 就是更优解。

插入/查找/删除的平均时间复杂度是 O(1)，最坏退化到 O(n)（全哈希碰撞）
不支持 lower_bound 或按序遍历——它没“顺序”概念
默认用 std::hash<t></t>，对 int、string 等内置类型开箱即用；自定义类型必须提供哈希和相等判断

怎么写一个能放进 unordered_set 的自定义结构体？

不能直接塞 struct 进去——编译器不知道怎么算哈希、怎么判相等。得显式告诉它。

必须定义哈希函数对象（重载 operator()），返回 size_t
必须定义相等比较函数对象（operator== 或独立仿函数），返回 bool
两者逻辑必须一致：如果 a == b，那 hash(a) == hash(b) 必须成立

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};
<p>struct PointHash {
size_t operator()(const Point& p) const {
// 避免简单异或（如 x ^ y），易碰撞；用 std::hash 混合
return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) <p>std::unordered_set<point pointhash> points;
</point></p></int></int></p>

查找操作怎么写才不踩坑？

别用 find 后再解引用——先确认是否找到，否则解引用 end() 是未定义行为。

正确写法：auto it = s.find(val); if (it != s.end()) { /<em> found </em>/ }
错误写法：if (s.find(val) != s.end()) use(*s.find(val)); —— 调了两次 find，白费性能
更简洁：用 s.count(val) 判断存在性（返回 0 或 1），但不返回迭代器；需要迭代器时必须用 find

C++ 算法竞赛自动化测试数据生成与校验框架
根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载
count() 对 unordered_set 是 O(1) 平均，但内部仍要哈希+查桶，别以为它比 find 轻量很多
如果只是判断存在性且不需要元素本身，count 可读性更好；如果后续要修改或访问，必须用 find