無序關聯容器

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

基本介紹

• 中文名：無序關聯容器
• 外文名：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也提供了一種實現。

定製哈希函式

定製的哈希函式的參數為到定製類型的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;

標準模板庫

標準模板庫（英文：Standard Template Library，縮寫：STL），是一個C++軟體庫，大量影響了C++標準程式庫但並非是其的一部分。其中包含4個組件，分別為算法、容器、函式、疊代器。

模板是C++程式設計語言中的一個重要特徵，而標準模板庫正是基於此特徵。標準模板庫使得C++程式語言在有了同Java一樣強大的類庫的同時，保有了更大的可擴展性。

散列表

散列表（Hash table，也叫哈希表），是根據鍵（Key）而直接訪問在記憶體存儲位置的數據結構。也就是說，它通過計算一個關於鍵值的函式，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函式稱做散列函式，存放記錄的數組稱做散列表。

一個通俗的例子是，為了查找電話簿中某人的號碼，可以創建一個按照人名首字母順序排列的表（即建立人名{\displaystyle x}到首字母{\displaystyle F(x)}的一個函式關係），在首字母為W的表中查找“王”姓的電話號碼，顯然比直接查找就要快得多。這裡使用人名作為關鍵字，“取首字母”是這個例子中散列函式的函式法則{\displaystyle F()}，存放首字母的表對應散列表。關鍵字和函式法則理論上可以任意確定。