为什么即使负载因子限制未打破，std :: unordered_set也仍会重新映射? [英] Why is std::unordered_set rehashed even if the load factor limit is not broken?

问题描述

根据 cppreference ，

仅当新元素数大于max_load_factor()*bucket_count()时，才会进行哈希处理.

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

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

如果(N+n) <= z * B，insert和emplace成员将不影响迭代器的有效性，其中N是插入操作之前容器中的元素数，n是元素数插入B是容器的存储区计数，z是容器的最大装载系数.

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.

但是，请考虑以下示例:

However, consider the following example:

#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中，它输出

With GCC 8.0.1, it outputs

3 0 7

这意味着在嵌入2之后，尽管新元素(3)的数量不大于max_load_factor()*bucket_count()(请注意第二个输出为0)，但仍会发生重新哈希处理.为什么会这样?

This means after emplacing 2, a rehashing occurs though the new number of elements (3) is not greater than max_load_factor()*bucket_count() (note the second output is 0). Why does this happen?

推荐答案

由于问题2156 .更改之前，当新元素的数量不少于 max_load_factor()*bucket_count()时，将进行重新哈希处理，并且在更改之后它变得大于".

The rehash condition is changed since Issue 2156. Before the change, a rehash occurs when the new number of elements is no less than max_load_factor()*bucket_count(), and it becomes "greater than" after the change.

GCC 8.0.1并未实现此更改.已经有一个错误报告，该问题已在GCC中修复. 9.

GCC 8.0.1 does not implement this change. There is already a bug report, and it has been fixed in GCC 9.

这篇关于为什么即使负载因子限制未打破，std :: unordered_set也仍会重新映射?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！