C++ 标准是否为 unordered_set 定义了桶的结构？
Does the C++ standard define the structure of a bucket for unordered_set?
当计算 unordered_set 中某个元素的散列值时，它与其他不同但散列值相同的元素一起放在 "bucket" 中。
我的经验是，这样的桶中的元素是存储在单链表中的。这意味着，在哈希函数错误的存储桶中搜索时，它变得 非常 慢。
单向链表是标准的要求还是只是一种可能的实现？可以用 set 作为桶来实现 unordered_set 吗？
标准规定了要求和保证，但没有明确强制底层数据结构和算法。
N4140 §23.2.5 [unord.req]/1
Unordered associative containers provide an ability for fast retrieval
of data based on keys. The worstcase complexity for most operations is
linear, but the average case is much faster.
这有点奇怪，因为它将最坏情况的复杂性陈述为事实，而不是仅仅允许它。
N4140 §23.2.5 [unord.req]/9
The elements of an unordered associative container are organized into
buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to
an unordered associative container, so that the average number of
elements per bucket is kept below a bound. Rehashing invalidates
iterators, changes ordering between elements, and changes which
buckets elements appear in, but does not invalidate pointers or
references to elements.
上面的内容似乎使 std::set 作为一种可能的数据类型无效，但如果它允许在其实例之间移动元素而不使指针或引用无效，则应该允许类似 set 的数据结构。
这留下了一个障碍：sets 需要定义一个比较器/operator<（具有严格的弱排序语义），而无序关联容器则没有这样的要求。不过，在这种情况下，如果未定义链表，您可以简单地返回到链表。
因此，据我所知，如果满足上述条件，您可以将链表替换为类似集合的结构。话虽这么说，如果您使用了适当的哈希算法，它确实感觉像是您一开始就不应该遇到的问题。
当计算 unordered_set 中某个元素的散列值时，它与其他不同但散列值相同的元素一起放在 "bucket" 中。
我的经验是，这样的桶中的元素是存储在单链表中的。这意味着，在哈希函数错误的存储桶中搜索时，它变得 非常 慢。
单向链表是标准的要求还是只是一种可能的实现？可以用 set 作为桶来实现 unordered_set 吗？
标准规定了要求和保证，但没有明确强制底层数据结构和算法。
N4140 §23.2.5 [unord.req]/1
Unordered associative containers provide an ability for fast retrieval of data based on keys. The worstcase complexity for most operations is linear, but the average case is much faster.
这有点奇怪，因为它将最坏情况的复杂性陈述为事实，而不是仅仅允许它。
N4140 §23.2.5 [unord.req]/9
The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements.
上面的内容似乎使 std::set 作为一种可能的数据类型无效，但如果它允许在其实例之间移动元素而不使指针或引用无效，则应该允许类似 set 的数据结构。
这留下了一个障碍：sets 需要定义一个比较器/operator<（具有严格的弱排序语义），而无序关联容器则没有这样的要求。不过，在这种情况下，如果未定义链表，您可以简单地返回到链表。
因此，据我所知，如果满足上述条件，您可以将链表替换为类似集合的结构。话虽这么说，如果您使用了适当的哈希算法，它确实感觉像是您一开始就不应该遇到的问题。