爲什麼`std :: unordered_map`「像Yoda一樣說話」 - 重新排列元素？

Question

當試圖寫一個std::unordered_map的std::string鍵在下面的例子中，密鑰被寫入以不同的順序不是由初始化列表給出的一個：

#include <iostream> 
#include <unordered_map> 


class Data 
{ 
    typedef std::unordered_map<std::string, double> MapType; 
    typedef MapType::const_iterator const_iterator; 

    MapType map_; 

    public: 

     Data(const std::initializer_list<std::string>& i) 
     { 
      int counter = 0; 
      for (const auto& name : i) 
      { 
       map_[name] = counter; 
      } 
     } 


     const_iterator begin() const 
     { 
      return map_.begin(); 
     } 

     const_iterator end() const 
     { 
      return map_.end(); 
     } 

}; 

std::ostream& operator<<(std::ostream& os, const Data& d) 
{ 
    for (const auto& pair : d) 
    { 
     os << pair.first << " "; 
    } 
    return os; 
} 

using namespace std; 

int main(int argc, const char *argv[]) 
{ 
    Data d = {"Why", "am", "I", "sorted"}; 

    // The unordered_map speaks like Yoda. 
    cout << d << endl; 

    return 0; 
} 

我期望看到「爲什麼我整理」，但我得到了一個尤達樣輸出：

sorted I am Why 

閱讀上unordered_maphere，我看到這一點：

在內部，元素沒有按照任何特定的順序排序，而是組織成桶。一個元素放入哪個桶完全取決於其密鑰的散列。這允許快速訪問單個元素，因爲一旦計算了散列值，它就會指向該元素被放入的確切桶。

這就是爲什麼元素沒有按照初始化列表中相同的方式排序？

當我想以與初始化程序列表相同的方式對鍵進行排序時，我會使用什麼數據結構？我應該在內部保存一個字符串矢量以保存參數順序嗎？可以通過選擇特定的散列函數以某種方式關閉存儲桶組織？

Answer 1

當我想要以與初始化程序列表相同的方式排序鍵時，我會使用什麼數據結構？我應該在內部保存一個字符串矢量以保存參數順序嗎？

也許你想要的只是（鍵，值）對的列表/向量？

如果你希望O（1）查找（hashmap）和迭代的順序與插入相同 - 那麼是的，使用vector和unordered_map聽起來是個不錯的主意。例如，Django的SortedDict（Python）的正是這麼做的，這裏的靈感來源：

https://github.com/django/django/blob/master/django/utils/datastructures.py#L122

的Python 2。7的OrderedDict是一個比較花哨（圖值，指向雙向鏈表鏈接），請參閱：

http://code.activestate.com/recipes/576693-ordered-dictionary-for-py24/

---

我不知道現有的C++標準庫實現的，但這可能讓你到某個地方。另請參見：

• a C++ hash map that preserves the order of insertion
• A std::map that keep track of the order of insertion?

Answer 2

unordered_map根據定義，是無序的，所以你不應該期望順序訪問地圖時任何順序。

如果你不想通過密鑰值排序的元素，只使用，讓您的插入順序的容器，無論是vector，deque，list也好，pair<key, value>元素類型的，如果你堅持使用它。

然後，如果在元素A之後添加一個元素B，它總是會出現在後面。這也適用於initializer_list初始化。

您可能可以使用Boost.MultiIndex之類的東西來保持它既通過插入順序和任意鍵進行排序。