unordered_set如何確定C++中的插入順序？

我知道人們在使用unordered_set的時候並不關心集合中元素的順序。然而，當我在C++ Shell unordered_set如何確定C++中的插入順序？

#include <iostream> 
#include <unordered_set> 
#include <string> 

int main() 

{ 
std::unordered_set<std::string> inputSet; 
inputSet.insert("Hello world"); 
inputSet.insert("Abcdef"); 
inputSet.insert("This is the test string..."); 

for(const auto &val : inputSet) 
    std::cout << val.c_str() << std::endl; 

return 0;}

運行示例程序它給了我

This is the test string... 
Abcdef 
Hello world

我試着運行了3〜4倍，但它仍然給了我這意味着相同的輸出有是unordered_set確定插入順序的一種方式。

有人可以解釋unordered_set如何確定插入順序？

對不起，如果它之前已詢問，我在網上搜索了一段時間，我無法找到這個問題的具體答案。提前致謝。

來源

2016-12-26 user2185071

爲什麼你需要知道嗎？在任何情況下都不應該依賴訂單。 – mclaassen

@mclaassen有時我們應該有好奇心。 –

沒有特定的排序...它使用默認的std::hash來對字符串進行散列。此外，無論哈希值，它被轉換成容器適當鬥指數..

我們正在談論的哈希值，可以得到：

auto hello = std::hash<std::string>()("Hello world"); 
auto abcd = std::hash<std::string>()("Abcdef"); 
auto test = std::hash<std::string>()("This is the test string...");

對於特定的STL實現，這樣就解決了到：

Hello maps to: 14420674105493498572 
abcd maps to: 10830572898531769673 
test maps to: 13068738153895491918

實時查看上C++Shell

值通常被轉換爲通過申請一個適當的桶索引ying %運營商。 std::unordered_set的迭代器不是強制循環遍歷所有的桶（碰撞怎麼辦？）。所以，你不應該依賴你在程序運行之間從迭代器中觀察到的任何順序。

從C++ 14，std::hash<>是明確允許之間的不同的程序運行，以產生不同的結果。到quote：

散列函數只需要產生用於節目的單次執行中的相同的輸入相同的結果;這允許醃製哈希，防止碰撞DoS攻擊。

來源

2016-12-26 18:35:14 WhiZTiM

當我使用桶方法並輸入一些我沒有放入無序集的東西時，它仍然會返回一些桶，爲什麼？ –

另外我試圖找到這三個桶，它出來是相同的，但他們有不同的哈希？ –

如這裏指出http://en.cppreference.com/w/cpp/container/unordered_set

內部，元素在任何特定的順序排序，但組織成桶。一個元素被放入哪個桶完全取決於其值的哈希值。這允許快速訪問單個元素，因爲一旦計算了散列，它就指向該元素被放入的精確桶。

因此，它使用默認或用戶提供的散列算法來排序到散列桶中。

來源

2016-12-26 18:30:03

所以你說沒有辦法預測輸出？ – user2185071

@ user2185071我認爲輸出的「可預測性」取決於：類型（因爲類型決定了散列值，它只是一個數字）和插入順序（因爲對於相同的散列值 - 不太可能;順序與插入順序相同）。 –

無序集合針對插入和檢索進行了優化，而不是遍歷。如果廣告訂單是您的優先事項，請使用其他容器。 –

std::unordered_set<T>中的訂單是無序的。但是，假定使用確定性散列，並執行相同的插入操作順序，則程序的不同運行將具有相同順序的元素。以不同的順序插入元素和/或使用爲不同運行產生不同值的散列會產生不同的元素順序。

來源

2016-12-26 18:31:30

unordered_set如何確定C++中的插入順序？

回答

相關問題