C++標準是否爲unordered_set定義了桶的結構？

Question

當計算unordered_set中元素的散列值時，它將與其他 - 不同元素一起放入「存儲區」中，但散列值相同。

我的經驗是，這種桶中的元素存儲在一個單獨的鏈表中。意思是，當在一個具有壞散列函數的桶內進行搜索時，它會得到非常慢的。

單向鏈表是標準的要求還是隻有一個可能的實現？是否可以使用unordered_set和set作爲桶？

Answer 1

該標準規定了要求和保證，但沒有明確強制底層數據結構和算法。

N4140§23.2.5[unord.req]/1

無序關聯容器提供一種基於密鑰數據的快速檢索 的能力。大多數操作的最壞情況是 線性，但平均情況要快得多。

這有點奇怪，因爲它將最壞情況的複雜性說成是事實，而不是僅僅允許它。

N4140§23.2.5[unord.req]/9

一個無序關聯容器的元件被組織成 水桶。具有相同散列碼的密鑰出現在同一個存儲桶中。隨着元素被添加到一個無序的關聯容器中，桶的數量會自動增加，因此每個桶的平均數量爲 元素保持在界限以下。 重新哈希無效 迭代器，元素之間的更改順序以及更改哪些內存元素出現，但不會使指針無效或 對元素的引用。

上述似乎無效std::set作爲一個可能的數據類型，但應允許一個set樣的數據結構，如果它允許移動其實例之間元素，而無需無效的指針或引用。

這留下了一個障礙：set s需要定義比較器/ operator<（嚴格的弱排序語義），而無序的關聯容器沒有這樣的要求。但是，在這種情況下，如果它沒有被定義，你可以簡單地回退到鏈表。因此，據我所知，如果符合上述條件，則可以用集合結構替換鏈表。話雖如此，如果你使用了合適的哈希算法，它確實感覺像是一個你本來不應該經歷的問題。