C++（初阶）（二十一）——unordered_set和unordered_map

二十二，unordered_set和unordered_map的使用

1.unordered_set

1.1介绍

c++11

template<class Key,class Hash = std::hash<Key>,class KeyEqual = std::equal_to<Key>,class Allocator = std::allocator<Key>
> class unordered_set;

c++17

namespace pmr {template<class Key,class Hash = std::hash<Key>,class Pred = std::equal_to<Key>> using unordered_set = std::unordered_set<Key, Hash, Pred, std::pmr::polymorphic_allocator<Key>>;    	
}

1. 定义在头文件<unordered_set>
2. Key就是unordered_set底层关键字的类型。
3. unordered_set默认要求Key支持转换为整形，如果不⽀持或者有额外的需求可以自行实现支持将Key转成整形的仿函数传给第⼆个模板参数。
4. unordered_set默认要求Key支持比较相等，如果不⽀持或者想按⾃⼰的需求⾛可以自行实现支持将Key比较相等的仿函数传给第三个模板参数。
5. unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数。
6. unordered_set底层是⽤哈希桶实现，增删查平均效率是O(1)，迭代器遍历无序，为了跟set区分，所以取名unordered_set。
7. 存储元素和set一样会去重。

1.2和set使用差异

​ unordered_set的增删查使用和set是一样的。

差异：

1. 对key的要求不同，set要求Key⽀持小于比较，⽽unordered_set要求Key⽀持转成整形且⽀持等于⽐较。
2. set是双向迭代器，unordered_set是单向迭代器。
3. set底层是红黑树，红黑树的底层是二叉搜索树，所以中序遍历是有序的，也就是实现了有序+去重；unordered_set底层是哈希表，遍历时是无序的，无序+去重。
4. 性能差异。红⿊树增删查改效率是O(logN) ，⽽哈希表增删查平均效率是O(1) 。

参考代码：ANY_10/c_plus_plus - Gitee.com

2，unordered_multimap/unordered_multiset

unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。

unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异，key的要求的差异，iterator及遍历顺序的差异，性能的差异。

3，map和unordered_map

map和unordered_map与set和unoedered_set无太大差异。