前言：

c++的各種容器使用的時(shí)候很方便，但是如果作為一個(gè)初學(xué)者，看到一堆庫(kù)要記住也是很頭疼的，而且很多庫(kù)名稱會(huì)很相似，所以我們要很好的使用這些庫(kù)的時(shí)候，我們需要了解清楚它們底層實(shí)現(xiàn)的原理，這樣我們使用中就更加得心應(yīng)手。

今天給大家分享一下map、multimap、unordered_map、unordered_multimap，看上去是不是很相似，今天就來(lái)描述幾者的區(qū)別。

作者：良知猶存

轉(zhuǎn)載授權(quán)以及圍觀：歡迎關(guān)注微信公眾號(hào)：羽林君

或者添加作者個(gè)人微信：become_me

幾種容器的初步介紹:

map簡(jiǎn)介

map是STL的一個(gè)關(guān)聯(lián)容器，map 容器中所有的元素都會(huì)根據(jù)元素對(duì)應(yīng)的鍵值來(lái)排序，而鍵值key 是唯一值，并不會(huì)出現(xiàn)同樣的鍵值key，也就是說(shuō)假設(shè)已經(jīng)有一個(gè)鍵值key 存在map 里，當(dāng)同樣的鍵值key 再insert 資料時(shí)，新的資料就會(huì)覆蓋掉原本key 的資料。

map 的實(shí)作方式通常是用紅黑樹(red-black tree)實(shí)作的，這樣它可以保證可以在O(log n)時(shí)間內(nèi)完成搜尋、插入、刪除，n為元素的數(shù)目。

常用函數(shù)

注意： 這里map的鍵值 key是不可以重復(fù)的，在實(shí)際使用中，如果用map[key] = xxx,其中key已經(jīng)存在的情況下，key對(duì)應(yīng)的元素會(huì)被覆蓋掉，如果是用insert方式進(jìn)行覆蓋則會(huì)失敗。

下面代碼里面用到了 first和second

map.first：第一個(gè)稱為(key)鍵值
map.second：第二個(gè)稱為(key)鍵值對(duì)應(yīng)的數(shù)值(value)

#include?
#include?
using?namespace?std;
int?main()
{
????std::map?studentMap?=?{
????{1,?"Tom"},
????{7,?"Mali"},
????{15,?"John"}};

????for(auto?i:studentMap2)
????{
????????cout<"?"
????????????<????????cout<????}
????std::pair::iterator,?bool>?retPair;
????retPair?=?studentMap.insert(std::pair(15,?"Bob"));??
????
????for(auto?i:studentMap)
????{
????????cout<"?"
????????????<????????cout<????}???


????studentMap[15]?=?"Lily";

????for(auto?i:studentMap)
????{
????????cout<"?"
????????????<????????cout<????}????
????
????cout<????studentMap.erase(15);
????for(auto?i:studentMap)
????{
????????cout<"?"
????????????<????????cout<????}????
}

輸出結(jié)果如圖所示：

multimap簡(jiǎn)介

multimaps是關(guān)聯(lián)式容器，它按照特定的順序，存儲(chǔ)由key和value映射成的鍵值對(duì)，其中多個(gè)鍵值對(duì)之間的key是可以重復(fù)的，multimap在底層用二叉搜索樹(紅黑樹)來(lái)實(shí)現(xiàn)。

在內(nèi)部，multimap中的元素總是通過(guò)其內(nèi)部比較對(duì)象，按照指定的特定嚴(yán)格弱排序標(biāo)準(zhǔn)對(duì)key進(jìn)行排序的。和map最大的區(qū)別，multimap中的key是可以重復(fù)的。

常用函數(shù)參照map函數(shù)使用

