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

簡(jiǎn)介

很明顯，這兩個(gè)頭文件分別是map、set頭文件對(duì)應(yīng)的unordered版本。 所以它們有一個(gè)重要的性質(zhì)就是：

• 亂序

如何亂序

這個(gè)unorder暗示著，這兩個(gè)頭文件中類(lèi)的底層實(shí)現(xiàn)----Hash。 也是因?yàn)槿绱耍悴趴梢栽诼暶鬟@些unordered模版類(lèi)的時(shí)候，傳入一個(gè)自定義的哈希函數(shù)，準(zhǔn)確的說(shuō)是哈希函數(shù)子（hash function object）。

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

為何亂序

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

用樹(shù)結(jié)構(gòu)（紅黑樹(shù)、二叉搜索樹(shù)等）實(shí)現(xiàn)的map、set，在查找、獲取、修改元素的時(shí)候，通常需要從根結(jié)點(diǎn)自上而下一次遍歷樹(shù)結(jié)構(gòu)，因此時(shí)間復(fù)雜度為線(xiàn)性 ； 而通過(guò)哈希表實(shí)現(xiàn)， 只要哈希函數(shù)以及桶的大小選取得當(dāng)，時(shí)間復(fù)雜度會(huì)是常數(shù)（只需要調(diào)用一次函數(shù)，并進(jìn)行小幅度的查找）。

單向迭代器

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

少了什么函數(shù)

• lower_bound

• upper_bound

普通版本的map和set，它們是有序容器，對(duì)每一個(gè)元素都能都能判斷它應(yīng)該在哪個(gè)之前、在哪個(gè)之后； 而該版本的容器則不一樣，因?yàn)樗鼈兪?strong >亂序的，不能確定每個(gè)元素的先后順序。 因此，容器沒(méi)有足夠的信息來(lái)計(jì)算這兩個(gè)邊界（然而元素的相等性比較依舊是可行的）。

多了什么函數(shù)

出于實(shí)現(xiàn)的概念，該版本的類(lèi)模版必不可少的多了些特殊的函數(shù)。

桶相關(guān)（Bucket）

• bucket_count ： 桶數(shù)量。

• max_bucket_count ： 最大桶數(shù)量。

• bucket_size ： 桶大小，即容量。

• bucket ： 定位給定元素的桶位置。

哈希策略

• load_factor ： 返回load factor，即容器當(dāng)前元素?cái)?shù)量與桶數(shù)量之比。

• max_load_factor ： 返回或設(shè)置最大load factor。

• rehash ： 設(shè)置桶的數(shù)量，并重新對(duì)元素進(jìn)行哈希映射。

• reserve ： 請(qǐng)求保留桶的數(shù)量至給定值。

注意到，沒(méi)有函數(shù)能改變桶的容量，可能桶也是動(dòng)態(tài)增長(zhǎng)的。

Observers

• hash_function : 返回哈希函數(shù)（在聲明時(shí)作為參數(shù)傳入，或默認(rèn)的位于funtional頭文件中的hash）。

• key_eq : 返回key的相等性謂詞，情況與hash_function相似。