unordered_set

定义

#include <unordered_set>
std::unordered_set<Key, Hash = std::hash<Key>, Pred = std::equal_to<Key>, Alloc = std::allocator<Key>>

• Key 是存储在 unordered_set 中的元素类型。
• Hash 是一个函数或函数对象，用于生成元素的哈希值，默认为 std::hash<Key>。
• Pred 是一个二元谓词，用于比较两个元素是否相等，默认为 std::equal_to<Key>。
• Alloc 是分配器类型，用于管理内存分配，默认为 std::allocator<Key>。

特点

1. 唯一性

• 所有元素都是唯一的，不可重复
• 插入重复元素时不会报错，但插入失败

2. 无序

• 元素的存储顺序与插入顺序、值大小无关
• 底层使用 哈希表（hash table），因此不能通过排序或索引访问元素

3. 高效的查找/插入/删除

• 所有操作平均时间复杂度为 O(1)
• 最坏情况为 O(n)，但实际情况中很少出现（哈希冲突严重时才会）

4. 基于哈希表

• 元素通过哈希函数映射到“桶”中
• 默认使用 std::hash<T> 进行哈希