map和unordered_map的使用

unordered_map的用法和map是一樣的，提供了insert，size，count，find等操作，并且里面的元素也是以pair類型來(lái)存貯的。

其底層實(shí)現(xiàn)是完全不同的，上方已經(jīng)解釋了，但是就外部使用來(lái)說(shuō)卻是一致的。

C++ Map常見(jiàn)用法說(shuō)明

---

map

包含在頭文件#include < map >中。

map是STL的一個(gè)關(guān)聯(lián)容器，它提供一對(duì)一（第一個(gè)為key，每個(gè)key只能在map中出現(xiàn)一次，第二個(gè)為value）的數(shù)據(jù)處理能力。map內(nèi)部自建一顆紅黑樹(shù)（一種非嚴(yán)格意義上的平衡二叉樹(shù)），所以在map內(nèi)部所有的數(shù)據(jù)都是有序的，且map的查詢、插入、刪除操作的時(shí)間復(fù)雜度都是O(logN)。在使用時(shí)，map的key需要定義operator<。

map中的元素是按照二叉搜索樹(shù)（又名二叉查找樹(shù)或者二叉排序樹(shù)，特點(diǎn)就是左子樹(shù)上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹(shù)所有節(jié)點(diǎn)的鍵值都大于根節(jié)點(diǎn)的鍵值）存儲(chǔ)的，使用中序遍歷可將鍵值按照從小到大遍歷出來(lái)。

---

unordered_map

包含在頭文件unordered_map: #include < unordered_map >中。

unordered_map和map類似，都是存儲(chǔ)的key-value的值，可以通過(guò)key快速索引到value。不同的是unordered_map不會(huì)根據(jù)key的大小進(jìn)行排序，存儲(chǔ)時(shí)是根據(jù)key的hash值判斷元素是否相同，即unordered_map內(nèi)部元素是無(wú)序的。unordered_map的key需要定義hash_value函數(shù)并且重載operator==。

unordered_map的底層是一個(gè)防冗余的哈希表（采用除留余數(shù)法）。哈希表最大的優(yōu)點(diǎn)，就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低，時(shí)間復(fù)雜度為O(1)；而代價(jià)僅僅是消耗比較多的內(nèi)存。

基本原理是使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素。可以設(shè)計(jì)一個(gè)哈希函數(shù)（hash函數(shù)，也叫做散列函數(shù)），使得每個(gè)元素的key都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)，hash值）相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照key為每一個(gè)元素“分類”，然后將這個(gè)元素存儲(chǔ)在相應(yīng)“類”所對(duì)應(yīng)的地方，稱為桶。

但是，不能夠保證每個(gè)元素的key與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了“沖突”，換句話說(shuō)，就是把不同的元素分在了相同的“類”之中?？偟膩?lái)說(shuō)，“直接定址”與“解決沖突”是哈希表的兩大特點(diǎn)。一般可采用拉鏈法解決沖突。

無(wú)序容器的性能依賴于hash函數(shù)的質(zhì)量和桶的數(shù)量和大小。

---

舉例說(shuō)明map的有序性和unordered_map的無(wú)序性

#include <iostream> #include <unordered_map> #include <map> #include <string> using namespace std; int main() { //注意：VS2012及以下版本不支持{}賦值unordered_map<int, string> myMap={{ 5, "張大" },{ 6, "李五" }};//使用{}賦值myMap[2] = "李四"; //使用[ ]進(jìn)行單個(gè)插入，若已存在鍵值2，則賦值修改，若無(wú)則插入。myMap.insert(pair<int, string>(3, "陳二"));//使用insert和pair插入//記住pair類型，可以通過(guò)使用make_pair來(lái)生成pair對(duì)象。//遍歷輸出+迭代器的使用auto iter = myMap.begin();//auto自動(dòng)識(shí)別為迭代器類型unordered_map<int,string>::iteratorwhile (iter!= myMap.end()){ cout << iter->first << "," << iter->second << endl; ++iter; } //查找元素并輸出+迭代器的使用auto iterator = myMap.find(2);//find()返回一個(gè)指向2的迭代器if (iterator != myMap.end())cout << endl<< iterator->first << "," << iterator->second << endl; system("pause"); return 0; }

此時(shí)用的是unordered_map，輸出的結(jié)果為：

若把unordered_map換成map，輸出的結(jié)果為：

---

優(yōu)缺點(diǎn)以及適用處

map：

優(yōu)點(diǎn)：

有序性，這是map結(jié)構(gòu)最大的優(yōu)點(diǎn)，其元素的有序性在很多應(yīng)用中都會(huì)簡(jiǎn)化很多的操作

紅黑樹(shù)，內(nèi)部實(shí)現(xiàn)一個(gè)紅黑書(shū)使得map的很多操作在lgn的時(shí)間復(fù)雜度下就可以實(shí)現(xiàn)，因此效率非常的高

缺點(diǎn)： 空間占用率高，因?yàn)閙ap內(nèi)部實(shí)現(xiàn)了紅黑樹(shù)，雖然提高了運(yùn)行效率，但是因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都需要額外保存父節(jié)點(diǎn)、孩子節(jié)點(diǎn)和紅/黑性質(zhì)，使得每一個(gè)節(jié)點(diǎn)都占用大量的空間

適用處：對(duì)于那些有順序要求的問(wèn)題，用map會(huì)更高效一些

unordered_map：

優(yōu)點(diǎn)： 因?yàn)閮?nèi)部實(shí)現(xiàn)了哈希表，因此其查找速度非常的快

缺點(diǎn)： 哈希表的建立比較耗費(fèi)時(shí)間

適用處：對(duì)于查找問(wèn)題，unordered_map會(huì)更加高效一些，因此遇到查找問(wèn)題，常會(huì)考慮一下用unordered_map

總結(jié)：
1. 內(nèi)存占有率的問(wèn)題就轉(zhuǎn)化成紅黑樹(shù) VS hash表 , 還是unorder_map占用的內(nèi)存要高。
2. 但是unordered_map執(zhí)行效率要比map高很多
3. 對(duì)于unordered_map或unordered_set容器，其遍歷順序與創(chuàng)建該容器時(shí)輸入的順序不一定相同，因?yàn)楸闅v是按照哈希表從前往后依次遍歷的

---

set和unordered_set的使用方法類似于map和unordered_map，詳情請(qǐng)見(jiàn)：
【總結(jié)】unordered_map,unordered_set,map和set的用法和區(qū)別

總結(jié)

以上是生活随笔為你收集整理的STL系列：map和unordered_map的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。