无序关联容器 (STL) - 维基百科，自由的百科全书

C++標準庫

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;

参考文献

[编辑]
  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）. 
检索自“https://zh.wikipedia.org/w/index.php?title=无序关联容器_(STL)&oldid=69235571”