无序关联容器 (STL)

时间:2020-04-04 01:34:08

C++标准库
容器
  • array
  • bitset
  • deque
  • forward_list
  • list
  • map
  • multimap
  • multiset
  • queue
  • set
  • stack
  • unordered_map
  • unordered_multimap
  • unordered_set
  • unordered_multiset
  • vector
输入/输出流
  • fstream
  • iomanip
  • ios
  • iosfwd
  • iostream
  • istream
  • ostream
  • sstream
  • streambuf
字符串及字符处理
  • charconv
  • codecvt
  • regex
  • string
  • string_view
工具
  • algorithm
  • any
  • chrono
  • execution
  • filesystem<>
  • functional
  • initializer_list
  • iterator
  • locale
  • optional
  • system_error
  • |tuple
  • type_index
  • typeinfo
  • type_traits
  • utility
  • valarray
  • variant
多线程与并发
  • atomic
  • condition_variable
  • future
  • mutex
  • shared_mutex
  • thread
数值
  • complex
  • limits
  • numeric
  • random
  • ratio
C++异常处理
  • exception
  • stdexcept
内存
  • new
  • memory
  • memory_resource
  • scoped_allocator
C标准函式库
  • cassert
  • ccomplex
  • cctype
  • cerrno
  • cfenv
  • cfloat
  • cinttypes
  • ciso646
  • climits
  • clocale
  • cmath
  • csetjmp
  • csignal
  • cstdalign
  • cstdarg
  • cstdbool
  • cstddef
  • cstdint
  • cstdio
  • cstdlib
  • cstring
  • ctime
  • ctgmath
  • cuchar
  • cwchar
  • cwctype

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也提供了一种实现。.

类成员函数

头文件中定义了类模板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_allocatorget_allocatorget_allocatorget_allocator返回分配器,用于给容器元素分配内存
Element access不适用at不适用不适用带边界检查的返回元素(C++11)
不适用operator[]不适用不适用不带边界检查的返回元素,可用于插入元素
Iteratorsbegin,cbeginbegin,cbeginbegin,cbeginbegin,cbegin返回指向哈希表指定条目(bucket)所包含的首元素的迭代器 (C++11)
endendendend指向容器末尾的迭代器
Capacityemptyemptyemptyempty检查容器是否为空
sizesizesizesize返回容器元素的数量。
max_sizemax_sizemax_sizemax_size返回受系统与库的实现所限,容器元素的最大可能数量
Modifiersclearclearclearclear清空容器
insertinsertinsertinsert插入元素
emplaceemplaceemplaceemplace原位构造 (C++11)
emplace_hintemplace_hintemplace_hintemplace_hint使用hint原位构造 (C++11)
try_emplacetry_emplacetry_emplacetry_emplace如果给定的key在容器中不存在,原位构造一个元素 (C++17)
eraseeraseeraseerase擦除元素
swapswapswapswap两个容器交换内容
Lookupcountcountcountcount返回匹配指定键值的元素数量
findfindfindfind发现具有指定键值的元素
equal_rangeequal_rangeequal_rangeequal_range返回匹配指定键值的元素范围
reservereservereservereserve扩展容器的容量(C++11)
Bucket接口bucket_sizebucket_sizebucket_sizebucket_size返回指定索引的哈希表条目所容纳的容器元素的数量(C++11)
哈希策略
hash_functionhash_functionhash_functionhash_function返回用于创制键值hash的函数对象
key_eqkey_eqkey_eqkey_eq返回键值比较函数对象(C++11)
rehashrehashrehashrehash设定哈希表的条目(bucket)数量并重新生成哈希表(C++11)
max_load_factormax_load_factormax_load_factormax_load_factor返回或者设置哈希表的每个条目能容纳的容器元素的最大数量(C++11)
load_factorload_factorload_factorload_factor返回哈希表的每个条目容纳的容器元素的平均数量(C++11)
max_bucket_countmax_bucket_countmax_bucket_countmax_bucket_count返回由于系统及库的实现所能支持的哈希表条目的最大可能数量(C++11)
bucket_countbucket_countbucket_countbucket_count返回容器中的哈希表条目的数量(C++11)
bucketbucketbucketbucket返回指定键值所匹配的哈希表条目的索引(C++11)
Observersoperator==,!=operator==,!=operator==,!=operator==,!=两个容器的内容是否相同

例子

#include #include #include  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;

与本文近似的文章: