C++ unordered_set怎么用-C++-PHP中文网

unordered_set插入和查找比set快，因其底层为哈希表，平均时间复杂度o(1)，而set基于红黑树，稳定o(log n)；但最坏情况（高冲突）下unordered_set退化为o(n)。

c++ unordered_set怎么用

unordered_set 插入和查找为什么比 set 快？

因为 unordered_set 底层是哈希表，平均时间复杂度 O(1)，而 set 是红黑树，O(log n)。但注意：最坏情况（大量哈希冲突）下，unordered_set 查找会退化到 O(n)，实际使用中只要不自定义糟糕的哈希函数，基本不会遇到。

插入和查找都依赖哈希值，所以要求元素类型必须支持 std::hash 特化，且支持 == 比较。内置类型（int、string 等）默认支持；自定义类需手动提供哈希和相等逻辑。

不支持重复元素，重复 insert() 无效果，返回 std::pair<iterator bool></iterator>，second 为 false 表示已存在
find() 返回 iterator，找不到时等于 end()，别直接解引用
不要用 operator[] —— unordered_set 没这玩意，那是 unordered_map 的

怎么让自定义结构体能放进 unordered_set？

必须同时提供哈希函数对象和相等比较函数对象，并在模板参数里传进去。常见写法是专门写一个 struct 实现 operator()，或者用 lambda（C++20 起支持，但受限于模板推导，一般还是用 struct 更稳）。

例如结构体 Point：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

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

struct PointHash {
    size_t operator()(const Point& p) const {
        // 避免简单异或（x=1,y=2 和 x=2,y=1 冲突），用 std::hash 混合
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) > points;
</int></int>

第三个模板参数默认就是 std::equal_to<t></t>，如果重载了 operator== 就不用显式写
哈希函数里别用 return x + y 或 x ^ y，极易冲突；推荐用 std::hash<t>{}</t> 对各字段分别哈希再组合
C++17 起可对 Point 偏特化 std::hash，之后就能直接写 unordered_set<point></point>，但要注意特化必须在全局命名空间，且不能在头文件里重复定义（否则 ODR 报错）

clear()、erase() 和迭代器失效规则

unordered_set 的迭代器只在被 erase() 的那个元素上失效，其他迭代器（包括 end()）仍有效；而 rehash（如扩容）会导致**所有迭代器失效**。但 clear() 不触发 rehash，只清空，所以它不导致迭代器失效 —— 这点和 vector 不同，容易误判。