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<iterator bool></iterator>，second是是否新插入 -
find()返回iterator，查不到时等于end() - 不能用
operator[]——unordered_set没下标访问
std::unordered_set<int> 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<mystruct>'</mystruct>。两个条件缺一不可：
- 特化
std::hash<t></t>，重载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<Point> {
size_t operator()(const Point& p) const {
return hash<int>{}(p.x) ^ (hash<int>{}(p.y) << 1);
}
};
}
std::unordered_set<Point> pts;
pts.insert({1, 2});
性能陷阱：rehash 和 bucket_count
插入导致负载因子超限会触发 rehash，所有元素重新散列，瞬间卡顿。可提前预留空间避免：
立即学习“C++免费学习笔记（深入）”；
- 用
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 的幂。
