科技改變生活 · 科技引領(lǐng)未來(lái)
科技改變生活 · 科技引領(lǐng)未來(lái)
繼 map、multimap、set、multiset 關(guān)聯(lián)式容器之后，從本節(jié)開(kāi)始，再講解一類(lèi)“特殊”的關(guān)聯(lián)式容器，它們常被稱(chēng)為“無(wú)序容器”、“哈希容器”或者“無(wú)序關(guān)聯(lián)容器”。
和關(guān)聯(lián)式容器一樣，無(wú)序容器也使用鍵值對(duì)（pair 類(lèi)型）的方式存儲(chǔ)數(shù)據(jù)。不過(guò)，本教程將二者分開(kāi)進(jìn)行講解，因?yàn)樗鼈冇斜举|(zhì)上的不同：
C++ STL 底層采用哈希表實(shí)現(xiàn)無(wú)序容器時(shí)，會(huì)將所有數(shù)據(jù)存儲(chǔ)到一整塊連續(xù)的內(nèi)存空間中，并且當(dāng)數(shù)據(jù)存儲(chǔ)位置發(fā)生沖突時(shí)，解決方法選用的是“鏈地址法”（又稱(chēng)“開(kāi)鏈法”）。有關(guān)哈希表存儲(chǔ)結(jié)構(gòu)，讀者可閱讀《哈希表(散列表)詳解》一文做詳細(xì)了解。
基于底層實(shí)現(xiàn)采用了不同的數(shù)據(jù)結(jié)構(gòu)，因此和關(guān)聯(lián)式容器相比，無(wú)序容器具有以下 2 個(gè)特點(diǎn)：
和關(guān)聯(lián)式容器一樣，無(wú)序容器只是一類(lèi)容器的統(tǒng)稱(chēng)，其包含有 4 個(gè)具體容器，分別為 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。
表 1 對(duì)這 4 種無(wú)序容器的功能做了詳細(xì)的介紹。
可能讀者已經(jīng)發(fā)現(xiàn)，以上 4 種無(wú)序容器的名稱(chēng)，僅是在前面所學(xué)的 4 種關(guān)聯(lián)式容器名稱(chēng)的基礎(chǔ)上，添加了 &34;unordered_&34;。如果讀者已經(jīng)學(xué)完了 map、multimap、set 和 multiset 容器不難發(fā)現(xiàn)，以 map 和 unordered_map 為例，其實(shí)它們僅有一個(gè)區(qū)別，即 map 容器內(nèi)存會(huì)對(duì)存儲(chǔ)的鍵值對(duì)進(jìn)行排序，而 unordered_map 不會(huì)。
也就是說(shuō)，C++ 11 標(biāo)準(zhǔn)的 STL 中，在已提供有 4 種關(guān)聯(lián)式容器的基礎(chǔ)上，又新增了各自的“unordered”版本（無(wú)序版本、哈希版本），提高了查找指定元素的效率。
有讀者可能會(huì)問(wèn)，既然無(wú)序容器和之前所學(xué)的關(guān)聯(lián)式容器類(lèi)似，那么在實(shí)際使用中應(yīng)該選哪種容器呢？總的來(lái)說(shuō)，實(shí)際場(chǎng)景中如果涉及大量遍歷容器的操作，建議首選關(guān)聯(lián)式容器；反之，如果更多的操作是通過(guò)鍵獲取對(duì)應(yīng)的值，則應(yīng)首選無(wú)序容器。
為了加深讀者對(duì)無(wú)序容器的認(rèn)識(shí)，這里以 unordered_map 容器為例，舉個(gè)例子（不必深究該容器的具體用法）：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建并初始化一個(gè) unordered_map 容器，其存儲(chǔ)的 類(lèi)型的鍵值對(duì)
std::unordered_map my_uMap{
{&34;C語(yǔ)言教程&34;,&34;http://c.biancheng.net/c/&34;},
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;} };
//查找指定鍵對(duì)應(yīng)的值，效率比關(guān)聯(lián)式容器高
string str = my_uMap.at(&34;C語(yǔ)言教程&34;);
cout << &34;str = &34; << str << endl;
//使用迭代器遍歷哈希容器，效率不如關(guān)聯(lián)式容器
for (auto iter = my_uMap.begin(); iter != my_uMap.end(); ++iter)
{
//pair 類(lèi)型鍵值對(duì)分為 2 部分
cout << iter->first << &34; &34; << iter->second << endl;
}
return 0;
} 程序執(zhí)行結(jié)果為：
str = http://c.biancheng.net/c/
C語(yǔ)言教程 http://c.biancheng.net/c/
Python教程 http://c.biancheng.net/python/
Java教程 http://c.biancheng.net/java/
C++ STL 標(biāo)準(zhǔn)庫(kù)中提供有 4 種無(wú)序關(guān)聯(lián)式容器，本節(jié)先講解 unordered_map 容器。
unordered_map 容器，直譯過(guò)來(lái)就是&34;無(wú)序 map 容器&34;的意思。所謂“無(wú)序”，指的是 unordered_map 容器不會(huì)像 map 容器那樣對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行排序。換句話說(shuō)，unordered_map 容器和 map 容器僅有一點(diǎn)不同，即 map 容器中存儲(chǔ)的數(shù)據(jù)是有序的，而 unordered_map 容器中是無(wú)序的。
對(duì)于已經(jīng)學(xué)過(guò) map 容器的讀者，可以將 unordered_map 容器等價(jià)為無(wú)序的 map 容器。
具體來(lái)講，unordered_map 容器和 map 容器一樣，以鍵值對(duì)（pair類(lèi)型）的形式存儲(chǔ)數(shù)據(jù)，存儲(chǔ)的各個(gè)鍵值對(duì)的鍵互不相同且不允許被修改。但由于 unordered_map 容器底層采用的是哈希表存儲(chǔ)結(jié)構(gòu)，該結(jié)構(gòu)本身不具有對(duì)數(shù)據(jù)的排序功能，所以此容器內(nèi)部不會(huì)自行對(duì)存儲(chǔ)的鍵值對(duì)進(jìn)行排序。
值得一提的是，unordered_map 容器在
include using namespace std; 注意，第二行代碼不是必需的，但如果不用，則后續(xù)程序中在使用此容器時(shí)，需手動(dòng)注明 std 命名空間（強(qiáng)烈建議初學(xué)者使用）。
unordered_map 容器模板的定義如下所示：
template < class Key, //鍵值對(duì)中鍵的類(lèi)型
class T, //鍵值對(duì)中值的類(lèi)型
class Hash = hash, //容器內(nèi)部存儲(chǔ)鍵值對(duì)所用的哈希函數(shù)
class Pred = equal_to, //判斷各個(gè)鍵值對(duì)鍵相同的規(guī)則
class Alloc = allocator< pairnst Key,T> > // 指定分配器對(duì)象的類(lèi)型
> class unordered_map; 以上 5 個(gè)參數(shù)中，必須顯式給前 2 個(gè)參數(shù)傳值，并且除特殊情況外，最多只需要使用前 4 個(gè)參數(shù)，各自的含義和功能如表 1 所示。
表 1 unordered_map 容器模板類(lèi)的常用參數(shù)
總的來(lái)說(shuō)，當(dāng)無(wú)序容器中存儲(chǔ)鍵值對(duì)的鍵為自定義類(lèi)型時(shí)，默認(rèn)的哈希函數(shù) hash 以及比較函數(shù) equal_to 將不再適用，只能自己設(shè)計(jì)適用該類(lèi)型的哈希函數(shù)和比較函數(shù)，并顯式傳遞給 Hash 參數(shù)和 Pred 參數(shù)。至于如何實(shí)現(xiàn)自定義，后續(xù)章節(jié)會(huì)做詳細(xì)講解。
常見(jiàn)的創(chuàng)建 unordered_map 容器的方法有以下幾種。
1) 通過(guò)調(diào)用 unordered_map 模板類(lèi)的默認(rèn)構(gòu)造函數(shù)，可以創(chuàng)建空的 unordered_map 容器。比如：
std::unordered_map umap; 由此，就創(chuàng)建好了一個(gè)可存儲(chǔ)
2) 當(dāng)然，在創(chuàng)建 unordered_map 容器的同時(shí)，可以完成初始化操作。比如：
std::unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} }; 通過(guò)此方法創(chuàng)建的 umap 容器中，就包含有 3 個(gè)鍵值對(duì)元素。
3) 另外，還可以調(diào)用 unordered_map 模板中提供的復(fù)制（拷貝）構(gòu)造函數(shù)，將現(xiàn)有 unordered_map 容器中存儲(chǔ)的鍵值對(duì)，復(fù)制給新建 unordered_map 容器。
例如，在第二種方式創(chuàng)建好 umap 容器的基礎(chǔ)上，再創(chuàng)建并初始化一個(gè) umap2 容器：
std::unordered_map umap2(umap); 由此，umap2 容器中就包含有 umap 容器中所有的鍵值對(duì)。
除此之外，C++ 11 標(biāo)準(zhǔn)中還向 unordered_map 模板類(lèi)增加了移動(dòng)構(gòu)造函數(shù)，即以右值引用的方式將臨時(shí) unordered_map 容器中存儲(chǔ)的所有鍵值對(duì)，全部復(fù)制給新建容器。例如：
//返回臨時(shí) unordered_map 容器的函數(shù)
std::unordered_map retUmap(){
std::unordered_maptempUmap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
return tempUmap;}
//調(diào)用移動(dòng)構(gòu)造函數(shù)，創(chuàng)建 umap2 容器
std::unordered_map umap2(retUmap()); 注意，無(wú)論是調(diào)用復(fù)制構(gòu)造函數(shù)還是拷貝構(gòu)造函數(shù)，必須保證 2 個(gè)容器的類(lèi)型完全相同。
4) 當(dāng)然，如果不想全部拷貝，可以使用 unordered_map 類(lèi)模板提供的迭代器，在現(xiàn)有 unordered_map 容器中選擇部分區(qū)域內(nèi)的鍵值對(duì)，為新建 unordered_map 容器初始化。例如：
//傳入 2 個(gè)迭代器，
std::unordered_map
umap2(++umap.begin(),umap.end()); 通過(guò)此方式創(chuàng)建的 umap2 容器，其內(nèi)部就包含 umap 容器中除第 1 個(gè)鍵值對(duì)外的所有其它鍵值對(duì)。
unordered_map 既可以看做是關(guān)聯(lián)式容器，更屬于自成一脈的無(wú)序容器。因此在該容器模板類(lèi)中，既包含一些在學(xué)習(xí)關(guān)聯(lián)式容器時(shí)常見(jiàn)的成員方法，還有一些屬于無(wú)序容器特有的成員方法。
表 2 列出了 unordered_map 類(lèi)模板提供的所有常用的成員方法以及各自的功能。
注意，對(duì)于實(shí)現(xiàn)互換 2 個(gè)相同類(lèi)型 unordered_map 容器的鍵值對(duì)，除了可以調(diào)用該容器模板類(lèi)中提供的 swap() 成員方法外，STL 標(biāo)準(zhǔn)庫(kù)還提供了同名的 swap() 非成員函數(shù)。
下面的樣例演示了表 2 中部分成員方法的用法：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空 umap 容器
unordered_map umap;
//向 umap 容器添加新鍵值對(duì)
umap.emplace(&34;Python教程&34;, &34;http://c.biancheng.net/python/&34;);
umap.emplace(&34;Java教程&34;, &34;http://c.biancheng.net/java/&34;);
umap.emplace(&34;Linux教程&34;, &34;http://c.biancheng.net/linux/&34;);
//輸出 umap 存儲(chǔ)鍵值對(duì)的數(shù)量
cout << &34;umap size = &34; << umap.size() << endl;
//使用迭代器輸出 umap 容器存儲(chǔ)的所有鍵值對(duì)
for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
cout << iter->first << &34; &34; << iter->second << endl;
}
return 0;
} 程序執(zhí)行結(jié)果為：
umap size = 3
Python教程 http://c.biancheng.net/python/
Linux教程 http://c.biancheng.net/linux/
Java教程 http://c.biancheng.net/java/
在了解哈希表存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上，本節(jié)將具體分析 C++ STL 無(wú)序容器（哈希容器）底層的實(shí)現(xiàn)原理。
C++ STL 標(biāo)準(zhǔn)庫(kù)中，不僅是 unordered_map 容器，所有無(wú)序容器的底層實(shí)現(xiàn)都采用的是哈希表存儲(chǔ)結(jié)構(gòu)。更準(zhǔn)確地說(shuō)，是用“鏈地址法”（又稱(chēng)“開(kāi)鏈法”）解決數(shù)據(jù)存儲(chǔ)位置發(fā)生沖突的哈希表，整個(gè)存儲(chǔ)結(jié)構(gòu)如圖 1 所示。
其中，Pi 表示存儲(chǔ)的各個(gè)鍵值對(duì)。
可以看到，當(dāng)使用無(wú)序容器存儲(chǔ)鍵值對(duì)時(shí)，會(huì)先申請(qǐng)一整塊連續(xù)的存儲(chǔ)空間，但此空間并不用來(lái)直接存儲(chǔ)鍵值對(duì)，而是存儲(chǔ)各個(gè)鏈表的頭指針，各鍵值對(duì)真正的存儲(chǔ)位置是各個(gè)鏈表的節(jié)點(diǎn)。
注意，STL 標(biāo)準(zhǔn)庫(kù)通常選用 vector 容器存儲(chǔ)各個(gè)鏈表的頭指針。
不僅如此，在 C++ STL 標(biāo)準(zhǔn)庫(kù)中，將圖 1 中的各個(gè)鏈表稱(chēng)為桶（bucket），每個(gè)桶都有自己的編號(hào)（從 0 開(kāi)始）。當(dāng)有新鍵值對(duì)存儲(chǔ)到無(wú)序容器中時(shí)，整個(gè)存儲(chǔ)過(guò)程分為如下幾步：
另外值得一提的是，哈希表存儲(chǔ)結(jié)構(gòu)還有一個(gè)重要的屬性，稱(chēng)為負(fù)載因子（load factor）。該屬性同樣適用于無(wú)序容器，用于衡量容器存儲(chǔ)鍵值對(duì)的空/滿(mǎn)程序，即負(fù)載因子越大，意味著容器越滿(mǎn)，即各鏈表中掛載著越多的鍵值對(duì)，這無(wú)疑會(huì)降低容器查找目標(biāo)鍵值對(duì)的效率；反之，負(fù)載因子越小，容器肯定越空，但并不一定各個(gè)鏈表中掛載的鍵值對(duì)就越少。
舉個(gè)例子，如果設(shè)計(jì)的哈希函數(shù)不合理，使得各個(gè)鍵值對(duì)的鍵帶入該函數(shù)得到的哈希值始終相同（所有鍵值對(duì)始終存儲(chǔ)在同一鏈表上）。這種情況下，即便增加桶數(shù)是的負(fù)載因子減小，該容器的查找效率依舊很差。
無(wú)序容器中，負(fù)載因子的計(jì)算方法為：
負(fù)載因子 = 容器存儲(chǔ)的總鍵值對(duì) / 桶數(shù)
默認(rèn)情況下，無(wú)序容器的最大負(fù)載因子為 1.0。如果操作無(wú)序容器過(guò)程中，使得最大復(fù)雜因子超過(guò)了默認(rèn)值，則容器會(huì)自動(dòng)增加桶數(shù)，并重新進(jìn)行哈希，以此來(lái)減小負(fù)載因子的值。需要注意的是，此過(guò)程會(huì)導(dǎo)致容器迭代器失效，但指向單個(gè)鍵值對(duì)的引用或者指針仍然有效。
這也就解釋了，為什么我們?cè)诓僮鳠o(wú)序容器過(guò)程中，鍵值對(duì)的存儲(chǔ)順序有時(shí)會(huì)“莫名”的發(fā)生變動(dòng)。
C++ STL 標(biāo)準(zhǔn)庫(kù)為了方便用戶(hù)更好地管控?zé)o序容器底層使用的哈希表存儲(chǔ)結(jié)構(gòu)，各個(gè)無(wú)序容器的模板類(lèi)中都提供表 2 所示的成員方法。
表 2 無(wú)序容器管理哈希表的成員方法
下面的程序以學(xué)過(guò)的 unordered_map 容器為例，演示了表 2 中部分成員方法的用法：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空 umap 容器
unordered_map umap;
cout << &34;umap 初始桶數(shù): &34; << umap.bucket_count() << endl;
cout << &34;umap 初始負(fù)載因子: &34; << umap.load_factor() << endl;
cout << &34;umap 最大負(fù)載因子: &34; << umap.max_load_factor() << endl;
//設(shè)置 umap 使用最適合存儲(chǔ) 9 個(gè)鍵值對(duì)的桶數(shù)
umap.reserve(9);
cout << &34;*********************&34; << endl;
cout << &34;umap 新桶數(shù): &34; << umap.bucket_count() << endl;
cout << &34;umap 新負(fù)載因子: &34; << umap.load_factor() << endl;
//向 umap 容器添加 3 個(gè)鍵值對(duì)
umap[&34;Python教程&34;] = &34;http://c.biancheng.net/python/&34;;
umap[&34;Java教程&34;] = &34;http://c.biancheng.net/java/&34;;
umap[&34;Linux教程&34;] = &34;http://c.biancheng.net/linux/&34;;
//調(diào)用 bucket() 獲取指定鍵值對(duì)位于桶的編號(hào)
cout << &34;以&34;Python教程&34;為鍵的鍵值對(duì)，位于桶的編號(hào)為:&34; << umap.bucket(&34;Python教程&34;) << endl;
//自行計(jì)算某鍵值對(duì)位于哪個(gè)桶
auto fn = umap.hash_function();
cout << &34;計(jì)算以&34;Python教程&34;為鍵的鍵值對(duì)，位于桶的編號(hào)為：&34; << fn(&34;Python教程&34;) % (umap.bucket_count()) << endl;
return 0;
} 程序執(zhí)行結(jié)果為：
umap 初始桶數(shù): 8
umap 初始負(fù)載因子: 0
umap 最大負(fù)載因子: 1
*********************
umap 新桶數(shù): 16
umap 新負(fù)載因子: 0
以&34;Python教程&34;為鍵的鍵值對(duì)，位于桶的編號(hào)為:9
計(jì)算以&34;Python教程&34;為鍵的鍵值對(duì)，位于桶的編號(hào)為：9
從輸出結(jié)果可以看出，對(duì)于空的 umap 容器，初始狀態(tài)下會(huì)分配 8 個(gè)桶，并且默認(rèn)最大負(fù)載因子為 1.0，但由于其為存儲(chǔ)任何鍵值對(duì)，因此負(fù)載因子值為 0。
與此同時(shí)，程序中調(diào)用 reverse() 成員方法，是 umap 容器的桶數(shù)改為了 16，其最適合存儲(chǔ) 9 個(gè)鍵值對(duì)。從側(cè)面可以看出，一旦負(fù)載因子大于 1.0（9/8 > 1.0），則容器所使用的桶數(shù)就會(huì)翻倍式（8、16、32、...）的增加。
程序最后還演示了如何手動(dòng)計(jì)算出指定鍵值對(duì)存儲(chǔ)的桶的編號(hào)，其計(jì)算結(jié)果和使用 bucket() 成員方法得到的結(jié)果是一致的。
C++ STL 標(biāo)準(zhǔn)庫(kù)中，unordered_map 容器迭代器的類(lèi)型為前向迭代器（又稱(chēng)正向迭代器）。這意味著，假設(shè) p 是一個(gè)前向迭代器，則其只能進(jìn)行 *p、p++、++p 操作，且 2 個(gè)前向迭代器之間只能用 == 和 != 運(yùn)算符做比較。
在 unordered_map 容器模板中，提供了表 1 所示的成員方法，可用來(lái)獲取指向指定位置的前向迭代器。
表 1 C++ unordered_map迭代器相關(guān)成員方法
值得一提的是，equal_range(key) 很少用于 unordered_map 容器，因?yàn)樵撊萜髦写鎯?chǔ)的都是鍵不相等的鍵值對(duì)，即便調(diào)用該成員方法，得到的 2 個(gè)迭代器所表示的范圍中，最多只包含 1 個(gè)鍵值對(duì)。事實(shí)上，該成員方法更適用于 unordered_multimap 容器（該容器后續(xù)章節(jié)會(huì)做詳細(xì)講解）。
下面的程序演示了表 1 中部分成員方法的用法。
include
include
include
using namespace std;
int main()
{
//創(chuàng)建 umap 容器
unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
cout << &34;umap 存儲(chǔ)的鍵值對(duì)包括：&34; << endl;
//遍歷輸出 umap 容器中所有的鍵值對(duì)
for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
cout << &34;<&34; << iter->first << &34;, &34; << iter->second << &34;>&34; << endl;
}
//獲取指向指定鍵值對(duì)的前向迭代器
unordered_map::iterator iter = umap.find(&34;Java教程&34;);
cout <<&34;umap.find(&34;Java教程&34;) = &34; << &34;<&34; << iter->first << &34;, &34; << iter->second << &34;>&34; << endl;
return 0;
} 程序執(zhí)行結(jié)果為：
umap 存儲(chǔ)的鍵值對(duì)包括：
umap.find(&34;Java教程&34;) =
需要注意的是，在操作 unordered_map 容器過(guò)程（尤其是向容器中添加新鍵值對(duì)）中，一旦當(dāng)前容器的負(fù)載因子超過(guò)最大負(fù)載因子（默認(rèn)值為 1.0），該容器就會(huì)適當(dāng)增加桶的數(shù)量（通常是翻一倍），并自動(dòng)執(zhí)行 rehash() 成員方法，重新調(diào)整各個(gè)鍵值對(duì)的存儲(chǔ)位置（此過(guò)程又稱(chēng)“重哈希”），此過(guò)程很可能導(dǎo)致之前創(chuàng)建的迭代器失效。
所謂迭代器失效，針對(duì)的是那些用于表示容器內(nèi)某個(gè)范圍的迭代器，由于重哈希會(huì)重新調(diào)整每個(gè)鍵值對(duì)的存儲(chǔ)位置，所以容器重哈希之后，之前表示特定范圍的迭代器很可能無(wú)法再正確表示該范圍。但是，重哈希并不會(huì)影響那些指向單個(gè)鍵值對(duì)元素的迭代器。
舉個(gè)例子：
include
include
using namespace std;
int main()
{
//創(chuàng)建 umap 容器
unordered_map umap;
//向 umap 容器添加 50 個(gè)鍵值對(duì)
for (int i = 1; i <= 50; i++) {
umap.emplace(i, i);
}
//獲取鍵為 49 的鍵值對(duì)所在的范圍
auto pair = umap.equal_range(49);
//輸出 pair 范圍內(nèi)的每個(gè)鍵值對(duì)的鍵的值
for (auto iter = pair.first; iter != pair.second; ++iter) {
cout << iter->first <<&34; &34;;
}
cout << endl;
//手動(dòng)調(diào)整最大負(fù)載因子數(shù)
umap.max_load_factor(3.0);
//手動(dòng)調(diào)用 rehash() 函數(shù)重哈希
umap.rehash(10);
//重哈希之后，pair 的范圍可能會(huì)發(fā)生變化
for (auto iter = pair.first; iter != pair.second; ++iter) {
cout << iter->first << &34; &34;;
}
return 0;
} 程序執(zhí)行結(jié)果為：
49
49 17
觀察輸出結(jié)果不難發(fā)現(xiàn)，之前用于表示鍵為 49 的鍵值對(duì)所在范圍的 2 個(gè)迭代器，重哈希之后表示的范圍發(fā)生了改變。
經(jīng)測(cè)試，用于遍歷整個(gè)容器的 begin()/end() 和 cbegin()/cend() 迭代器對(duì)，重哈希只會(huì)影響遍歷容器內(nèi)鍵值對(duì)的順序，整個(gè)遍歷的操作仍然可以順利完成。
通過(guò)前面的學(xué)習(xí)我們知道，unordered_map 容器以鍵值對(duì)的方式存儲(chǔ)數(shù)據(jù)。為了方便用戶(hù)快速地從該類(lèi)型容器提取出目標(biāo)元素（也就是某個(gè)鍵值對(duì)的值），unordered_map 容器類(lèi)模板中提供了以下幾種方法。
1) unordered_map 容器類(lèi)模板中，實(shí)現(xiàn)了對(duì) [ ] 運(yùn)算符的重載，使得我們可以像“利用下標(biāo)訪問(wèn)普通數(shù)組中元素”那樣，通過(guò)目標(biāo)鍵值對(duì)的鍵獲取到該鍵對(duì)應(yīng)的值。
舉個(gè)例子：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建 umap 容器
unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
//獲取 &34;Java教程&34; 對(duì)應(yīng)的值
string str = umap[&34;Java教程&34;];
cout << str << endl;
return 0;
} 程序輸出結(jié)果為：
http://c.biancheng.net/java/
需要注意的是，如果當(dāng)前容器中并沒(méi)有存儲(chǔ)以 [ ] 運(yùn)算符內(nèi)指定的元素作為鍵的鍵值對(duì)，則此時(shí) [ ] 運(yùn)算符的功能將轉(zhuǎn)變?yōu)椋?strong>向當(dāng)前容器中添加以目標(biāo)元素為鍵的鍵值對(duì)。舉個(gè)例子：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空 umap 容器
unordered_map umap;
//[] 運(yùn)算符在 = 右側(cè)
string str = umap[&34;STL教程&34;];
//[] 運(yùn)算符在 = 左側(cè)
umap[&34;C教程&34;] = &34;http://c.biancheng.net/c/&34;;
for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
cout << iter->first << &34; &34; << iter->second << endl;
}
return 0;
} 程序執(zhí)行結(jié)果為：
C教程 http://c.biancheng.net/c/
STL教程
可以看到，當(dāng)使用 [ ] 運(yùn)算符向 unordered_map 容器中添加鍵值對(duì)時(shí)，分為 2 種情況：
2) unordered_map 類(lèi)模板中，還提供有 at() 成員方法，和使用 [ ] 運(yùn)算符一樣，at() 成員方法也需要根據(jù)指定的鍵，才能從容器中找到該鍵對(duì)應(yīng)的值；不同之處在于，如果在當(dāng)前容器中查找失敗，該方法不會(huì)向容器中添加新的鍵值對(duì)，而是直接拋出out_of_range異常。
舉個(gè)例子：
include
include
include
using namespace std;
int main(){
//創(chuàng)建 umap 容器
unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
//獲取指定鍵對(duì)應(yīng)的值
string str = umap.at(&34;Python教程&34;);
cout << str << endl;
//執(zhí)行此語(yǔ)句會(huì)拋出 out_of_range 異常
//cout << umap.at(&34;GO教程&34;);
return 0;} 程序執(zhí)行結(jié)果為：
http://c.biancheng.net/python/
此程序中，第 13 行代碼用于獲取 umap 容器中鍵為“Python教程”對(duì)應(yīng)的值，由于 umap 容器確實(shí)有符合條件的鍵值對(duì)，因此可以成功執(zhí)行；而第 17 行代碼，由于當(dāng)前 umap 容器沒(méi)有存儲(chǔ)以“Go教程”為鍵的鍵值對(duì)，因此執(zhí)行此語(yǔ)句會(huì)拋出 out_of_range 異常。
3) [ ] 運(yùn)算符和 at() 成員方法基本能滿(mǎn)足大多數(shù)場(chǎng)景的需要。除此之外，還可以借助 unordered_map 模板中提供的 find() 成員方法。
和前面方法不同的是，通過(guò) find() 方法得到的是一個(gè)正向迭代器，該迭代器的指向分以下 2 種情況：
舉個(gè)例子：
include
include
include
using namespace std;
int main(){
//創(chuàng)建 umap 容器
unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
//查找成功
unordered_map::iterator iter = umap.find(&34;Python教程&34;);
cout << iter->first << &34; &34; << iter->second << endl;
//查找失敗
unordered_map::iterator iter2 = umap.find(&34;GO教程&34;);
if (iter2 == umap.end()) {
cout << &34;當(dāng)前容器中沒(méi)有以&34;GO教程&34;為鍵的鍵值對(duì)&34;;
}
return 0;} 程序執(zhí)行結(jié)果為：
Python教程 http://c.biancheng.net/python/
當(dāng)前容器中沒(méi)有以&34;GO教程&34;為鍵的鍵值對(duì)
4) 除了 find() 成員方法之外，甚至可以借助 begin()/end() 或者 cbegin()/cend()，通過(guò)遍歷整個(gè)容器中的鍵值對(duì)來(lái)找到目標(biāo)鍵值對(duì)。
舉個(gè)例子：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建 umap 容器
unordered_map umap{
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;},
{&34;Linux教程&34;,&34;http://c.biancheng.net/linux/&34;} };
//遍歷整個(gè)容器中存儲(chǔ)的鍵值對(duì)
for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
//判斷當(dāng)前的鍵值對(duì)是否就是要找的
if (!iter->first.compare(&34;Java教程&34;)) {
cout << iter->second << endl;
break;
}
}
return 0;
} 程序執(zhí)行結(jié)果為：
http://c.biancheng.net/java/
以上 4 種方法中，前 2 種方法基本能滿(mǎn)足多數(shù)場(chǎng)景的需要，建議初學(xué)者首選 at() 成員方法！
為了方便用戶(hù)向已建 unordered_map 容器中添加新的鍵值對(duì)，該容器模板中提供了 insert() 方法，本節(jié)就對(duì)此方法的用法做詳細(xì)的講解。
unordered_map 模板類(lèi)中，提供了多種語(yǔ)法格式的 insert() 方法，根據(jù)功能的不同，可劃分為以下幾種用法。
1) insert() 方法可以將 pair 類(lèi)型的鍵值對(duì)元素添加到 unordered_map 容器中，其語(yǔ)法格式有 2 種：
//以普通方式傳遞參數(shù)
pair
//以右值引用的方式傳遞參數(shù)
template
pair
為了方便用戶(hù)向已建 unordered_map 容器中添加新的鍵值對(duì)，該容器模板中提供了 insert() 方法，本節(jié)就對(duì)此方法的用法做詳細(xì)的講解。
unordered_map 模板類(lèi)中，提供了多種語(yǔ)法格式的 insert() 方法，根據(jù)功能的不同，可劃分為以下幾種用法。
1) insert() 方法可以將 pair 類(lèi)型的鍵值對(duì)元素添加到 unordered_map 容器中，其語(yǔ)法格式有 2 種：
//以普通方式傳遞參數(shù)
pair
//以右值引用的方式傳遞參數(shù)
template
pair
以上 2 種格式中，參數(shù) val 表示要添加到容器中的目標(biāo)鍵值對(duì)元素；該方法的返回值為 pair類(lèi)型值，內(nèi)部包含一個(gè) iterator 迭代器和 bool 變量：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空 umap 容器
unordered_map umap;
//構(gòu)建要添加的鍵值對(duì)
std::pairmypair(&34;STL教程&34;, &34;http://c.biancheng.net/stl/&34;);
//創(chuàng)建接收 insert() 方法返回值的pair類(lèi)型變量
std::pair::iterator, bool> ret;
//調(diào)用 insert() 方法的第一種語(yǔ)法格式
ret = umap.insert(mypair);
cout << &34;bool = &34; << ret.second << endl;
cout << &34;iter -> &34; << ret.first->first <<&34; &34; << ret.first->second << endl;
//調(diào)用 insert() 方法的第二種語(yǔ)法格式
ret = umap.insert(std::make_pair(&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;));
cout << &34;bool = &34; << ret.second << endl;
cout << &34;iter -> &34; << ret.first->first << &34; &34; << ret.first->second << endl;
return 0;
}
程序執(zhí)行結(jié)果為：
bool = 1
iter -> STL教程 http://c.biancheng.net/stl/
bool = 1
iter -> Python教程 http://c.biancheng.net/python/
從輸出結(jié)果很容易看出，兩次添加鍵值對(duì)的操作，insert() 方法返回值中的 bool 變量都為 1，表示添加成功，此時(shí)返回的迭代器指向的是添加成功的鍵值對(duì)。
2) 除此之外，insert() 方法還可以指定新鍵值對(duì)要添加到容器中的位置，其語(yǔ)法格式如下：
//以普通方式傳遞 val 參數(shù)
iterator insert ( const_iterator hint, const value_type& val );
//以右值引用方法傳遞 val 參數(shù)
template
iterator insert ( const_iterator hint, P&& val );
以上 2 種語(yǔ)法格式中，hint 參數(shù)為迭代器，用于指定新鍵值對(duì)要添加到容器中的位置；val 參數(shù)指的是要添加容器中的鍵值對(duì)；方法的返回值為迭代器：
注意，以上 2 種語(yǔ)法格式中，雖然通過(guò) hint 參數(shù)指定了新鍵值對(duì)添加到容器中的位置，但該鍵值對(duì)真正存儲(chǔ)的位置，并不是 hint 參數(shù)說(shuō)了算，最終的存儲(chǔ)位置仍取決于該鍵值對(duì)的鍵的值。
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空 umap 容器
unordered_map umap;
//構(gòu)建要添加的鍵值對(duì)
std::pairmypair(&34;STL教程&34;, &34;http://c.biancheng.net/stl/&34;);
//創(chuàng)建接收 insert() 方法返回值的迭代器類(lèi)型變量
unordered_map::iterator iter;
//調(diào)用第一種語(yǔ)法格式
iter = umap.insert(umap.begin(), mypair);
cout << &34;iter -> &34; << iter->first <<&34; &34; << iter->second << endl;
//調(diào)用第二種語(yǔ)法格式
iter = umap.insert(umap.begin(),std::make_pair(&34;Python教程&34;, &34;http://c.biancheng.net/python/&34;));
cout << &34;iter -> &34; << iter->first << &34; &34; << iter->second << endl;
return 0;
} 程序輸出結(jié)果為：
iter -> STL教程 http://c.biancheng.net/stl/
iter -> Python教程 http://c.biancheng.net/python/
3) insert() 方法還支持將某一個(gè) unordered_map 容器中指定區(qū)域內(nèi)的所有鍵值對(duì)，復(fù)制到另一個(gè) unordered_map 容器中，其語(yǔ)法格式如下：
template
void insert ( InputIterator first, InputIterator last );
其中 first 和 last 都為迭代器，[first, last)表示復(fù)制其它 unordered_map 容器中鍵值對(duì)的區(qū)域。
include
include
include
using namespace std;
int main()
{
//創(chuàng)建并初始化 umap 容器
unordered_map umap{ {&34;STL教程&34;,&34;http://c.biancheng.net/stl/&34;},
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;} };
//創(chuàng)建一個(gè)空的 unordered_map 容器
unordered_map otherumap;
//指定要拷貝 umap 容器中鍵值對(duì)的范圍
unordered_map::iterator first = ++umap.begin();
unordered_map::iterator last = umap.end();
//將指定 umap 容器中 [first,last) 區(qū)域內(nèi)的鍵值對(duì)復(fù)制給 otherumap 容器
otherumap.insert(first, last);
//遍歷 otherumap 容器中存儲(chǔ)的鍵值對(duì)
for (auto iter = otherumap.begin(); iter != otherumap.end(); ++iter){
cout << iter->first << &34; &34; << iter->second << endl;
}
return 0;
} 程序輸出結(jié)果為：
Python教程 http://c.biancheng.net/python/
Java教程 http://c.biancheng.net/java/
4) 除了以上 3 種方式，insert() 方法還支持一次向 unordered_map 容器添加多個(gè)鍵值對(duì)，其語(yǔ)法格式如下：
void insert ( initializer_list
其中，il 參數(shù)指的是可以用初始化列表的形式指定多個(gè)鍵值對(duì)元素。
include
include
include
using namespace std;
int main()
{
//創(chuàng)建空的 umap 容器
unordered_map umap;
//向 umap 容器同時(shí)添加多個(gè)鍵值對(duì)
umap.insert({ {&34;STL教程&34;,&34;http://c.biancheng.net/stl/&34;},
{&34;Python教程&34;,&34;http://c.biancheng.net/python/&34;},
{&34;Java教程&34;,&34;http://c.biancheng.net/java/&34;} });
//遍歷輸出 umap 容器中存儲(chǔ)的鍵值對(duì)
for (auto iter = umap.begin(); iter != umap.end(); ++iter){
cout << iter->first << &34; &34; << iter->second << endl;
}
return 0;
} 程序輸出結(jié)果為：
STL教程 http://c.biancheng.net/stl/
Python教程 http://c.biancheng.net/python/
Java教程 http://c.biancheng.net/java/
和前面學(xué)的 map、set 等容器一樣，C++ 11 標(biāo)準(zhǔn)也為 unordered_map 容器新增了 emplace() 和 emplace_hint() 成員方法，本節(jié)將對(duì)它們的用法做詳細(xì)的介紹。
我們知道，實(shí)現(xiàn)向已有 unordered_map 容器中添加新鍵值對(duì)，可以通過(guò)調(diào)用 insert() 方法，但其實(shí)還有更好的方法，即使用 emplace() 或者 emplace_hint() 方法，它們完成“向容器中添加新鍵值對(duì)”的效率，要比 insert() 方法高。
emplace() 方法的用法很簡(jiǎn)單，其語(yǔ)法格式如下：
template
pair
其中，參數(shù) args 表示可直接向該方法傳遞創(chuàng)建新鍵值對(duì)所需要的 2 個(gè)元素的值，其中第一個(gè)元素將作為鍵值對(duì)的鍵，另一個(gè)作為鍵值對(duì)的值。也就是說(shuō)，該方法無(wú)需我們手動(dòng)創(chuàng)建鍵值對(duì)，其內(nèi)部會(huì)自行完成此工作。
另外需要注意的是，該方法的返回值為 pair 類(lèi)型值，其包含一個(gè)迭代器和一個(gè) bool 類(lèi)型值：
include
include
include
using namespace std;
int main()
{
//創(chuàng)建 umap 容器
unordered_map umap;
//定義一個(gè)接受 emplace() 方法的 pair 類(lèi)型變量
pair::iterator, bool> ret;
//調(diào)用 emplace() 方法
ret = umap.emplace(&34;STL教程&34;, &34;http://c.biancheng.net/stl/&34;);
//輸出 ret 中包含的 2 個(gè)元素的值
cout << &34;bool =&34; << ret.second << endl;
cout << &34;iter ->&34; << ret.first->first << &34; &34; << ret.first->second << endl;
return 0;
} 程序執(zhí)行結(jié)果為：
bool =1
iter ->STL教程 http://c.biancheng.net/stl/
通過(guò)執(zhí)行結(jié)果中 bool 變量的值為 1 可以得知，emplace() 方法成功將新鍵值對(duì)添加到了 umap 容器中。
emplace_hint() 方法的語(yǔ)法格式如下：
template
iterator emplace_hint ( const_iterator position, Args&&... args );
和 emplace() 方法相同，emplace_hint() 方法內(nèi)部會(huì)自行構(gòu)造新鍵值對(duì)，因此我們只需向其傳遞構(gòu)建該鍵值對(duì)所需的 2 個(gè)元素（第一個(gè)作為鍵，另一個(gè)作為值）即可。不同之處在于：
可以這樣理解，emplace_hint() 方法中傳入的迭代器，僅是給 unordered_map 容器提供一個(gè)建議，并不一定會(huì)被容器采納。
舉個(gè)例子：
include
include
include
using namespace std;
int main(){
//創(chuàng)建 umap 容器
unordered_map umap;
//定義一個(gè)接受 emplace_hint() 方法的迭代器
unordered_map::iterator iter;
//調(diào)用 empalce_hint() 方法
iter = umap.emplace_hint(umap.begin(),&34;STL教程&34;, &34;http://c.biancheng.net/stl/&34;);
//輸出 emplace_hint() 返回迭代器 iter 指向的鍵值對(duì)的內(nèi)容
cout << &34;iter ->&34; << iter->first << &34; &34; << iter->second << endl;
return 0;
} 程序執(zhí)行結(jié)果為：
iter ->STL教程 http://c.biancheng.net/stl/
高悅明