無序關聯容器 (STL)

C++程序設計語言中，`unordered_map`、`unordered_multimap`、`unordered_set`、`unordered_multiset`是標準模板庫（STL）提供的一類無序關聯容器（unordered associative containers）。是通過哈希表實現的數據結構。無序是指元素的名字（或者鍵值）的存儲是無序的；這與用平衡二叉樹實現的元素名字是有序存儲的「關聯容器」是相對概念。

## 歷史

SGI的STL提供了`hash_map`, `hash_set`, `hash_multimap`, `hash_multiset`等類模板。由於其有用性，很快其它的C++編譯器也支持了這一特性，如GCC、 libstdc++ 以及MSVC （在stdext命名空間）。

C++ TR1語言標準中提出了增加`hash_*`類模板，最終接受為`unordered_*`。Boost C++ Libraries也提供了一種實現。`<boost/unordered_map.hpp>`.

## 類成員函數

頭文件`<unordered_map>`中定義了類模板`unordered_map`。並滿足 容器 概念，這意味著它支持`begin()`、`end()`、`size()`、`max_size()`、`empty()`、 `swap()`等方法。

`unordered_set`(C++11)｜`unordered_map`(C++11)｜`unordered_multiset`(C++11)｜`unordered_multimap`(C++11)｜描述

(constructor)｜(constructor)｜(constructor)｜(constructor)｜構造函數包括預設構造、拷貝構造、移動構造等

(destructor)｜(destructor)｜(destructor)｜(destructor)｜析構函數

`[http://en.cppreference.com/w/cpp/container/unordered_set/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/operator= operator=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/operator= operator=]`｜賦值運算符

`[http://en.cppreference.com/w/cpp/container/unordered_set/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/get_allocator get_allocator]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/get_allocator get_allocator]`｜返回分配器，用於給容器元素分配記憶體

Element access｜不適用｜`[http://en.cppreference.com/w/cpp/container/unordered_map/at at]`｜不適用｜不適用｜帶邊界檢查的返回元素（C++11）

不適用｜operator`[]`｜不適用｜不適用｜不帶邊界檢查的返回元素，可用於插入元素

