无序关联容器

科技工作者之家 2020-11-17

C++程序设计语言中,unordered_mapunordered_multimapunordered_setunordered_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也提供了一种实现。1

定制哈希函数定制的哈希函数的参数为到定制类型的const引用,返回类型为size_t1。

struct X{int i,j,k;};struct hash_X{ size_t operator()(const X &x) const{ return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k); }};定制哈希函数作为std::unordered_map的模板参数使用。

std::unordered_map my_map;或者通过特化std::hash来使用。

namespace std { template class hash{ public : size_t operator()(const X &x ) const{ return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k); } };}//... std::unordered_map my_map;标准模板库标准模板库(英文:Standard Template Library,缩写:STL),是一个C++软件库,大量影响了C++标准程序库但并非是其的一部分。其中包含4个组件,分别为算法、容器、函数、迭代器。

模板是C++程序设计语言中的一个重要特征,而标准模板库正是基于此特征。标准模板库使得C++编程语言在有了同Java一样强大的类库的同时,保有了更大的可扩展性。1

散列表散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名{\displaystyle x}到首字母{\displaystyle F(x)}的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则{\displaystyle F()},存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。2

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学

科技工作者之家

科技工作者之家APP是专注科技人才,知识分享与人才交流的服务平台。