c++ - 2つの同じunordered_mapsの順序は同じですか？

Question

言い換えると、2つunordered_map、またはunordered_set、まったく同じコンテンツと同じハッシュ関数でオブジェクトを埋めた場合、それらを反復処理すると、キーと値のペアの同じシーケンスが得られますか？

もしそうなら、これが成り立つための条件は何ですか（例えば、同じハッシュ関数、同じキー、必ずしも同じ値ではありません）。

Answer 1

いいえ。たとえば、同じハッシュを持つオブジェクトを特定の順序で配置する必要はありません。実際、一般に、順序付けされていないマップがこれを行うことは不可能です。これは、マップがアクセスできる情報はハッシュ値のみであるためです。

Answer 2

この場合の動作は未定義です。したがって、状況によってはシーケンスが同じになる場合もあれば、異なる場合もあります。あなたは何も確信が持てません。あなたが言及したタイプは、偶然ではなく、順序付けられていない名前が付けられています。それらを注文したものとして使用することは、非常に悪く、非常に危険なスタイルです。

コンパイラが使用したい特別な方法で動作することがわかります。しかし、あなたは確信が持てません。確信が持てないはずです！どのような条件がコンパイラのそのような振る舞いを引き起こしているのか、あなたは知りません。コンパイラのバージョンを変更しても、必要な動作が変更されないことを確信することはできません。

他の言語で単に禁止されていること、C /C++では指定されていません。しかし、あなたもそれを禁じられていると見なすべきです。

未定義動作の問題についてc-faqを見てくださいこの概念はすべてのC/C++に共通です

Answer 3

まず最初にMSDNを引用します：

制御されたシーケンス内の要素の実際の順序は、ハッシュ関数、比較関数、挿入の順序、最大負荷率、および現在のバケット数によって異なります。一般に、制御されたシーケンス内の要素の順序を予測することはできません。ただし、同等の順序を持​​つ要素のサブセットは、制御されたシーケンスで隣接していることを常に保証できます。

上記の引用はとと同じでunordered_mapありunordered_set、名前が示すようにシーケンスが指定されていませんが、同等のキーが隣接していることを示しています。

Answer 4

保証された順序が必要な場合、これはデータ構造ではありません。実際、主に反復を行う場合unordered_map/setは、データ構造でもありません。

反復の場合、あるstd::mapノードから次のノードへの移動はアルゴリズム的にそれほど複雑ではないため、aがより優れたデータ構造であることがわかります。また、のオブジェクトの反復順序はstd::map 仕様によって保証されています（実際には、構造自体の定義プロパティです）。（これはすべて、明らかに同じ比較演算子を使用していることを前提としています）。にハッシュは含まれませんstd::map。

言うまでもなく、ここで間違った木を吠えているようです。unordered_map通常、O（1）ルックアップなどの利点のために使用する必要があり、オブジェクトのリストを格納してからそれらを反復処理するためには使用しないでください。決定論的な反復順序を取得しようとしている場合は、絶対に使用しないでください。