割り当て時にunordered_mapの変更順

Question

この動作が不思議です。

unordered_map<int, string> m1; 
unordered_map<int, string> m2; 
unordered_map<int, string> m3; 

m1[2] = "john"; 
m1[4] = "sarah"; 
m1[1] = "mark"; 

m2 = m1; 
m3 = m2; 

for(auto it = m1.begin(); it != m1.end(); ++it) { 
    cout << it->second << " "; 
} 
cout << endl; 
for(auto it = m2.begin(); it != m2.end(); ++it) { 
    cout << it->second << " "; 
} 
cout << endl; 
for(auto it = m3.begin(); it != m3.end(); ++it) { 
    cout << it->second << " "; 
} 
cout << endl; 

出力：

mark sarah john 
john sarah mark 
mark sarah john 

Iは上で維持任意の特定の順序がないことを知っている私はunordered_mapを割り当てることは、任意の挿入/削除することなく、無秩序マップの内部順序を変更することを見出しましたunordered_mapは、内部的にはハッシュテーブルなので、要素の挿入はどこでも終了でき、再ハッシュはすべてそれを混合します。

ただし、ここでの割り当ては割り当ての直後に変更されています。私は基本的なストレージをコピーすると思っていたので、その順序は同じであると思った。

私が考えた最初の説明は、おそらくunordered_mapがコピーを利用して、新しいマップをより最適な配置に再ハッシュしているということでした。しかし、私はm2から新しいマップ（m3）に代入を繰り返してみましたが、m2の順序はm3に保存されていません。

なぜ地図を割り当てると注文が変わるのですか？明らかにこれは実装固有であるので

私のコンパイラは（それはすべての後に順不同マップである）のApple LLVMバージョン8.1.0（打ち鳴らす-802.0.42）

Answer 1

これはlibc++の実装の詳細です：

_LIBCPP_INLINE_VISIBILITY 
    unordered_map& operator=(const unordered_map& __u) 
    { 
#ifndef _LIBCPP_CXX03_LANG 
     __table_ = __u.__table_; 
#else 
     if (this != &__u) { 
      __table_.clear(); 
      __table_.hash_function() = __u.__table_.hash_function(); 
      __table_.key_eq() = __u.__table_.key_eq(); 
      __table_.max_load_factor() = __u.__table_.max_load_factor(); 
      __table_.__copy_assign_alloc(__u.__table_); 
      insert(__u.begin(), __u.end()); 
     } 
#endif 
     return *this; 
    } 

^{From libc++'s unordered_map header}

私たちは、あなたがC++ 11以降を使用していると仮定した場合、これは基本的にクリアすることで動作します古いハッシュテーブルを作成し、__uの要素をこのベクトルに挿入します。 operator=の実装だけであるとして、あなたはlibstdc++を使用する場合は発生しません

m2.clear(); 
m2.max_load_factor(m1.max_load_factor()); 
m2.insert(m1.begin(), m1.end()); 

：

m2 = m1; 

それは以下のコードとほぼ同じです：あなたがやるときという意味

= default（libstdC++のunordered_map headerを参照してください）

Answer 2

である私は教養作るつもりです投機。

markとjohnが同じハッシュを持ち、問題のバケットの数と衝突し、実装でチェーンを使用している場合、これを説明することができます。チェーンインプリメンテーションが新しいアイテムを前面に挿入する場合（単一リンクリストの場合でも一定の時間）、コンテナを割り当てるたびに、チェーンアイテムの順序が入れ替えられます。