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

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

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

歡迎關(guān)注微信公眾號：羽林君，或者添加作者個人微信：become_me

幾種容器的初步介紹:

map簡介

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

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

常用函數(shù)

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

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

map.first：第一個稱為(key)鍵值
map.second：第二個稱為(key)鍵值對應(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簡介

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

在內(nèi)部，multimap中的元素總是通過其內(nèi)部比較對象，按照指定的特定嚴(yán)格弱排序標(biāo)準(zhǔn)對key進行排序的。和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

}

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

沖突的元素會使用元素鏈接的方式保存。

注意：multimap中沒有重載operator[]操作。

所以我們無法使用 multimap[key]進行訪問數(shù)據(jù)，是因為multimap的key可以對應(yīng)多個數(shù)據(jù)，所以下標(biāo)訪問是沒有意義的。

unordered_map簡介

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

unordered_map 特點就是搜尋效率高，利用鍵值與哈希函數(shù)(hash function)計算出哈希值而快速的查找到對應(yīng)的元素，時間復(fù)雜度為常數(shù)級別O(1)， 而額外空間復(fù)雜度則要高出許多。unordered_map 與map 的使用方法基本上一樣，都是key/value 之間的映射，只是他們內(nèi)部采用的資料結(jié)構(gòu)不一樣。所以對于需要高效率查詢的情況可以使用unordered_map 容器。而如果對記憶體消耗比較敏感或者資料存放要求排序的話則可以用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基本一致，但是考慮的訪問的速度有要求的情況下，我們優(yōu)先使用，unordered_map;要是考慮到空間大小對程序影響的時候，我們優(yōu)先使用map。

unordered_multimap簡介

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

同map和unordered_map區(qū)別一樣，multimap通過key訪問單個元素的速度通常也比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ù)元素對應(yīng)的debug顯示

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

區(qū)別介紹

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

來自wiki

關(guān)聯(lián)容器是指C++標(biāo)準(zhǔn)模板庫中的一套類模板，實現(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++中的無序關(guān)聯(lián)容器。差別為：

• 關(guān)聯(lián)容器是紅黑樹實現(xiàn)，無序關(guān)聯(lián)容器是哈希表實現(xiàn)。

• 關(guān)聯(lián)容器保證按鍵值有序遍歷，因此可以做范圍查找，而無序關(guān)聯(lián)容器不可以。

• 關(guān)聯(lián)支持一些導(dǎo)航類的>>操作，如求出給定鍵最鄰近的鍵，最大鍵、最小鍵操作。

• 關(guān)聯(lián)容器的迭代器不會失效，除非所指元素被刪除。無序關(guān)聯(lián)容器的iterator在修改元素時可能會失>>效。所以對關(guān)聯(lián)容器的遍歷與修改在一定程度上可并行

哈希表查找時候要算hash，這個最壞時間復(fù)雜度是O(key的長度)；基于比較的有序關(guān)聯(lián)容器通常只使用>頭幾個字符進行比較

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

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

因為map和multimap unordered_map和unordered_multimap兩兩區(qū)分時候，從底層實現(xiàn)來說，區(qū)別不是很大，所以我們先進行map與multimap的區(qū)別，再進行map和unordered_map區(qū)別比較。其他的類比即可。

最直觀的區(qū)別：

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

實現(xiàn)機制的區(qū)別：

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

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

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

使用的角度

空間占用率和效率上

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

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

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

結(jié)語

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

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