unordered_set(c++)

unordered_set 是 C++ 标准库中的一个容器，属于 std 命名空间，和 set 类似，但与 set 不同的是，unordered_set 中的元素没有任何排序。unordered_set 的底层实现基于哈希表，因此它能够提供常数时间复杂度的插入、删除和查找操作（在最坏情况下为线性时间复杂度）。不过，由于没有排序，元素的遍历顺序是无序的。

1. insert()

insert() 用于向 unordered_set 中插入一个元素。如果元素已经存在，insert() 不会插入新元素，并且返回一个指示插入结果的对（iterator, bool）。如果插入成功，返回的布尔值为 true；如果元素已经存在，返回 false。

1
2
3
4
std::unordered_set<int> mySet;
mySet.insert(10);
mySet.insert(20);
mySet.insert(10); // 插入失败，因为 10 已经存在

2. erase()

erase() 用于删除 unordered_set 中的元素。它可以接受元素值或迭代器作为参数。

  • 通过元素值删除：删除指定的元素。
  • 通过迭代器删除：删除指定位置的元素。
1
2
3
4
std::unordered_set<int> mySet = {10, 20, 30};
mySet.erase(20); // 删除元素 20
auto it = mySet.find(10);
mySet.erase(it); // 删除元素 10

3. find()

find() 用于查找 unordered_set 中是否包含某个元素。返回一个指向该元素的迭代器，如果找不到则返回 unordered_set::end()。

1
2
3
4
5
6
7
std::unordered_set<int> mySet = {10, 20, 30};
auto it = mySet.find(20); // 返回指向 20 的迭代器
if (it != mySet.end()) {
    // 找到了
} else {
    // 未找到
}

4. count()

count() 返回指定元素在 unordered_set 中的出现次数。由于 unordered_set 中的元素是唯一的，因此返回值只能是 0 或 1。

1
2
3
std::unordered_set<int> mySet = {10, 20, 30};
int count = mySet.count(20); // count 为 1，因为 20 存在
count = mySet.count(40); // count 为 0，因为 40 不存在

5. empty()

empty() 用于检查 unordered_set 是否为空。如果为空，返回 true；否则返回 false。

1
2
3
4
std::unordered_set<int> mySet;
if (mySet.empty()) {
    std::cout << "Set is empty." << std::endl;
}

6. size()

size() 返回 unordered_set 中的元素个数。

1
2
std::unordered_set<int> mySet = {10, 20, 30};
std::cout << "Size: " << mySet.size() << std::endl; // 输出 3

7. clear()

clear() 清空 unordered_set 中的所有元素。

1
2
std::unordered_set<int> mySet = {10, 20, 30};
mySet.clear(); // 清空所有元素

8. bucket_count()

bucket_count() 返回 unordered_set 中哈希表的桶数。

1
2
std::unordered_set<int> mySet = {10, 20, 30};
std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;

9. bucket_size()

bucket_size() 返回指定桶中元素的数量。哈希表将元素分配到不同的桶中，bucket_size() 用于查看某个特定桶中有多少个元素。

1
2
3
std::unordered_set<int> mySet = {10, 20, 30};
size_t bucketIndex = mySet.bucket(0); // 获取桶 0 的索引
std::cout << "Bucket size: " << mySet.bucket_size(bucketIndex) << std::endl;

10. rehash()

rehash() 用于调整 unordered_set 内部哈希表的桶数量。此方法在元素数量增长时很有用，它通过增加桶的数量来减少哈希冲突，提高性能。

1
2
std::unordered_set<int> mySet = {10, 20, 30};
mySet.rehash(10); // 将桶数量调整为 10

11. load_factor()

load_factor() 返回当前哈希表的负载因子，即元素数量与桶数量的比率。负载因子越大，哈希冲突的概率越高。

1
2
std::unordered_set<int> mySet = {10, 20, 30};
std::cout << "Load factor: " << mySet.load_factor() << std::endl;

12. begin() 和 end()

  • begin() 返回指向 unordered_set 中第一个元素的迭代器。
  • end() 返回指向 unordered_set 末尾元素的迭代器，指向的是一个虚拟元素，比最后一个元素的后一个位置。
1
2
3
4
std::unordered_set<int> mySet = {10, 20, 30};
for (auto it = mySet.begin(); it != mySet.end(); ++it) {
    std::cout << *it << " "; // 输出 10 20 30（元素顺序可能不同）
}

13. reserve()

reserve() 用于预留空间，以减少动态扩展哈希表时的性能损失。通过提前为容器分配足够的空间，避免在插入元素时多次重新哈希。

1
2
std::unordered_set<int> mySet;
mySet.reserve(100); // 预留 100 个桶

14. swap()

swap() 用于交换两个 unordered_set 容器的内容。

1
2
3
std::unordered_set<int> set1 = {10, 20, 30};
std::unordered_set<int> set2 = {40, 50, 60};
set1.swap(set2); // set1 变为 {40, 50, 60}，set2 变为 {10, 20, 30}

总结

unordered_set 与 set 相比，提供了更高效的插入、删除和查找操作（在平均情况下为常数时间复杂度），但是由于它不保持元素的顺序，无法按排序顺序遍历。它非常适合用于存储不需要排序的唯一元素集合，特别是在涉及大量查找操作时，性能表现优异。