C++ 标准是否定义了 unordered_set 的存储桶结构？

Question

当计算 a 中某个元素的哈希值时，unordered_set它会与其他不同但哈希值相同的元素一起放置在“桶”中。

我的经验是，这样的桶中的元素存储在单链表中。这意味着，当在具有错误哈希函数的存储桶中进行搜索时，它会变得非常慢。

单链表是标准的要求还是只是一种可能的实现？可以unordered_set用sets 作为桶来实现吗？

Answer 1

该标准规定了要求和保证，但没有明确强制底层数据结构和算法。

\n\n

\n

N4140 \xc2\xa723.2.5 [unord.req]/1

\n\n

无序关联容器提供了基于键快速检索数据的能力。大多数操作的最坏情况复杂度是线性的，但平均情况要快得多。

\n

\n\n

这有点奇怪，因为它陈述了最坏情况的复杂性作为事实，而不是仅仅允许它。

\n\n

\n

N4140 \xc2\xa723.2.5 [unord.req]/9

\n\n

无序关联容器的元素被组织成\n 桶。具有相同哈希码的键出现在同一个桶中。当将元素添加到无序关联容器时，存储桶的数量会自动增加，以便每个存储桶的平均元素数量保持在一定范围以下。重新散列会使迭代器无效、更改元素之间的顺序以及更改元素出现在的存储桶中，但不会使指针或对元素的引用无效。

\n

\n\n

上面的内容似乎std::set作为一种可能的数据类型无效，但set如果它允许在其实例之间移动元素而不使指针或引用无效，则应该允许类似的数据结构。

\n\n

这就留下了一个障碍：sets需要operator<定义一个比较器/（具有严格的弱排序语义），而无序关联容器则没有这样的要求。在这种情况下，如果未定义链接列表，您可以简单地退回到链接列表。

\n\n

因此，据我所知，如果满足上述条件，您可以用类似集合的结构替换链表。话虽这么说，如果您使用了正确的哈希算法，这确实是一个您一开始就不应该遇到的问题。

\n