无序关联容器 (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_map、unordered_multimap、unordered_set、unordered_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_allocator`	`get_allocator`	`get_allocator`	`get_allocator`	返回分配器，用于给容器元素分配内存
Element access	不适用	`at`	不适用	不适用	带边界检查的返回元素（C++11）
Element access	不适用	`operator[]`	不适用	不适用	不带边界检查的返回元素，可用于插入元素
Iterators	`begin,cbegin`	`begin,cbegin`	`begin,cbegin`	`begin,cbegin`	返回指向哈希表指定条目（bucket）所包含的首元素的迭代器（C++11）
Iterators	`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 #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;

无序关联容器 (STL)

历史

类成员函数

例子

定制哈希函数

与本文近似的文章：

其他人正在再看...