c++ - 为什么 std::unordered_set 重新散列，即使负载因子限制没有被打破？

Question

根据 cppreference ,

Rehashing occurs only if the new number of elements is greater than max_load_factor()*bucket_count().

此外，[unord.req]/15有类似的规则:

The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container's bucket count, and z is the container's maximum load factor.

但是，请考虑以下示例:

#include <unordered_set>
#include <iostream>

int main()
{
    std::unordered_set<int> s;
    s.emplace(1);
    s.emplace(42);
    std::cout << s.bucket_count() << ' ';
    std::cout << (3 > s.max_load_factor() * s.bucket_count()) << ' ';
    s.emplace(2);
    std::cout << s.bucket_count() << ' ';
}

使用 GCC 8.0.1，它输出

3 0 7

这意味着在放置 2 之后，虽然新的元素数量 (3) 不大于 max_load_factor()*bucket_count()，但会发生重新散列。 (注意第二个输出是 0)。为什么会这样？

Answer 1

您混淆了 bucket_count() 已随迭代器失效而更改的事实。迭代器仅在重新散列的情况下无效，如果新的元素数量小于或等于 max_load_factor()*bucket_count()(顺便说一句，如果 size()>max_load_factor ()*bucket_count() 重新散列可以发生，但不是必须发生)。

因为在您的示例中不是这种情况，所以没有发生重新散列并且迭代器仍然有效。但是，必须增加桶数以容纳新元素。

我用 Mac OSX 的 clang 做了一些实验(扩展你的代码)，即使在 rehash(size()) 之后迭代器仍然有效(它确实改变了元素的桶关联，直接测试遍历存储桶并打印其内容)。