爲什麼我的unordered_map會自行排序？

所以我正在玩STL新標準化的unordered_map。我的代碼是有點這樣的，我只是創建一個unordered_map，填滿它，並把它打印出來：爲什麼我的unordered_map會自行排序？

unordered_map<int,string> m1; 

    m1[5]="lamb"; 
    m1[2]="had"; 
    m1[3]="a"; 
    m1[1]="mary"; 
    m1[4]="little"; 
    m1[7]="fleece"; 
    m1[6]="whose"; 
    m1[10]="fleecey"; 
    m1[8]="was"; 
    m1[9]="all"; 

for(unordered_map<int,string>::const_iterator i = m1.begin(); i != m1.end(); ++i) 
cout<<i->first<<" "<<i->second<<endl;

然而，輸出我得到正是如此下令：

1 mary 
2 had 
3 a 
4 little 
5 lamb 
6 whose 
7 fleece 
8 was 
9 all 
10 fleecey

但我不想付出代價來訂購我的地圖！這就是爲什麼我使用unordered_map ...這裏發生了什麼？另外

注：我使用gcc version 4.3.4 20090804 (release) 1 (GCC)和我編寫這樣g++ -std=c++0X maptest.cpp

來源

2011-07-29 Jimmy

可能，大小爲<='sizeof（std :: size_t）'的整數類型的哈希函數只是標識函數。 – ildjarn

爲了好玩，試着改變'm1 [10] =「fleecey」;'像'm1 [154297] =「fleecey」;':) – JohannesD

「無序」並不意味着它會隨機存儲項目或維持你把他們在地圖上的順序。這隻意味着你不能依賴任何特定的順序。你不需要爲訂購付出代價，恰恰相反 - 實現並沒有明確訂購物品，它是一個散列表，並以任何喜歡的方式存儲它的元素，這通常是一種非常高效的方式。恰巧恰巧，地圖的散列算法和其他內部工作，在使用這些鍵和這些數字和地圖上的操作順序時，最終會按照看起來有序的順序存儲這些項目。例如，字符串可能會導致明顯的隨機佈局。

在附註中，這可能是由使用散列的映射引起的，該散列將（至少一些）整數映射到自身並使用散列的較低位（與映射大小要求一樣多）來確定底層數組的索引（例如，CPython就是這樣做的 - 有一些巧妙的添加來相對簡單和高效地處理衝突;同樣的原因，CPython字符串和元組的哈希值也是可以預測的）。

來源

2011-07-29 23:49:14 delnan

是的，它會全部散列起來。謝謝。 – Jimmy

爲了您的娛樂，下面是來自libC++的輸出，它還具有std::hash<int>的身份識別功能。

9 all 
8 was 
10 fleecey 
6 whose 
7 fleece 
4 little 
1 mary 
3 a 
2 had 
5 lamb

有幾種方法來實現散列容器，每個方法都有自己的折衷。

來源

2011-07-30 02:13:20

爲什麼我的unordered_map會自行排序？

回答

相關問題