c++如何使用std::unordered_set_c++快速查重与去重【常用】

std::unordered_set插入时自动去重，因其底层哈希表在insert()中先算哈希值再用operator==比对等价性，重复则返回pair.second为false；自定义类型需提供hash特化和operator==，内置类型直接可用。

std::unordered_set 插入时自动去重的原理

它底层是哈希表，insert() 时会先计算元素的哈希值，再检查桶中是否已存在等价元素（通过 operator== 判断）。如果已存在，插入失败，insert() 返回的 pair 中 second 为 false。这天然适合查重：只要关注返回值的 bool 就能知道是否重复。

注意：自定义类型必须提供 std::hash 特化和 operator==，否则编译不过。内置类型（int、std::String 等）开箱即用。

查重：用 insert() 返回值判断是否已存在

比先调用 find() 再判断更高效——避免两次哈希查找。直接靠 insert() 的返回值就能拿到结果。

• std::unordered_set seen;
• 对每个待查元素 x，执行 auto [it, inserted] = seen.insert(x);
• inserted == false 表示 x 是重复项
• 不需要额外调用 count() 或 find()，一次操作完成查重+记录

去重：遍历原容器 + insert() 构建新集合

最常用场景是把一个含重复元素的 std::vector 或数组转成无重复集合。注意：std::unordered_set 不保持插入顺序，若需顺序保留，得配合 std::vector 手动去重（用 seen.insert(x).second 控制是否 push_back）。

立即学习“C++免费学习笔记（深入）”；

示例：

std::vector v = {1, 2, 2, 3, 1}; std::unordered_set unique_set(v.begin(), v.end()); // 构造时自动去重 // 或逐个插入： std::unordered_set s; for (int x : v) s.insert(x); // 重复项被静默忽略

构造函数方式简洁，但内部仍是逐个 insert()；显式循环插入则方便在过程中做额外逻辑（如计数、日志）。

性能与坑：哈希冲突、负载因子和移动语义

平均 O(1) 查找/插入，但最坏退化到 O(n)，尤其当哈希函数质量差或大量冲突时。默认最大负载因子是 1.0，超限会 rehash，引发内存重分配和所有元素重散列——频繁插入时可提前 reserve() 避免多次 rehash。

• 插入大量已知数量元素前，调用 s.reserve(N)（N 是预期唯一元素个数）
• 字符串类对象优先用 std::string_view 插入（c++17 起），避免临时 std::string 构造开销
• 移动语义生效：对右值调用 insert(std::move(x)) 可避免拷贝，尤其对大对象有效
• 不要混用不同编译器标准库的 std::unordered_set 迭代器或指针跨 DLL 边界传递——ABI 不兼容

真正影响性能的往往不是“用了没用”，而是哈希函数是否均匀、是否预留空间、以及是否在热路径里反复构造临时对象。