#include?
#include?
using?namespace?std;
int?main()
{
????std::multimap?studentMap2?=?{
????{"first",?"Tom"},
????{"second",?"Mali"},
????{"third",?"John"}};????


????studentMap2.insert(std::pair("first",?"Bob"));??
????
????cout<"output:"<????for?(std::multimap::iterator?it?=?studentMap2.begin();?it?!=?studentMap2.end();?it++)?{
????????std::cout?<",?"?<"\n";
????}
????std::cout?<"first")?<
}

以上代碼可以進(jìn)行debug 進(jìn)行查看，一個(gè)鍵值對(duì)應(yīng)多個(gè)元素，對(duì)應(yīng)數(shù)據(jù)排列的情況如下：

沖突的元素會(huì)使用元素鏈接的方式保存。

所以我們無(wú)法使用 multimap[key]進(jìn)行訪問(wèn)數(shù)據(jù)，是因?yàn)閙ultimap的key可以對(duì)應(yīng)多個(gè)數(shù)據(jù)，所以下標(biāo)訪問(wèn)是沒有意義的。

unordered_map簡(jiǎn)介

unordered_map 內(nèi)部實(shí)現(xiàn)了一個(gè)哈希表（也叫散列表，通過(guò)把關(guān)鍵碼值映射到Hash表中一個(gè)位置來(lái)訪問(wèn)記錄，查找的時(shí)間復(fù)雜度可達(dá)到O(1)，其在海量數(shù)據(jù)處理中有著廣泛應(yīng)用）。因此，其元素的排列順序是無(wú)序的。容器中每個(gè)元素都是 key/value，每個(gè) key 僅可出現(xiàn)一次。

unordered_map 特點(diǎn)就是搜尋效率高，利用鍵值與哈希函數(shù)(hash function)計(jì)算出哈希值而快速的查找到對(duì)應(yīng)的元素，時(shí)間復(fù)雜度為常數(shù)級(jí)別O(1)， 而額外空間復(fù)雜度則要高出許多。unordered_map 與map 的使用方法基本上一樣，都是key/value 之間的映射，只是他們內(nèi)部采用的資料結(jié)構(gòu)不一樣。所以對(duì)于需要高效率查詢的情況可以使用unordered_map 容器。而如果對(duì)記憶體消耗比較敏感或者資料存放要求排序的話則可以用map 容器。

常用函數(shù)參照map函數(shù)使用

#include?
#include?
using?namespace?std;
int?main()
{
???std::unordered_map??studentUMap3?=?{?
????????{?"Tom"?,?1?},?
????????{?"Ann"?,?4?},?
????????{?"Job"?,?2?}?
????};

???studentUMap3.insert(std::pair("Job",?5));??
????

????cout<"output:"<????for?(auto?it?=?studentUMap3.begin();?it?!=?studentUMap3.end();?it++)?{
????????std::cout?<",?"?<"\n";
????}

????cout<????studentUMap3["Job"]?=?3;
????for?(auto?it?=?studentUMap3.begin();?it?!=?studentUMap3.end();?it++)?{
????????std::cout?<",?"?<"\n";
????}
}

unordered_map用法和map基本一致，但是考慮的訪問(wèn)的速度有要求的情況下，我們優(yōu)先使用，unordered_map;要是考慮到空間大小對(duì)程序影響的時(shí)候，我們優(yōu)先使用map。

unordered_multimap簡(jiǎn)介

unordered_multimap 是一個(gè)封裝哈希表的無(wú)序容器。容器中每個(gè)元素都是 key/value，每個(gè) key 可重復(fù)出現(xiàn)。

同map和unordered_map區(qū)別一樣，multimap通過(guò)key訪問(wèn)單個(gè)元素的速度通常也比unordered_multimap容器慢。常用函數(shù)參照map函數(shù)使用

