免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 23201 | 回复: 35

[C++] 请教:STL的map为什么用红黑树而不是哈希 [复制链接]

论坛徽章:
12
2015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之同曦
日期:2017-03-17 19:13:162016科比退役纪念章
日期:2016-11-07 08:28:12luobin
日期:2016-06-17 17:46:36wusuopu
日期:2016-06-17 17:43:4515-16赛季CBA联赛之福建
日期:2016-01-14 12:49:22程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:002015年亚洲杯之科威特
日期:2015-03-24 14:21:272015年迎新春徽章
日期:2015-03-04 09:57:092016科比退役纪念章
日期:2018-04-10 16:20:18
发表于 2015-05-29 17:16 |显示全部楼层
RT

个人以为用红黑树虽然速度可能会略逊于哈希,但是整体来说,应该更节省内存。

大牛指教。

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2015-05-29 18:05 |显示全部楼层
map是有序容器,hash map是无序容器.
无序的的map也有,叫unoredered_map, C++11新加的

论坛徽章:
12
2015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之同曦
日期:2017-03-17 19:13:162016科比退役纪念章
日期:2016-11-07 08:28:12luobin
日期:2016-06-17 17:46:36wusuopu
日期:2016-06-17 17:43:4515-16赛季CBA联赛之福建
日期:2016-01-14 12:49:22程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:002015年亚洲杯之科威特
日期:2015-03-24 14:21:272015年迎新春徽章
日期:2015-03-04 09:57:092016科比退役纪念章
日期:2018-04-10 16:20:18
发表于 2015-05-29 18:09 |显示全部楼层
回复 2# egmkang


    答非所问,


    你说的我知道。

   
    谢谢,

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2015-05-29 18:41 |显示全部楼层
VIP_fuck 发表于 2015-05-29 18:09
回复 2# egmkang


你hash map怎么有序? 有时候别人就是需要这个功能,而不只是快速查找.

论坛徽章:
12
2015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之同曦
日期:2017-03-17 19:13:162016科比退役纪念章
日期:2016-11-07 08:28:12luobin
日期:2016-06-17 17:46:36wusuopu
日期:2016-06-17 17:43:4515-16赛季CBA联赛之福建
日期:2016-01-14 12:49:22程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:002015年亚洲杯之科威特
日期:2015-03-24 14:21:272015年迎新春徽章
日期:2015-03-04 09:57:092016科比退役纪念章
日期:2018-04-10 16:20:18
发表于 2015-05-29 18:50 |显示全部楼层
回复 4# egmkang


    晕,我不是找你来说教的。

    你说的东西我知道,

论坛徽章:
44
15-16赛季CBA联赛之浙江
日期:2021-10-11 02:03:59程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2015-05-29 20:22 |显示全部楼层
有序的叫map,无序的叫unordered_map,两个东西么。

你是不是想问为什么不把有序的叫ordered_map无序的叫map?这你得问C++他爹……

论坛徽章:
12
2015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之同曦
日期:2017-03-17 19:13:162016科比退役纪念章
日期:2016-11-07 08:28:12luobin
日期:2016-06-17 17:46:36wusuopu
日期:2016-06-17 17:43:4515-16赛季CBA联赛之福建
日期:2016-01-14 12:49:22程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:00程序设计版块每日发帖之星
日期:2015-06-08 22:20:002015年亚洲杯之科威特
日期:2015-03-24 14:21:272015年迎新春徽章
日期:2015-03-04 09:57:092016科比退役纪念章
日期:2018-04-10 16:20:18
发表于 2015-05-29 21:14 |显示全部楼层
我的问题是没说清楚?还是各位看不懂?

我知道c++11新增了unordered_map 和 set,

论坛徽章:
323
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2015-05-29 21:54 |显示全部楼层
VIP_fuck 发表于 2015-05-29 21:14
我的问题是没说清楚?还是各位看不懂?

我知道c++11新增了unordered_map 和 set,


应该是你问题没说清楚。

论坛徽章:
1
射手座
日期:2013-08-21 13:11:46
发表于 2015-05-29 22:59 |显示全部楼层
个人以为用红黑树虽然速度可能会略逊于哈希,但是整体来说,应该更节省内存。

速度我们不说,肯定慢很多.
省内存,我们来分析一下.
一个红黑树的节点,有左右节点指针,和父节点指针,这就是三个指针的大小+value_type的大小;
unordered_map呢,开放地址法,就value_type,如果是开链法,那就是prev指针和next指针,俩指针+value_type

也就是说,当你的value_type越小,红黑树越浪费内存.
而hash table呢,主要是填充因子,比如0.5的填充因子,那么那些桶是要浪费一些内存的.

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-05-30 10:55 |显示全部楼层
楼主NB, 8741.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP