代码之家 › 专栏 › 技术社区 › xskxzr

为什么std::unordered\u set会重新刷新,即使负载系数限制没有打破?

unordered-set stl hash c++

xskxzr · 技术社区 · 6 年前

仅当新元素数大于 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\u load\u factor()*bucket\u count() (注意,第二个输出为0)。为什么会发生这种情况?

3 回复 | 直到 6 年前

Walter 6 年前

你混淆了一个事实 bucket_count() 随着迭代器的失效而改变。迭代器仅在重新刷新的情况下无效,如果新的元素数小于或等于,则不会是1 max_load_factor()*bucket_count() (顺便说一句,如果 size()>max_load_factor()*bucket_count() 重新灰化可以发生,但不一定发生)。

由于您的示例中不是这种情况,因此不会发生重新灰化,迭代器仍然有效。然而,必须增加桶数以适应新的元素。

我对Mac OSX的clang进行了一点实验(扩展了代码),它使迭代器即使在 rehash(size()) (这确实改变了元素的bucket关联,直接通过迭代bucket并打印其内容进行测试)。

xskxzr 5 年前

自 Issue 2156 . 在更改之前,当新的元素数为 不低于 max_load_factor()*bucket_count() ,并且在更改后变为“大于”。

GCC 8.0.1未实施此变更。已经有一个 bug report ,已在GCC 9中修复。

Yola 6 年前

从…起 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() 。

编辑:回答我检查的问题中的更改对我可用与实现 unordered_set ,它实现为

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

然后你要求一个迭代器,使用例如。 lower_bound ,您可以获得列表元素的迭代器,该元素不会因重新灰化而失效。因此,它同意[未通知的要求]/15。