Iterators｜`[http://en.cppreference.com/w/cpp/container/unordered_set/begin begin,cbegin]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/begin begin,cbegin]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/begin begin,cbegin]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/begin begin,cbegin]`｜返回指向哈希表指定條目（bucket）所包含的首元素的迭代器 （C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/end end]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/end end]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/end end]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/end end]`｜指向容器末尾的迭代器

Capacity｜`[http://en.cppreference.com/w/cpp/container/unordered_set/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/empty empty]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/empty empty]`｜檢查容器是否為空

`[http://en.cppreference.com/w/cpp/container/unordered_set/size size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/size size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/size size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/size size]`｜返回容器元素的數量。

`[http://en.cppreference.com/w/cpp/container/unordered_set/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/max_size max_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/max_size max_size]`｜返回受系統與庫的實現所限，容器元素的最大可能數量

Modifiers｜`[http://en.cppreference.com/w/cpp/container/unordered_set/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/clear clear]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/clear clear]`｜清空容器

`[http://en.cppreference.com/w/cpp/container/unordered_set/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/insert insert]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/insert insert]`｜插入元素

`[http://en.cppreference.com/w/cpp/container/unordered_set/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/emplace emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/emplace emplace]`｜原位構造 (C++11)

`[http://en.cppreference.com/w/cpp/container/unordered_set/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/emplace_hint emplace_hint]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/emplace_hint emplace_hint]`｜使用hint原位構造 (C++11)

`[http://en.cppreference.com/w/cpp/container/unordered_set/try_emplace try_emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/try_emplace try_emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/try_emplace try_emplace]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/try_emplace try_emplace]`｜如果給定的key在容器中不存在，原位構造一個元素 (C++17)

`[http://en.cppreference.com/w/cpp/container/unordered_set/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/erase erase]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/erase erase]`｜擦除元素

`[http://en.cppreference.com/w/cpp/container/unordered_set/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/swap swap]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/swap swap]`｜兩個容器交換內容

Lookup｜`[http://en.cppreference.com/w/cpp/container/unordered_set/count count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/count count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/count count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/count count]`｜返回匹配指定鍵值的元素數量

`[http://en.cppreference.com/w/cpp/container/unordered_set/find find]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/find find]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/find find]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/find find]`｜發現具有指定鍵值的元素

`[http://en.cppreference.com/w/cpp/container/unordered_set/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/equal_range equal_range]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/equal_range equal_range]`｜返回匹配指定鍵值的元素範圍

`[http://en.cppreference.com/w/cpp/container/unordered_set/reserve reserve]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/reserve reserve]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/reserve reserve]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/reserve reserve]`｜擴展容器的容量（C++11）

Bucket接口｜`[http://en.cppreference.com/w/cpp/container/unordered_set/bucket_size bucket_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/bucket_size bucket_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/bucket_size bucket_size]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/bucket_size bucket_size]`｜返回指定索引的哈希表條目所容納的容器元素的數量（C++11）

哈希策略

`[http://en.cppreference.com/w/cpp/container/unordered_set/hash_function hash_function]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/hash_function hash_function]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/hash_function hash_function]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/hash_function hash_function]`｜返回用於創製鍵值hash的函數對象

`[http://en.cppreference.com/w/cpp/container/unordered_set/key_eq key_eq]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/key_eq key_eq]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/key_eq key_eq]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/key_eq key_eq]`｜返回鍵值比較函數對象（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/rehash rehash]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/rehash rehash]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/rehash rehash]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/rehash rehash]`｜設定哈希表的條目（bucket）數量並重新生成哈希表（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/max_load_factor max_load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/max_load_factor max_load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/max_load_factor max_load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/max_load_factor max_load_factor]`｜返回或者設置哈希表的每個條目能容納的容器元素的最大數量（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/load_factor load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/load_factor load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/load_factor load_factor]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/load_factor load_factor]`｜返回哈希表的每個條目容納的容器元素的平均數量（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/max_bucket_count max_bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/max_bucket_count max_bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/max_bucket_count max_bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/max_bucket_count max_bucket_count]`｜返回由於系統及庫的實現所能支持的哈希表條目的最大可能數量（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/bucket_count bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/bucket_count bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/bucket_count bucket_count]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/bucket_count bucket_count]`｜返回容器中的哈希表條目的數量（C++11）

`[http://en.cppreference.com/w/cpp/container/unordered_set/bucket bucket]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/bucket bucket]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/bucket bucket]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/bucket bucket]`｜返回指定鍵值所匹配的哈希表條目的索引（C++11）

Observers｜`[http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp operator==,!=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_map/operator_cmp operator==,!=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multiset/operator_cmp operator==,!=]`｜`[http://en.cppreference.com/w/cpp/container/unordered_multimap/operator_cmp operator==,!=]`｜兩個容器的內容是否相同

## 例子

```cpp
#include <iostream>
#include <string>
#include <unordered_map>

int main()
{
    std::unordered_map<std::string, int> months;
    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;
    std::cout << "september -> " << months["september"] << std::endl;
    std::cout << "april     -> " << months["april"] << std::endl;
    std::cout << "december  -> " << months["december"] << std::endl;
    std::cout << "february  -> " << months["february"] << std::endl;

    //判断map中是否包含一个键值，没有直接做此事的成员函数。类似其他的STL容器，解决办法是：
    if( months.find("no_value") == months.end() )
    {
          printf("No such key in the map.");
    }
    return 0;
}
```

## 定製哈希函數

定製的哈希函數的參數為到定製類型的const引用，返回類型為size_t

```cpp
struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};
```

定製哈希函數作為std::unordered_map的模板參數使用。

```cpp
 std::unordered_map<X,int,hash_X> my_map;
```

或者通過特化std::hash來使用。

```cpp
namespace std {
    template <>
        class hash<X>{
        public :
        size_t operator()(const X &x ) const{
            return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
        }
    };
}

//...
 std::unordered_map<X,int> my_map;
```