#include?
#include?
using?namespace?std;
int?main()
{
???std::unordered_multimap??studentUMap4;
????studentUMap4.insert(std::pair(1,?333));
????studentUMap4.insert(std::pair(3,?555));
????studentUMap4.insert(std::pair(5,?666));


???studentUMap4.insert(std::pair(5,?5));??
????

????cout<"output:"<????for?(auto?it?=?studentUMap4.begin();?it?!=?studentUMap4.end();?it++)?{
????????std::cout?<",?"?<"\n";
????}

????std::cout?<<"count:"<????std::cout?<<"size:?"<????std::cout?<<"empty?"<"\n"?<

????std::unordered_multimap?studentUMap5;
????studentUMap5.swap(studentUMap4);
????std::cout?<<"count:"<????std::cout?<<"size:?"<????std::cout?<<"empty?"<"\n"?<

????std::cout?<<"count:"?<"\n"?<

????studentUMap5.clear();
????std::cout?<<"size:?"?<????std::cout?<<"empty?"<}

重復(fù)元素對(duì)應(yīng)的debug顯示

代碼執(zhí)行輸出顯示

區(qū)別介紹

首先這幾個(gè)容器都是關(guān)聯(lián)容器，其中無(wú)論是有序關(guān)聯(lián)容器還是有序關(guān)聯(lián)容器都是基于(set:集合 key ?map:映射表 ?[key : value])

來(lái)自wiki

關(guān)聯(lián)容器是指C++標(biāo)準(zhǔn)模板庫(kù)中的一套類模板，實(shí)現(xiàn)了有序關(guān)聯(lián)數(shù)組。可用于存放任意數(shù)據(jù)類型的元素。C++標(biāo)準(zhǔn)中定義的關(guān)聯(lián)容器有：set, map, multiset, multimap。

關(guān)聯(lián)容器類似于C++中的無(wú)序關(guān)聯(lián)容器。差別為：

• 關(guān)聯(lián)容器是紅黑樹實(shí)現(xiàn)，無(wú)序關(guān)聯(lián)容器是哈希表實(shí)現(xiàn)。
  
• 關(guān)聯(lián)容器保證按鍵值有序遍歷，因此可以做范圍查找，而無(wú)序關(guān)聯(lián)容器不可以。
  
• 關(guān)聯(lián)支持一些導(dǎo)航類的>>操作，如求出給定鍵最鄰近的鍵，最大鍵、最小鍵操作。
  
• 關(guān)聯(lián)容器的迭代器不會(huì)失效，除非所指元素被刪除。
• 無(wú)序關(guān)聯(lián)容器的iterator在修改元素時(shí)可能會(huì)失>>效。所以對(duì)關(guān)聯(lián)容器的遍歷與修改在一定程度上可并行
  
• 哈希表查找時(shí)候要算hash，這個(gè)最壞時(shí)間復(fù)雜度是O(key的長(zhǎng)度)；基于比較的有序關(guān)聯(lián)容器通常只使用>頭幾個(gè)字符進(jìn)行比較

關(guān)聯(lián)容器不支持順序容器的位置相關(guān)的操作，例如 push_front 或 push_back 操作。原因是關(guān)聯(lián)容器中>的元素是根據(jù)關(guān)鍵字來(lái)存儲(chǔ)的，這些操作對(duì)于關(guān)聯(lián)容器沒有意義。

關(guān)聯(lián)容器也不支持構(gòu)造函數(shù)或插入操作這些接收一個(gè)元素值和一個(gè)數(shù)量值的操作。

因?yàn)閙ap和multimap unordered_map和unordered_multimap兩兩區(qū)分時(shí)候，從底層實(shí)現(xiàn)來(lái)說(shuō)，區(qū)別不是很大，所以我們先進(jìn)行map與multimap的區(qū)別，再進(jìn)行map和unordered_map區(qū)別比較。其他的類比即可。

最直觀的區(qū)別：

map和unordered_map;//key不允許重復(fù)，是單重映射表
multimap和unordered_multimap;//key允許重復(fù)，是多重映射表

實(shí)現(xiàn)機(jī)制的區(qū)別：

map和unordered_map的區(qū)別:內(nèi)部實(shí)現(xiàn)機(jī)理不同

