C++中的unordered_map和map差別1. unordered_map 2. map

1.

unordered_map

在頭檔案上，引入

<unordered_map>

來使用它。對于

unordered_map

而言，最大的特點在于内部實作上，使用到了哈希表（散清單、

hash_table

）來進行映射存儲，它的模闆類聲明及其參數如下：

/**
 * 程式來自STL源碼 bits/unordered_map.h
 */
template<typename _Key,  // key 類型 
        typename _Tp,    // value 類型
        typename _Hash = hash <_Key>,     // 哈希函數
        typename _Pred = equal_to <_Key>, // 用于比較兩者是否相同的函數
        typename _Alloc = allocator <std::pair<const _Key, _Tp>>> // 配置設定器，描述了容器在記憶體管理上的細節，不應該自己來處理，除非寫自己的容器
class unordered_map {
};           

在

unordered_map

内部，使用的

Hash Table

對資料進行組織，通過把鍵值

key

映射到

hash

表中的一個位置進行通路，根據

hash

函數的特點，

unordered_map

對于元素查找的時間複雜度可以達到

O(1)

，但是，它的元素排列是無序的。具體例子如下：

int main() {
    using namespace std;
    // 首先建立一個無序 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"));
 
    // 對内部元素挨個輸出
    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>

進來，然後使用。它的類模闆聲明以及部分函數聲明如下：

/**
 * 程式來自C++源碼 bits/stl_map.h
 */
template<typename _Key,  // key 類型
        typename _Tp,    // value 類型
        typename _Compare = std::less<_Key>, // 用于比較兩個元素的比較函數
        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > // 配置設定器，同樣的描述了容器在記憶體管理上的細節，不應該自己來處理，除非寫自己的容器
class map {
private:
    /// 将一個紅黑樹轉換成 [multi]map.
    typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
    rebind<value_type>::other _Pair_alloc_type;

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
    key_compare, _Pair_alloc_type> _Rep_type;
};           

map

的内部，使用了紅黑樹（

red-black tree

）來組織資料，是以預設的就已經實作了資料的排序。從下面例子中可以看出，它預設實作了在

key

上排序實作遞增：

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

卻比較占用空間，因為在紅黑樹中，每一個節點都要額外儲存父節點和子節點的連接配接，是以使得每一個節點都占用較大空間來維護紅黑樹性質。

3. 總結

兩種資料結構特點如下表格~

unordered_map	map
查找	快，Average： O(1) ，Worst Case： O(n)	恒定的 log(n)
插入	和上面一樣	log(n) + 平衡二叉樹所用時間
删除	還和上面一樣	log(n)
是否排序	不排序	排序
實作方法	哈希表	紅黑樹
适用于	查找操作頻率高	要求結果有序（按 key 排序）