C++標準では、unordered_setのバケットの構造を定義していますか？

Question

unordered_setの要素のハッシュ値が計算されると、それは他の異なる要素と同じハッシュ値と共に「バケット」に配置されます。

私の経験では、このようなバケットの要素は1つのリンクリストに格納されています。意味、それは非常に悪いハッシュ関数を持つバケットの内部を検索するときに遅くなります。

単一リンクリストは、標準または1つの可能な実装の要件ですか？ 1つはとsetをバケットとして実装できますか？

Answer 1

標準は要件と保証を述べていますが、基礎となるデータ構造とアルゴリズムを明示的に強制しません。

N4140§23.2.5[unord.req]/1

順不同連想コンテナは、キーに基づいてデータの高速検索 ための能力を提供します。ほとんどの操作の最悪の複雑さは、 linearですが、平均的なケースははるかに高速です。

これは単なる許可ではなく、最悪の場合の複雑さを事実として示しているため、これはちょっと変わったものです。

N4140§23.2.5[unord.req]/9

順不同連想コンテナの要素は バケットに編成されます。同じハッシュコードを持つキーは同じバケットに表示されます。バケットあたりの平均数が であるように、順序付けされていない連想型コンテナである に要素が追加されると、バケット数が自動的に増加します。 リハッシュすると反復子 イテレータが無効になり、要素間の順序が変更され、バケット要素が表示されますが、ポインタは無効になりません。 要素への参照が変更されます。

は、上記の可能なデータ型としてstd::setを無効にするように見えるんが、それはポインタや参照を無効にすることなく、そのインスタンス間で要素を移動する許可されている場合set様なデータ構造を可能にしなければなりません。 setでは、コンパレータ/ operator<を定義する必要があります（厳密な弱い順序付けのセマンティクスで）が必要ですが、順序付けられていない連想型コンテナはそのような要件をしません。しかし、この場合、リンクリストに定義されていなければ、単にリンク先リストに戻ることができます。

したがって、上記の条件が満たされていれば、リンクリストをセットのような構造に置き換えることができます。つまり、適切なハッシングアルゴリズムを使用していれば、最初に経験してはならない問題のように感じられます。