• map :map內(nèi)部實(shí)現(xiàn)了一個(gè)紅黑樹（紅黑樹是非嚴(yán)格平衡二叉搜索樹，而AVL是嚴(yán)格平衡二叉搜索樹），紅黑樹具有自動(dòng)排序的功能，因此map內(nèi)部的所有元素都是有序的，紅黑樹的每一個(gè)節(jié)點(diǎn)都代表著map的一個(gè)元素。因此，對(duì)于map進(jìn)行的查找、刪除，添加等一系列的操作都相當(dāng)于是對(duì)紅黑樹進(jìn)行的操作。map中的元素是按照二叉搜索樹 （又名兒茶查找樹、二叉排序樹–特點(diǎn)就是左子樹上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹所有節(jié)點(diǎn)的鍵值都大于根結(jié)點(diǎn)的鍵值）存儲(chǔ)的，使用中序遍歷可將鍵值按照從小到大遍歷出來(lái)。map和multimap的區(qū)別在于，map不允許相同key值存在，multimap則允許相同的key值存在。

• unordered_map :unordered_map內(nèi)部實(shí)現(xiàn)了一個(gè)哈希表 （也叫散列表，通過(guò)把關(guān)鍵碼值映射到Hash表中一個(gè)位置來(lái)訪問(wèn)記錄，查找的時(shí)間復(fù)雜度可達(dá)到O(1)，其在海量數(shù)據(jù)處理中有著廣泛應(yīng)用）。因此，其元素的排列順序都是無(wú)序的。unordered_map 和 unordered_multimap 都是基于哈希表實(shí)現(xiàn)的，而且沖突策略采用的是鏈地址法。

使用的角度

空間占用率和效率上

unorder_map占用的內(nèi)存更加高一點(diǎn),unorder_map內(nèi)部采用hash表,map內(nèi)部采用的是紅黑樹,內(nèi)存占有率的問(wèn)題轉(zhuǎn)化成hash表 VS 紅黑樹,還是unorder_map內(nèi)存要高一點(diǎn).

但是unorder_map采用哈希表搜索，搜尋效率高，利用鍵值與哈希函數(shù)(hash function)計(jì)算出哈希值而快速的查找到對(duì)應(yīng)的元素，時(shí)間復(fù)雜度為常數(shù)級(jí)別O(1)

在關(guān)鍵字類型的元素沒有明顯的序的情況下，或者在某些應(yīng)用中，維護(hù)元素有序的代價(jià)非常高昂，采用無(wú)序容器代替map來(lái)說(shuō)效果會(huì)好。

結(jié)語(yǔ)

這就是我對(duì)map、multimap、unordered_map、unordered_multimap幾者的分享，有機(jī)會(huì)可以給大家一起分享一下set, multiset 和 unordered_set, unordered_multiset的使用與區(qū)別。如果大家有更好的想法和需求，也歡迎大家加我好友交流分享哈。

作者：良知猶存，白天努力工作，晚上原創(chuàng)公號(hào)號(hào)主。公眾號(hào)內(nèi)容除了技術(shù)還有些人生感悟，一個(gè)認(rèn)真輸出內(nèi)容的職場(chǎng)老司機(jī)，也是一個(gè)技術(shù)之外豐富生活的人，攝影、音樂 and 籃球。關(guān)注我，與我一起同行。

                              ????????????????  END  ????????????????

推薦閱讀

【1】在球場(chǎng)上我向人民幣玩家低了頭

【2】Linux開發(fā)coredump文件分析實(shí)戰(zhàn)分享

【3】CPU中的程序是怎么運(yùn)行起來(lái)的 必讀

【4】cartographer環(huán)境建立以及建圖測(cè)試

【5】設(shè)計(jì)模式之簡(jiǎn)單工廠模式、工廠模式、抽象工廠模式的對(duì)比

本公眾號(hào)全部原創(chuàng)干貨已整理成一個(gè)目錄，回復(fù)[ 資源 ]即可獲得。