STL map, hash_map , unordered_map区别、对比

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80877558

首先:

hash_mapunordered_map比较

具体可见 stack overflow: Difference between hash_map and unordered_map?

由于在C++标准库中没有定义散列表hash_map,标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的,所以它们在功能和性能保证上都有微妙的差别。

从C++11开始,哈希表实现已添加到C++标准库标准。决定对类使用备用名称,以防止与这些非标准实现的冲突,并防止在其代码中有hash_table的开发人员无意中使用新类。

所选择的备用名称是unordered_map,它更具描述性,因为它暗示了类的映射接口和其元素的无序性质。

可见hash_mapunordered_map本质是一样的,只不过 unordered_map被纳入了C++标准库标准。

map vs unordered_map

比较好的对比见:stackoverflow:How to choose between map and unordered_map?

主要是,查询、插入、删除的时间复杂度三个方面:

unordered_map(等价于hash_map)和map类似,都是存储的key-value的值,可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序,

  1. map 内部数据的组织,基于红黑树实现,红黑树具有自动排序的功能,因此map内部所有的数据,在任何时候,都是有序的。
  2. unordered_map(hash_map) 基于哈希表,数据插入和查找的时间复杂度很低,几乎是常数时间,而代价是消耗比较多的内存。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。

可以见STL源码剖析:

STL源码剖析-hash_set / hash_multiset STL源码剖析-hash_map / hash_multimap STL源码剖析-hashtable

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之树的子结构(九度OJ1520)

题目描述: 输入两颗二叉树A,B,判断B是不是A的子结构。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行一个整数n,m(...

200100
来自专栏小樱的经验随笔

hihoCoder #1082 : 然而沼跃鱼早就看穿了一切(字符串处理)

#1082 : 然而沼跃鱼早就看穿了一切 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 ? fjxmlhx每天都在被沼跃鱼刷屏,因...

29150
来自专栏灯塔大数据

每周学点大数据 | No.28 表排序

No.28期 表排序 Mr. 王:前面我们讨论了一些基础磁盘算法,现在我们来讨论一些关于磁盘中图算法的问题。 通过对基础磁盘算法的学习,我们可以很容易地想到...

34270
来自专栏深度学习那些事儿

探讨pytorch中nn.Module与nn.autograd.Function的backward()函数

本文讲解基于pytorch0.4.0版本,如不清楚版本信息请看这里。backward()在pytorch中是一个经常出现的函数,我们一般会在更新loss的时候使...

28440
来自专栏Web 开发

做wordpress CMS必须用到的强力代码(转)

这个代码很强力,做一个wordpress cms的索引页面(index.php) 这个代码是必须要会使用,不然会走很多弯路。

11220
来自专栏yw的数据分析

data.table包使用应该注意的一些细节

  注意默认nThread=getDTthreads(),即使用所有能用的核心,但并不是核心用的越多越好,本人亲自测试的情况下,其实单核具有较强的性能,只有在数...

8310
来自专栏用户2442861的专栏

阿里巴巴2014笔试题详解(9月22北京)

第一部分 单选题(前10题,每题2分;后10题,每题3分。选对得满分,选错倒扣1分,不选得0分)

20910
来自专栏xcywt

编译到底做了什么(***.c -> ***.o的过程)

 (第一次写博客,好激动的说.......) 我们知道,一个程序由源代码到可执行文件往往由这几步构成: 预处理(Prepressing)-> 编译(Compil...

20850
来自专栏Android相关

散列表(Hash Table)

散列表是一种以平均O(1)时间插入、删除和查找的数据结构,可是类似于findMax,findMin等操作则需要以O(N)的时间才能完成

18430
来自专栏软件开发 -- 分享 互助 成长

分解成3NF的保持函数依赖的分解算法:

转换成3NF的保持函数依赖的分解算法: ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,...

37350

扫码关注云+社区

领取腾讯云代金券