为什么即使加载因子限制没有被破坏，std :: unordered_set也会重新出现？

Question

根据cppreference，

仅当新元素数大于max_load_factor()*bucket_count()时才会发生重新散列。

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

insert和emplace成员不会影响迭代器的有效性如果(N+n) <= z * B，其中N是插入操作之前容器中元素的数量，n是插入的元素的数量，B是容器的桶数，z是容器的最大负载系数。

但是，请考虑以下示例：

#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()随着迭代器的失效而发生了变化。迭代器只在rehash的情况下失效，如果新的元素数量小于或等于max_load_factor()*bucket_count()，则不会为1（如果size()>max_load_factor()*bucket_count()可以发生，则可以发生，但不必）。

由于在您的示例中不是这种情况，因此不会发生重新散列并且迭代器仍然有效。但是，必须增加桶数以适应新元素。

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

Answer 2

从26.2.7无序关联容器

当元素添加到无序关联容器时，桶的数量会自动增加，因此每个桶的平均元素数量保持在一个边界之下。

b.load_factor()           Returns the average number of elements per bucket.

b.max_load_factor()       Returns a positive number that the container attempts 
                          to keep the load factor less than or equal to. The container
                          automatically increases the number of buckets as necessary
                          to keep the load factor below this number.

我同意，max_load_factor描述的第一部分表明负载系数可以达到该值，但在第二部分和前面的引用中，它清楚地表明负载系数将保持在这个数字以下。所以，你在cppreference中发现了一个错误。

在您的代码中，在没有重新散列的情况下，在第三次插入之后，您的s.load_factor将等于s.max_load_factor()。

编辑：为了回答我检查的问题的变化VS我实施的unordered_set，它被实现为

// hash table -- list with vector of iterators for quick access

然后你要求一个迭代器，使用例如lower_bound，你得到list元素的迭代器，它不会通过rehashing失效。所以，它同意[unord.req] / 15。

Answer 3

自Issue 2156以来，重组的情况发生了变化。在更改之前，当新元素数量不小于max_load_factor()*bucket_count()时会发生重新散列，并且在更改后变为“大于”。

GCC 8.0.1没有实现此更改。已经有一个bug report，它已在GCC 9中修复。