c++中map、multimap、unordered_map/multimap的區(qū)別

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

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

歡迎關(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í)作方式通常是用紅黑樹(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?<iostream>
#include?<map>
using?namespace?std;
int?main()
{
????std::map<int,?std::string>?studentMap?=?{
????{1,?"Tom"},
????{7,?"Mali"},
????{15,?"John"}};

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


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

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

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

multimap簡(jiǎn)介

multimaps是關(guān)聯(lián)式容器，它按照特定的順序，存儲(chǔ)由key和value映射成的鍵值對(duì)<key, value>，其中多個(gè)鍵值對(duì)之間的key是可以重復(fù)的，multimap在底層用二叉搜索樹(shù)(紅黑樹(shù))來(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?<iostream>
#include?<map>
using?namespace?std;
int?main()
{
????std::multimap<string,?std::string>?studentMap2?=?{
????{"first",?"Tom"},
????{"second",?"Mali"},
????{"third",?"John"}};????


????studentMap2.insert(std::pair<std::string,?std::string>("first",?"Bob"));??
????
????cout<<?"output:"<<endl;??
????for?(std::multimap<std::string,?std::string>::iterator?it?=?studentMap2.begin();?it?!=?studentMap2.end();?it++)?{
????????std::cout?<<?(*it).first?<<?",?"?<<?(*it).second?<<?"n";
????}
????std::cout?<<?studentMap2.count("first")?<<std::endl;?//?輸出為2

}

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

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

注意：multimap中沒(méi)有重載operator[]操作。

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

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?<iostream>
#include?<unordered_map>
using?namespace?std;
int?main()
{
???std::unordered_map?<?std::string?,?int?>?studentUMap3?=?{?
????????{?"Tom"?,?1?},?
????????{?"Ann"?,?4?},?
????????{?"Job"?,?2?}?
????};

???studentUMap3.insert(std::pair<std::string,?int>("Job",?5));??
????

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

????cout<<endl;?????
????studentUMap3["Job"]?=?3;
????for?(auto?it?=?studentUMap3.begin();?it?!=?studentUMap3.end();?it++)?{
????????std::cout?<<?(*it).first?<<?",?"?<<?(*it).second?<<?"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?<iostream>
#include?<unordered_map>
using?namespace?std;
int?main()
{
???std::unordered_multimap?<?int?,?int?>?studentUMap4;
????studentUMap4.insert(std::pair<int,?int>(1,?333));
????studentUMap4.insert(std::pair<int,?int>(3,?555));
????studentUMap4.insert(std::pair<int,?int>(5,?666));


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

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

????std::cout?<<"count:"<<?studentUMap4.count(5)?<<std::endl;
????std::cout?<<"size:?"<<?studentUMap4.size()?<<std::endl;
????std::cout?<<"empty?"<<?studentUMap4.empty()<<"n"?<<std::endl;


????std::unordered_multimap?<?int?,?int?>studentUMap5;
????studentUMap5.swap(studentUMap4);
????std::cout?<<"count:"<<?studentUMap4.count(5)?<<std::endl;
????std::cout?<<"size:?"<<?studentUMap4.size()?<<std::endl;
????std::cout?<<"empty?"<<?studentUMap4.empty()<<"n"?<<std::endl;


????std::cout?<<"count:"?<<studentUMap5.count(5)<<"n"?<<std::endl;


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

重復(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ù)實(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)容器沒(méi)有意義。

關(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è)紅黑樹(shù)（紅黑樹(shù)是非嚴(yán)格平衡二叉搜索樹(shù)，而AVL是嚴(yán)格平衡二叉搜索樹(shù)），紅黑樹(shù)具有自動(dòng)排序的功能，因此map內(nèi)部的所有元素都是有序的，紅黑樹(shù)的每一個(gè)節(jié)點(diǎn)都代表著map的一個(gè)元素。因此，對(duì)于map進(jìn)行的查找、刪除，添加等一系列的操作都相當(dāng)于是對(duì)紅黑樹(shù)進(jìn)行的操作。map中的元素是按照二叉搜索樹(shù) （又名兒茶查找樹(shù)、二叉排序樹(shù)–特點(diǎn)就是左子樹(shù)上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹(shù)所有節(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)部采用的是紅黑樹(shù),內(nèi)存占有率的問(wèn)題轉(zhuǎn)化成hash表 VS 紅黑樹(shù),還是unorder_map內(nèi)存要高一點(diǎn).

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

在關(guān)鍵字類型的元素沒(méi)有明顯的序的情況下，或者在某些應(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ù)之外豐富生活的人，攝影、音樂(lè) and 籃球。關(guān)注我，與我一起同行。