在 C++ STL 中的 unordered_set bucket_count 函数

C++ STL 中的 unordered_set 是一个关联容器，具有快速查找和插入元素的功能。其中的 bucket_count 函数可以返回当前存储桶的数量，存储桶是是 unordered_set 内部的 hash table。

什么是unordered_set

unordered_set 是 C++ STL 中的一个关联容器，其底层实现采用哈希表。与 set 不同的是，它不会自动对元素进行排序，因此查找某个值的效率较高。

以下示例代码演示了如何定义和使用 unordered_set：

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> myset = {1, 2, 3, 4};

    // 添加元素
    myset.insert(5);

    // 检查元素在 set 中是否存在
    if (myset.find(3) != myset.end()) {
        std::cout << "3 is in the set\n";
    }

    // 遍历 unordered_set
    for (auto it = myset.begin(); it != myset.end(); it++) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

bucket_count 函数的作用

在 unordered_set 中，哈希表的每个元素存储在一个称为桶(bucket)的容器中。在对 unordered_set 进行查找，插入等操作时，会先将哈希值映射到桶的索引，再在桶内查找元素。

因此，在 unordered_set 中，桶的数量会直接影响哈希表的效率。如何计算桶的数量非常关键。unordered_set 中的 bucket_count 函数返回存储容器中桶的数量。

以下示例代码演示了首次将 unordered_set 的元素插入时，桶的数量的变化：

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> myset;

    // 插入元素1
    myset.insert(1);
    std::cout << "桶的数量: " << myset.bucket_count() << std::endl;

    // 插入元素2
    myset.insert(2);
    std::cout << "桶的数量: " << myset.bucket_count() << std::endl;

    // 插入元素3
    myset.insert(3);
    std::cout << "桶的数量: " << myset.bucket_count() << std::endl;

    return 0;
}

输出结果如下：

桶的数量: 1
桶的数量: 2
桶的数量: 4

可以看到，桶的数量随着插入元素的不同而逐渐增加。

建议的桶数量

unordered_set 中的桶数量与元素数量无关，而取决于元素的哈希值和桶的负载因子(load factor)。在哈希表中，负载因子是指桶中的元素数量与桶容量(bucket capacity)之比。

当哈希表的负载因子变高时，会导致元素在桶中的冲突率增加，影响查找和插入的效率。因此，负载因子的大小应该根据具体情况加以调整。

在 unordered_set 中，默认的负载因子为 1.0，即当桶中元素数量达到容量时，会重新分配加倍后的新桶数组。这种情况下，桶的数量会影响哈希表的效率，因此建议适当设置桶的数量。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> myset;

    // 设置为 10 个桶
    myset.reserve(10);
    std::cout << "桶的数量: " << myset.bucket_count() << std::endl;

    return 0;
}

在上述例子中，通过 reserve(10) 方法设置 unordered_set 中桶的数量为 10，可以在插入元素之前固定哈希表中桶的数量。这样在插入元素时，即使负载因子为 1.0，桶的数量也不会随着元素数量增加而自动增加。