unordered_set和unordered

Hello，今天我来为大家介绍一下前几年才刚刚新出的两个容器——unordered_map和unordered_set，这两个容器属于是map系列和set系列中的一种，和map/set不同的是它们的底层，map/set的底层是红黑树，而unordered_map/unordered_set这两个容器的底层则是哈希表，就查找效率而言，unordered_map/unordered_set要更胜一筹。我在这里为大家推荐一个英语的相关网站，希望对大家在学习unordered_map/unordered_set时能够有所帮助。

C/C++相关函数查询官网：Reference - C++ Reference

unordered_set%E7%B1%BB%E7%9A%84%E4%BB%8B%E7%BB%8D-toc" name="tableOfContents" style="margin-left:0px">1 unordered_set类的介绍

unordered_set%E5%92%8Cset%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82-toc" name="tableOfContents" style="margin-left:40px"> 1.1 unordered_set和set的使用差异

unordered_map%E7%B1%BB%E7%9A%84%E4%BB%8B%E7%BB%8D-toc" name="tableOfContents" style="margin-left:0px">2 unordered_map类的介绍

unordered_map%E5%92%8Cmap%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82-toc" name="tableOfContents" style="margin-left:40px"> 2.1 unordered_map和map的使用差异

3 unordered_multiset / unordered_multimap

4 unordered_xxx到的哈希相关接口

1 unordered_set类的介绍

1>.unordered_set的声明如下，Key就是unordered_set底层关键字的类型。

template < class Key, class Hash = hash<Key>, class Pred = equal_to<Key>, class Alloc = allocator<Key>>
class unordered_set;

2>.unordered_set默认要求Key支持转换为整形，如果不支持或者是想按照自己的需求走的，可以自行实现支持将Key转化成整形的仿函数传给第二个模板参数，也就是Hash。

3>.unordered_set默认要求Key支持比较相等，如果不支持或想按照自己的要求走的话则可以自行实现支持将Key比较相等的仿函数传给第三个模板参数。

4>.unordered_set底层存储数据的内存是空间配置器申请的，如果需要的话可以自己实现一个内存池，传给第四个参数。

5>.一般情况下，我们都不需要传后三个模板参数。

6>.unordered_set的底层使用哈希桶实现的，增删查平均效率是O(1)，迭代器遍历将不再是有序的了，为了跟set区分开来，因此取名为unordered_set。

7>.前面部分我们已经学习了set容器的使用，set和unordered_set的功能高度相似，只是底层结构不同，有一些性能（效率）和使用上的差异，这里我们只讲它们差异的那部分。

unordered_set%E5%92%8Cset%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82" name="%C2%A0%201.1%C2%A0unordered_set%E5%92%8Cset%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82"> 1.1 unordered_set和set的使用差异

1>.查看文档我们就会发现unordered_set的增删查操作跟set的增删查操作的使用是一摸一样的，既然如此的话，那么关于使用这里我们就不再做赘述和演示了，若有不会的，则可以参考文档及前面的set和map的使用这一章节，链接如下：

map和set的使用，相信我，超简单的！-CSDN博客文章浏览阅读2.6k次，点赞184次，收藏146次。class set;//T是关键字类型，用来构造二叉搜索树的时候会用到;Compare是一个仿函数，默认set类的底层的那棵二叉搜索树是左边的关键字永远比根小，右边的关键字永远比根大;Alloc是一个内存池，我们现在不需要看这个参数。2>.set类默认要求T支持小于比较，如果不支持或者作者想按自己的需求走的话我们可以自行实现仿函数传给第二个模板参数。3>.set底层存储数据的内存是从空间配置器中申请的，如果需要我们可以自己实现内存池，传给第三个参数。4>.一般情况下，我们都不需要去传后两个模板参数。https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502https://blog.csdn.net/2301_81390458/article/details/143649337?spm=1001.2014.3001.5502

2>.unordered_set和set的第一个差异是对Key的要求不同，set要求Key支持小于比较，而unordered_set则要求Key支持转成整形并且要支持等于比较，要理解unordered_set地去这两点要求得等到下一章我们结合哈希表的底层实现才能真正地理解，也就是说本质上其实是哈希表地要求。

3>.unordered_set和set的第二个差异是迭代器地差异，set地iterator是双向迭代器，unordered_set则是单向迭代器，其次由于set的底层是一棵红黑树，而红黑树是二叉搜索树，走中序遍历的话是有序的，所以set迭代器遍历是有序+去重。

4>.unordered_set和set的第三个差异是性能上的差异，整体而言在大多数的场景下，unordered_set的增删查能更快一些，因为红黑树增删查的效率是O(logN)，而哈希表增删查的平均效率是O(1)，这样简单地对比下来，unordered_set增删查地性能略胜一筹。

unordered_map%E7%B1%BB%E7%9A%84%E4%BB%8B%E7%BB%8D" name="2%20unordered_map%E7%B1%BB%E7%9A%84%E4%BB%8B%E7%BB%8D">2 unordered_map类的介绍

unordered_map的介绍和unordered_set差不多，我们这里参考unordered_set的介绍即可，这里就不再讲了。

unordered_map%E5%92%8Cmap%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82" name="%C2%A0%202.1%C2%A0unordered_map%E5%92%8Cmap%E7%9A%84%E4%BD%BF%E7%94%A8%E5%B7%AE%E5%BC%82"> 2.1 unordered_map和map的使用差异

1>.查看文档的话我们就会发现unordered_map支持的增删查改和map支持的增删查改的使用是一模一样的，关于使用我们这里就不做过多的讲述和演示了。

2>.unordered_map和map的第一个差异是对Key的要求不同，map要求Key支持小于比较，而unordered_map要求Key支持转成整形比较且支持等于比较，要理解unordered_map的这两点要求得后续我们结合哈希表底层实现才能真正的理解，也就是说这本质上是哈希表的要求。

3>.unordered_map和map的第二个差异是迭代器的差异，map的iterator是双向迭代器，unordered_map的iterator是单向迭代器，其次map的底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以map迭代器遍历时Key有序+去重，而unordered_map的底层时哈希表，迭代器遍历是Key无需+去重。

4>.unordered_map和map的第三个差异是性能的差异，整体而言大多数场景下，unordered_map的增删查改会更快一些，因为红黑树的增删查改的效率是O(logN)，而哈希表的增删查改的平均效率为O(1)。

3 unordered_multiset / unordered_multimap

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

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

4 unordered_xxx到的哈希相关接口

Buckets和Hash policy系列的接口分别是哈希桶和负载因子相关的接口，从日常使用的角度来看的话我们是不需要太关注的，后面学习了哈希表层面，我们再回来看这个系列的接口的话，那个时候会一目了然，此时看它不太合适。