C++ 頭文件系列(unordered_map、unordered_set)

簡介

很明顯，這兩個頭文件分別是map、set頭文件對應的unordered版本。 所以它們有一個重要的性質就是：

• 亂序

如何亂序

這個unorder暗示著，這兩個頭文件中類的底層實現----Hash。 也是因為如此，你才可以在聲明這些unordered模版類的時候，傳入一個自定義的哈希函數，准確的說是哈希函數子（hash function object）。

具有相同相同哈希值的元素被放在同一個桶（bucket）中。

為何亂序

在提供映射、集合功能的情況下，側重於元素的快速獲取。

用樹結構（紅黑樹、二叉搜索樹等）實現的map、set，在查找、獲取、修改元素的時候，通常需要從根結點自上而下一次遍歷樹結構，因此時間復雜度為線性 ； 而通過哈希表實現， 只要哈希函數以及桶的大小選取得當，時間復雜度會是常數（只需要調用一次函數，並進行小幅度的查找）。

單向迭代器

哈希表的實現復雜了該容器上的雙向遍歷，似乎沒有一種合適的方法能夠做到高效快速。 因此，unorder版本的map和set只提供前向迭代器（非unorder版本提供雙向迭代器）。

少了什麼函數

• lower_bound
• upper_bound

普通版本的map和set，它們是有序容器，對每一個元素都能都能判斷它應該在哪個之前、在哪個之後； 而該版本的容器則不一樣，因為它們是亂序的，不能確定每個元素的先後順序。 因此，容器沒有足夠的信息來計算這兩個邊界（然而元素的相等性比較依舊是可行的）。

多了什麼函數

出於實現的概念，該版本的類模版必不可少的多了些特殊的函數。

桶相關（Bucket）

• bucket_count ： 桶數量。
• max_bucket_count ： 最大桶數量。
• bucket_size ： 桶大小，即容量。
• bucket ： 定位給定元素的桶位置。

哈希策略

• load_factor ： 返回load factor，即容器當前元素數量與桶數量之比。
• max_load_factor ： 返回或設置最大load factor。
• rehash ： 設置桶的數量，並重新對元素進行哈希映射。
• reserve ： 請求保留桶的數量至給定值。

注意到，沒有函數能改變桶的容量，可能桶也是動態增長的。

Observers

• hash_function : 返回哈希函數（在聲明時作為參數傳入，或默認的位於funtional頭文件中的hash）。
• key_eq : 返回key的相等性謂詞，情況與hash_function相似。