实现原理
unordered_set 在 C++ 标准库中是基于哈希表（Hash Table）的数据结构实现的。哈希表是一种通过散列函数将键（在这里是 unordered_set 中的元素）映射到一个固定大小数组的不同桶（buckets）中的数据结构。每个桶可以包含多个元素，当两个或更多的元素散列到同一个桶时，通常使用链表或其他冲突解决策略来存储这些元素。在查找、插入和删除操作时，首先计算元素的哈希值，然后直接定位到对应的桶进行操作。
常用操作
- 插入：通过
insert函数添加元素，如果元素已存在，则不执行插入操作。
std::unordered_set<int> mySet;
mySet.insert(10);
mySet.insert({20, 30});- 查找：使用
find函数确定元素是否存在，返回指向元素的迭代器或end()表示未找到。
if (mySet.find(20) != mySet.end()) {
// 元素20存在于集合中
}- 删除：
erase函数用于移除指定元素或者范围内的元素。
mySet.erase(10);
auto it = mySet.find(20);
if (it != mySet.end()) {
mySet.erase(it);
}- 判断空集：使用
empty()函数检查容器是否为空。
if (mySet.empty()) {
// 集合为空
}- 大小获取：调用
size()获取容器中元素的数量。 - 清除所有元素：
clear()函数用来清空整个容器。
特性及应用场景
特性：
- 无序：元素在容器中的顺序与插入顺序无关，且每次遍历可能得到不同的顺序。
- 唯一性：保证集合内没有重复元素，对于尝试插入的重复值，不会实际增加新元素。
- 高效性：平均情况下，插入、删除和查找操作的时间复杂度为 O(1)，取决于哈希函数的质量以及负载因子。
应用场景：
- 当需要快速查询某个元素是否存在时，例如字词过滤、去重处理等。
- 实现“集合”概念的应用，如数学上的集合运算（并集、交集、差集）。
- 快速查找大量数据中唯一的成员资格验证。
相关容器及其区别
set：同样是标准库中的关联容器，但它是有序的，内部采用红黑树实现。因此，set中的元素始终按照某种排序规则排列，而unordered_set不保证任何排序。由于有序性的维护，set的插入、删除和查找操作在最坏情况下的时间复杂度都是 O(log n)，但在有序遍历方面更高效。unordered_multiset和multiset：这两种容器允许元素重复出现，unordered_multiset对应于无序版本，而multiset是有序版本。
总结来说，unordered_set 是为了提供快速的无序唯一元素集合操作而设计的容器，在不需要维持元素顺序且重视效率的情况下是一个很好的选择。
