unordered_map?類模板和?map?類模板都是描述了這么一個對象：它是由?std::pair<const Key, value>?組成的可變長容器；

這個容器中每個元素存儲兩個對象，也就是?key?-?value?對。

1.?unordered_map?

在頭文件上，引入?<unordered_map>?來使用它。對于?unordered_map?而言，最大的特點(diǎn)在于內(nèi)部實現(xiàn)上，使用到了「哈希表」（散列表、hash_table?）來進(jìn)行映射存儲，它的模板類聲明及其參數(shù)如下：

/*** 程序來自STL源碼 bits/unordered_map.h*/
template<typename _Key,  // key 類型 typename _Tp,    // value 類型typename _Hash = hash <_Key>,     // 哈希函數(shù)typename _Pred = equal_to <_Key>, // 用于比較兩者是否相同的函數(shù)typename _Alloc = allocator <std::pair<const _Key, _Tp>>> // 分配器，描述了容器在內(nèi)存管理上的細(xì)節(jié)，不應(yīng)該自己來處理，除非寫自己的容器
class unordered_map {
};

在?unordered_map?內(nèi)部，使用的?Hash Table?對數(shù)據(jù)進(jìn)行組織，通過把鍵值?key?映射到?hash?表中的一個位置進(jìn)行訪問，根據(jù)?hash?函數(shù)的特點(diǎn)，?unordered_map?對于元素查找的時間復(fù)雜度可以達(dá)到?O(1)?，但是，它的元素排列是無序的。具體例子如下：?

int main() {using namespace std;// 首先創(chuàng)建一個無序 map，它的 key 使用 int 類型，value 使用 string 類型unordered_map<int, string> unorderedMap;    // 三種插入新元素的方法，“茴”字有三種寫法~unorderedMap.insert(make_pair(0, "Alice")); unorderedMap[1] = "Bob";unorderedMap.insert(unordered_map<int, string>::value_type(2, "Candy"));// 對內(nèi)部元素挨個輸出for (auto iter = unorderedMap.begin(); iter != unorderedMap.end(); iter++) {cout << iter->first << " - " << iter->second << endl;/** >: 輸出如下，可以得知它們在 key 的排序上并沒有順序* 2 - Candy* 0 - Alice* 1 - Bob*/}
}

unordered_map?由于建立了哈希表，所以它在最開始建立的時候比較耗時間，但是它查詢速度快呀~，一般情況下用?unordered_map?是沒有問題的。?

2.?map?

對于?map?而言，首先在頭文件上，引用?<map>?進(jìn)來，然后使用。它的類模板聲明以及部分函數(shù)聲明如下：

/*** 程序來自C++源碼 bits/stl_map.h*/
template<typename _Key,  // key 類型typename _Tp,    // value 類型typename _Compare = std::less<_Key>, // 用于比較兩個元素的比較函數(shù)typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > // 分配器，同樣的描述了容器在內(nèi)存管理上的細(xì)節(jié)，不應(yīng)該自己來處理，除非寫自己的容器
class map {
private:/// 將一個紅黑樹轉(zhuǎn)換成 [multi]map.typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<value_type>::other _Pair_alloc_type;typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,key_compare, _Pair_alloc_type> _Rep_type;
};

在?map?的內(nèi)部，使用了「紅黑樹」（red-black tree）來組織數(shù)據(jù)，因此默認(rèn)的就已經(jīng)實現(xiàn)了數(shù)據(jù)的排序。從下面例子中可以看出，它默認(rèn)實現(xiàn)了在?key?上排序?qū)崿F(xiàn)遞增：?

int main() {map<int, string> mapper;mapper.insert(make_pair(0, "Alice"));mapper[1] = "Bob";mapper.insert(map<int, string>::value_type(2, "Candy"));for (auto &iter : mapper) {cout << iter.first << " - " << iter.second << endl;/** >: 輸出如下，很明顯的，它們在 key 的排序上是遞增排列的* 0 - Alice* 1 - Bob* 2 - Candy*/}
}

不過，在存儲上?map?卻比較占用空間，因為在紅黑樹中，每一個節(jié)點(diǎn)都要額外保存父節(jié)點(diǎn)和子節(jié)點(diǎn)的連接，因此使得每一個節(jié)點(diǎn)都占用較大空間來維護(hù)紅黑樹性質(zhì)。?

3. 總結(jié)?

?兩種數(shù)據(jù)結(jié)構(gòu)特點(diǎn)如下表格~