c++中如何使用std::unordered_set实现快速查找_c++集合用法【实例】

std::unordered_set查找快因底层哈希表，平均O(1)；自定义类型须特化std::hash并重载==；insert返回pair，find返回iterator；需用reserve/rehash预分配桶避免rehash卡顿

。

std::unordered_set 查找为什么快

因为底层是哈希表，平均时间复杂度 O(1)；不像 std::set 那样用红黑树、要 O(log n)。但注意：最坏情况（大量哈希冲突）会退化到 O(n)，所以别随便用自定义类型又不写好 std::hash 特化。

插入和查找的基本写法

直接用 insert() 和 find()，返回值类型不同，容易混淆：

• insert() 返回 std::pair，second 是是否新插入
• find() 返回 iterator，查不到时等于 end()
• 不能用 operator[] —— unordered_set 没下标访问

std::unordered_set s;
s.insert(42);           // OK
s.insert(42);           // 无效果，返回 {已有迭代器, false}
auto it = s.find(42);   // it != s.end() 表示找到了
if (it != s.end()) {
    std::cout << *it << "\n";  // 输出 42
}

自定义类型必须提供 hash 和 equal_to

否则编译报错，典型错误信息：error: call to implicitly-deleted default constructor of 'std::hash'。两个条件缺一不可：

• 特化 std::hash，重载 operator() 返回 size_t
• 提供等价判断（默认用 operator==，也可传入第 3 个模板参数 EqualKey）

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

namespace std {
template<>
struct hash {
    size_t operator()(const Point& p) const {
        return hash{}(p.x) ^ (hash{}(p.y) << 1);
    }
};
}

std::unordered_set pts;
pts.insert({1, 2});

性能陷阱：rehash 和 bucket_count

插入导致负载因子超限会触发 rehash，所有元素重新散列，瞬间卡顿。可提前预留空间避免：

• 用 reserve(n) 预分配至少能存 n 个元素的桶数（不是直接设 bucket_count）
• max_load_factor() 默认是 1.0，设太小会频繁 rehash，太大则冲突增多
• 调用 rehash() 手动扩桶时，传入的是桶数量（bucket_count），不是元素数

如果事先知道大概有 1000 个元素，建议：s.reserve(1024) 或 s.rehash(1024)，而不是 s.reserve(1000) —— 因为内部桶数通常是 2 的幂。