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

C++ 頭文件系列(unordered_map、unordered_set)。本站提示廣大學習愛好者：（C++ 頭文件系列(unordered_map、unordered_set)）文章只能為提供參考，不一定能成為您想要的結果。以下是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_count ： 桶數量。
• max_bucket_count ： 最大桶數量。
• bucket_size ： 桶大小，即容量。
• bucket ： 定位給定元素的桶地位。

• load_factor ： 前往load factor，即容器以後元素數量與桶數量之比。
• max_load_factor ： 前往或設置最大load factor。
• rehash ： 設置桶的數量，偏重新對元素停止哈希映射。
• reserve ： 懇求保存桶的數量至給定值。

留意到，沒有函數能改動桶的容量，能夠桶也是靜態增長的。

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