無序關聯容器 (STL)

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

歷史

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

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

類成員函數

頭文件<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) （頁面存檔備份，存於網際網路檔案館）	析構函數
	operator=	operator=	operator=	operator=	賦值運算符
	get_allocator	get_allocator	get_allocator	get_allocator	返回分配器，用於給容器元素分配內存
Element access	不適用	at	不適用	不適用	帶邊界檢查的返回元素（C++11）
	不適用	operator[]	不適用	不適用	不帶邊界檢查的返回元素，可用於插入元素
Iterators	begin,cbegin	begin,cbegin	begin,cbegin	begin,cbegin	返回指向哈希表指定條目（bucket）所包含的首元素的迭代器 （C++11）
	end	end	end	end	指向容器末尾的迭代器
Capacity	empty	empty	empty	empty	檢查容器是否為空
	size	size	size	size	返回容器元素的數量。
	max_size	max_size	max_size	max_size	返回受系統與庫的實現所限，容器元素的最大可能數量
Modifiers	clear	clear	clear	clear	清空容器
	insert	insert	insert	insert	插入元素
	emplace	emplace	emplace	emplace	原位構造 (C++11)
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	使用hint原位構造 (C++11)
	try_emplace	try_emplace	try_emplace	try_emplace	如果給定的key在容器中不存在，原位構造一個元素 (C++17)
	erase	erase	erase	erase	擦除元素
	swap	swap	swap	swap	兩個容器交換內容
Lookup	count	count	count	count	返回匹配指定鍵值的元素數量
	find	find	find	find	發現具有指定鍵值的元素
	equal_range	equal_range	equal_range	equal_range	返回匹配指定鍵值的元素範圍
	reserve	reserve	reserve	reserve	擴展容器的容量（C++11）
Bucket接口	bucket_size	bucket_size	bucket_size	bucket_size	返回指定索引的哈希表條目所容納的容器元素的數量（C++11）
哈希策略
	hash_function	hash_function	hash_function	hash_function	返回用於創製鍵值hash的函數對象
	key_eq	key_eq	key_eq	key_eq	返回鍵值比較函數對象（C++11）
	rehash	rehash	rehash	rehash	設定哈希表的條目（bucket）數量並重新生成哈希表（C++11）
	max_load_factor	max_load_factor	max_load_factor	max_load_factor	返回或者設置哈希表的每個條目能容納的容器元素的最大數量（C++11）
	load_factor	load_factor	load_factor	load_factor	返回哈希表的每個條目容納的容器元素的平均數量（C++11）
	max_bucket_count	max_bucket_count	max_bucket_count	max_bucket_count	返回由於系統及庫的實現所能支持的哈希表條目的最大可能數量（C++11）
	bucket_count	bucket_count	bucket_count	bucket_count	返回容器中的哈希表條目的數量（C++11）
	bucket	bucket	bucket	bucket	返回指定鍵值所匹配的哈希表條目的索引（C++11）
Observers	operator==,!=	operator==,!=	operator==,!=	operator==,!=	兩個容器的內容是否相同

例子

#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

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的模板參數使用。

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

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

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;