c++ - 順序付けられていないコンテナへの挿入による決定論

Question

順序付けされていない 2 つのコンテナーに同じ (サイズと値) 要素を挿入すると、2 つの反復子でコンテナーをトラバースすると、常に同じ要素が同じ位置に表示されますか?

はいの場合、(単一の!) ハッシュ関数を作成して、この決定論を破ることはできますか?

Answer 1

それは状況によって異なります: 同じ要素を同じ順序で 2 つの異なる順序付けられていないコンテナーに挿入する場合、順序自体が unspecified であっても、順序は両方のコンテナーで同じでなければなりません。

推論は少し複雑ですhash(k)。 および 再割り当てなどのすべての操作は決定論的です。ただし、標準には実際の引用はありませんが、find()in O(1)after anを実行できる機能は、insert()あらゆる種類のランダム化または非決定論的な挿入を除外するようです。

ただし、挿入の順序を変更すると、内部の再割り当てによって要素の順序が変更されるため、すべての賭けがオフになります。

23.2.5 順不同の連想コンテナ [unord.req]

9 順序付けられていない連想コンテナの要素は、バケットに編成されます。同じハッシュ コードを持つキーは同じバケットに表示されます。要素が順序付けられていない連想コンテナーに追加されると、バケットの数が自動的に増加するため、バケットあたりの要素の平均数は境界未満に保たれます。再ハッシュはイテレータを無効にし、要素間の順序を変更し、要素が表示されるバケットを変更しますが、要素へのポインタや参照は無効にしません。unordered_multiset と unordered_multimap の場合、再ハッシュによって同等の要素の相対的な順序が維持されます。