一、map和unordered_map的區(qū)別

（1）需要引入的頭文件不同

map: #include <map>
unordered_map: #include <unordered_map>

（2）內(nèi)部實(shí)現(xiàn)機(jī)理不同

<1>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)行的操作，其時(shí)間復(fù)雜度都是O(logn)，最壞和平均都是。map中的元素是按照二叉搜索樹（又名二叉查找樹、二叉排序樹，特點(diǎn)就是左子樹上所有節(jié)點(diǎn)的鍵值都小于根節(jié)點(diǎn)的鍵值，右子樹所有節(jié)點(diǎn)的鍵值都大于根節(jié)點(diǎn)的鍵值）存儲(chǔ)的，使用中序遍歷可將鍵值按照從小到大遍歷出來。

<2>unordered_map

unordered_map內(nèi)部實(shí)現(xiàn)了一個(gè)哈希表（也叫散列表，通過把關(guān)鍵碼值映射到Hash表中一個(gè)位置來訪問記錄，查找的時(shí)間復(fù)雜度可達(dá)到O(1)，其在海量數(shù)據(jù)處理中有著廣泛應(yīng)用）。因此，其元素的排列順序是無序的。但是并不是unordered_map查詢時(shí)間一定比map短，因?yàn)閷?shí)際情況中還要考慮到數(shù)據(jù)量，而且unordered_map的hash函數(shù)的構(gòu)造速度也沒那么快，所以不能一概而論，應(yīng)該具體情況具體分析。

hash_map和unordered_map的底層實(shí)現(xiàn)是一樣的，但是在C++11中將unordered_map引入了標(biāo)準(zhǔn)庫(kù)，而hash_map沒有，所以建議還是使用unordered_map比較好。
unordered_set就是在哈希表插入value，而這個(gè)value就是它自己的key。

（3）優(yōu)缺點(diǎn)

<1>map

• 優(yōu)點(diǎn)
  （1）有序性，這是map結(jié)構(gòu)最大的優(yōu)點(diǎn)，其元素的有序性在很多應(yīng)用中都會(huì)簡(jiǎn)化很多的操作；
  （2）紅黑樹，內(nèi)部實(shí)現(xiàn)一個(gè)紅黑書使得map的很多操作在logn的時(shí)間復(fù)雜度下就可以實(shí)現(xiàn)，因此效率非常的高
• 缺點(diǎn)
  空間占用率高，因?yàn)閙ap內(nèi)部實(shí)現(xiàn)了紅黑樹，雖然提高了運(yùn)行效率，但是因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都需要額外保存父節(jié)點(diǎn)、孩子節(jié)點(diǎn)和紅/黑性質(zhì)，使得每一個(gè)節(jié)點(diǎn)都占用大量的空間。

<2>unordered_map

• 優(yōu)點(diǎn)
  因?yàn)閮?nèi)部實(shí)現(xiàn)了哈希表，因此其查找速度非常的快。
• 缺點(diǎn)
  哈希表的建立比較耗費(fèi)時(shí)間。

（4）適用性

<1>map

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

<2>unordered_map

對(duì)于查找問題，unordered_map會(huì)更加高效一些，因此遇到查找問題，常會(huì)考慮一下用unordered_map。
對(duì)于unordered_map或unordered_set容器，其遍歷順序與創(chuàng)建該容器時(shí)輸入的順序不一定相同，因?yàn)楸闅v是按照哈希表從前往后依次遍歷的。

（5）使用

unordered_map的用法和map完全是一樣的，提供了 insert，size，count，find等操作，并且里面的元素也是以pair類型來存貯的。其底層實(shí)現(xiàn)是完全不同的，上方已經(jīng)解釋了，但是就外部使用來說卻是一致的

二、map和multimap的區(qū)別

multimap容器保存的是有序的鍵/值對(duì)，但是可以保存重復(fù)的元素。multimap中會(huì)出現(xiàn)具有相同鍵值的元素序列。multimap大部分成員函數(shù)的使用方式和map相同。因?yàn)橹貜?fù)鍵的原因，multimap有一些函數(shù)的使用方式和map有一些區(qū)別。

<1>訪問元素

multimap不支持下標(biāo)運(yùn)算符，因?yàn)殒I并不能確定一個(gè)唯一元素。和 map 相似，multimap 也不能使用 at() 函數(shù)。

<2>刪除元素

• 以待刪除元素的迭代器作為參數(shù)，這個(gè)函數(shù)沒有返回值；
• erase()函數(shù)以一個(gè)鍵作為參數(shù)，它會(huì)刪除容器中所有含這個(gè)鍵的元素，返回容器中被移除元素的個(gè)數(shù)
• 接受兩個(gè)迭代器參數(shù)，這個(gè)范圍內(nèi)的所有元素都會(huì)被刪除。

<3>count函數(shù)

multimap 的成員函數(shù) count() 可以知道有多少個(gè)元素的鍵和給定的鍵相同。

三、unordered_multimap

在該數(shù)據(jù)結(jié)構(gòu)里面的元素沒有順序，并且可以有多個(gè)key值相同。