unordered_map更改的順序

我很好奇這種行爲。我發現，分配一個unordered_map改變無序地圖的內部順序，而沒有任何插入/缺失：unordered_map更改的順序

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

我知道有不能維持上的任何特定的順序unordered_map由於內部是一個哈希表，因此元素插入可以在任何地方結束，重新哈希將混合它。

但是，這裏的順序在分配後才發生變化。我預計訂單是一樣的，因爲我認爲它只是複製底層存儲。

我認爲的第一個解釋是，也許unordered_map正在利用副本將新地圖重新散列爲更優化的安排。但是，我嘗試在m2上重新分配新地圖（m3），m2的順序不保留爲m3。

爲什麼分配地圖會改變順序？

我的編譯器是蘋果LLVM版本8.1.0（鐺-802.0.42）

來源

2017-08-10 Gonzalo Solera

我喜歡你認識到沒有內部o的部分一個*無序*地圖....然後仍然奇怪爲什麼訂單不一致 – CoryKramer

@CoryKramer這是一個很好的問題，但。問題是爲什麼後備存儲未被複制*原樣*;爲什麼重新安排？ – Justin

@Justin如果答案只是「支持存儲是實現定義的，因此沒有人能給你一個比隨機猜測或實現具體細節更好的答案」我們應該如何處理這些信息？ – CoryKramer

這是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的元素插入此向量中。

這意味着，當你這樣做：

m2 = m1;

這大致相當於下面的代碼：

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

當您使用libstdc++這不會發生，作爲其實現的operator=只是= default（請參閱libstdC++的unordered_map header）

來源

2017-08-10 18:23:22 Justin

在wandbox上試用它，我的「等效代碼」並不完全等效：https：//wandbox.org/permlink/byubQ9VEU9UPCcsf。這可能只是* libC++ *的不同版本，或者完全不同的標準庫 – Justin

因爲這顯然是實現特定的（它是一個無序地圖畢竟）我要做出一個受過教育的投機。

如果mark和john具有相同的哈希值並且相關的桶數相互衝突，並且實現使用鏈接，我們可能可以解釋這一點。如果鏈接實現在前面插入新項目（即使對於單鏈表也是恆定的時間），那麼每次分配容器時，鏈接項目順序都將被交換。

來源

2017-08-10 17:38:55

我覺得'mark'和'john'會有相同的散列，而且如果是這樣，這個問題應該通過使用不同的字符串消失，這似乎並不是這種情況（例如https://wandbox.org/permlink/hFVcM6fuLAG72rzx）。當然，不同的字符串可能會發生碰撞，但不應該很難找到不會碰撞的字符串。 – Justin

unordered_map更改的順序

回答

相關問題