标题中提到的四种容器,对于概念不清的人来说,经常容易弄混淆。这里我不去把库里面复杂的原码拿出剖析,这个如果有兴趣其实完全可以查C++Reference,网上的原码是最权威和细致的了,而且我觉得有耐心直接认真看原码的人,也不需要我这篇速记博文了,所以我这里还是讲的通俗一些,把它们区分的七七八八。

一、hash_map、unordered_map

这两个的内部结构都是采用哈希表来实现。区别在哪里?unordered_map在C++11的时候被引入标准库了,而hash_map没有,所以建议还是使用unordered_map比较好。

哈希表的好处是什么?查询平均时间是O(1)。顾名思义,unordered,就是无序了,数据是按散列函数插入到槽里面去的,数据之间无顺序可言,但是有些时候我只要访问而不需要顺序,因此可以选择哈希表。举个最好的例子,就是我的LeetCode的博文里------Longest Consecutive Sequence这一题,我的方法二就是用的unordered_map来实现“空间弥补时间”这样的做法。


二、unordered_map与map

虽然都是map,但是内部结构大大的不同哎,map的内部结构是R-B-tree来实现的,所以保证了一个稳定的动态操作时间,查询、插入、删除都是O(logN),最坏和平均都是。而unordered_map如前所述,是哈希表。顺便提一下,哈希表的查询时间虽然是O(1),但是并不是unordered_map查询时间一定比map短,因为实际情况中还要考虑到数据量,而且unordered_map的hash函数的构造速度也没那么快,所以不能一概而论,应该具体情况具体分析。


三、unordered_map与unordered_set

后者就是在哈希表插入value,而这个value就是它自己的key,而不是像之前的unordered_map那样有键-值对,这里单纯就是为了方便查询这些值。我在Longest Consecutive Sequence这一题,我的方法一就是用了unordered_set,同样是一个将空间弥补时间的方法。再举个大家好懂的例子,给你A,B两组数,由整数组成,然后把B中在A中出现的数字取出来,要求用线性时间完成。很明显,这道题应该将A的数放到一个表格,然后线性扫描B,发现存在的就取出。可是A的范围太大,你不可能做一个包含所有整数的表,因为这个域太大了,所以我们就用unordered_set来存放A的数,具体实现库函数已经帮你搞定了,如果对于具体怎么去散列的同学又兴趣可以查看《算法导论》的第11章或者《数据结构与算法分析》的第五章,如果要看《算法导论》的同学我给个建议,完全散列你第一遍的时候可以暂时跳过不看,确实有点复杂。


暂时区别就是这样了,如果对于具体实现,或者函数的具体操作有疑问的,可以在评论里面留言或者私信我。>.<



Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