同じ2つのunordered_mapの順序は同じですか？

Question

つまり、unordered_mapまたはunordered_setの2つを入力すると、同じ内容と同じハッシュ関数を持つオブジェクトは、繰り返し処理されて同じキー/値ペアのシーケンスが得られますか？

もしそうなら、これが保持する条件は何ですか（同じハッシュ関数、同じキー、必ずしも同じ値ではない）。

Answer 1

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

Answer 2

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

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

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

ルックc-faq about the problem of undefined behaviorこの概念は、すべてのC/C++

Answer 3

さて最初のIはMSDN引用します：

制御シーケンスの要素の実際の順序は、ハッシュ関数、比較機能、挿入のため、最大負荷率、および現在の数に依存

バケツの一般的に、制御された順序で要素の順序を予測することはできません。ただし、同等の順序付けを持つ要素のサブセットは、制御された順序で隣接していることが常に保証されます。

上記の引用はunordered_mapとunordered_setのための同じで、名前は順序が指定されていない暗示するように、しかし、彼らは同等のキーが隣接していることを言及します。

Answer 4

ご注文の保証が必要な場合は、でなく、のデータ構造です。実際、主に反復処理を行う場合は、unordered_map/setもデータ構造体ではありません。

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

ここで間違ったツリーを吠えているように聞こえます。 unordered_mapは一般的にO（1）ルックアップなどの利点を利用するべきであり、オブジェクトのリストを格納してそれらを反復するべきではありません。決定的な反復順序を取得しようとしている場合は、の間違いなくを使用すべきではありません。