主要观点:
- GNU libstdc++的基于哈希的关联容器的节点结构布局会根据哈希函数的
noexcept
特性而改变,这在文档中虽有提及但较易被忽略。 std::unordered_set
本质上是由“桶”和“节点”组成,删除元素时若先比较哈希值可能更优,但哈希函数较慢时则是反优化。- 可以在节点中预计算并存储哈希值,这样在
erase(const T&)
、erase(const_iterator)
和重新哈希时都能受益,但对于unordered_set<int>
等简单类型,存储哈希值可能较傻。 - libstdc++的
unordered_set
性能特性依赖于哈希函数的真实名称和noexcept
特性,用户定义的哈希函数在不同noexcept
设置下会有不同的性能表现。 - 有一个基准测试展示了libstdc++启发式算法的一些后果,不同类型在不同哈希函数设置下的节点大小和重新哈希时间不同。
- 总体而言,这一现象在实际编程中大多无关紧要,但比特币核心曾因类似问题而受到影响,若性能受单个哈希表数据结构主导,可能需要优化该结构。
关键信息:
unordered_set
的数据结构及erase
函数的实现细节。- 存储哈希值在节点中的好处及不同情况下的适用性。
- libstdc++中影响
unordered_set
性能的哈希函数特性及相关判断条件。 - 基准测试的结果及不同类型和哈希函数设置下的表现。
重要细节:
unordered_set
中通过桶和节点存储元素,删除元素时遍历桶中的节点并比较元素值或哈希值。- 存储哈希值可节省
erase(const T&)
的时间,在erase(const_iterator)
和重新哈希时也需要哈希值。 - libstdc++中根据哈希函数是否在黑名单、是否为
noexcept
来决定是否存储哈希值。 - 基准测试中不同类型(
int*
、string
、vector<bool>
)在不同哈希函数设置下的节点大小和重新哈希时间。 - 比特币核心因哈希函数未标记
noexcept
而导致unordered_map
内存占用增加,添加noexcept
关键字后降低了内存使用。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。