無序關聯容器 (STL)

C++程式語言中,unordered_mapunordered_multimapunordered_setunordered_multiset標準模板庫(STL)提供的一類無序關聯容器(unordered associative containers)。是通過哈希表實現的數據結構。無序是指元素的名字(或者鍵值)的存儲是無序的;這與用平衡二叉樹實現的元素名字是有序存儲的「關聯容器」是相對概念。

歷史

SGISTL提供了hash_map, hash_set, hash_multimap, hash_multiset等類模板。[1]由於其有用性,很快其它的C++編譯器也支持了這一特性,如GCClibstdc++[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;

參考文獻

  1. ^ hash_map<Key, Data, HashFcn, EqualKey, Alloc>. SGI. [26 January 2011]. (原始內容存檔於2017-12-30). 
  2. ^ libstdc++: hash_map Class Template Reference. [26 January 2011]. (原始內容存檔於2017-07-19). 
  3. ^ WG21. A Proposal to Add Hash Tables to the Standard Library (revision 4). 9 April 2003 [2015-12-21]. n1456. (原始內容存檔於2011-05-20). 
  4. ^ WG21, Working Draft, Standard for Programming Language C++ (PDF), 21 August 2010 [2015-12-21], n3126, (原始內容存檔 (PDF)於2010-09-26) 
  5. ^ Class template unordered_map. Boost. [26 January 2011]. (原始內容存檔於2017-10-11).