【C++】攻克哈希表(unordered_map)

举报
看,未来 发表于 2020/12/30 00:16:59 2020/12/30
【摘要】 文章目录 与hash_map纠缠的日子unordered_map测试代码unordered_map与map的区别hash_map ≈ unordered_mapunordered_map 使用成员函数: 对 c++ unordered_map 源码的解析 与hash_map纠缠的日子 hash_map可以说是我一直欲求不得的宝了,第一次接触我就想...

在这里插入图片描述

与hash_map纠缠的日子

hash_map可以说是我一直欲求不得的宝了,第一次接触我就想拿下它,奈何,网上这种的:《手把手教你实现hash_map》,zzz,还手把手呢,自制hash_map,我们自己不会?我要的是使用教程啊。。

后来千方百计弄到一套函数,以为至于能一窥堂奥了,结果一测试,VS报错说hash_map,安检过不了,于是我又在网上找了,说去改配置文件,结果改完之后根本没办法写回系统。。

然后我想起来之前在Linux下有见过老师用,代码还在呢,便急匆匆去Linux下测试,还是那个错,说过不了安检。唉。。

好在编译器还给我指了条明路:unordered_map。这不,我就来了。

然后,这篇文章顺序有点凌乱,哈哈哈,要哪一部分自行目录导航吧

unordered_map测试代码

先来看看内存测试代码,Linux环境。

如果硬件不好,N就别开那么大了,稍微小点死不了

/**
比较map、hash_map和unordered_map的执行效率以及内存占用情况
**/
 
#include <sys/types.h>
#include <unistd.h>
#include <sys/time.h>	
#include <iostream>
#include <fstream>
#include <string>
#include <map>
//#include <ext/hash_map>
#include <tr1/unordered_map>
 
using namespace std;
//using namespace __gnu_cxx;
using namespace std::tr1;
 
#define N 100000000  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000
 
//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>
//typedef map<int,int> MapKey; //采用map
//typedef hash_map<int,int> MapKey; //采用hash_map
typedef unordered_map<int,int> MapKey;  //采用unordered_map
 
int GetPidMem(pid_t pid,string& memsize)
{
	char filename[1024]; snprintf(filename,sizeof(filename),"/proc/%d/status",pid); ifstream fin; fin.open(filename,ios::in);
	if (! fin.is_open())
	{
		cout<<"open "<<filename<<" error!"<<endl;
		return (-1);
	} char buf[1024];
	char size[100];
	char unit[100]; while(fin.getline(buf,sizeof(buf)-1))
	{
		if (0 != strncmp(buf,"VmRSS:",6)) continue; sscanf(buf+6,"%s%s",size,unit); memsize = string(size)+string(unit);
	} fin.close(); return 0;
}
 
int main(int argc, char *argv[])
{
	struct timeval begin; struct timeval end; MapKey MyMap; gettimeofday(&begin,NULL); for(int i=0;i<N;++i)
		MyMap.insert(make_pair(i,i)); gettimeofday(&end,NULL); cout<<"insert N="<<N<<",cost="<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl; for(int i=0;i<N;++i)
		MyMap.find(i); gettimeofday(&end,NULL); cout<<"insert and getall N="<<N<<",cost="<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl; string memsize; GetPidMem(getpid(),memsize); cout<<memsize<<endl; return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

unordered_map与map的区别

boost::unordered_map, 它与 stl::map的区别就是,stl::map是按照operator<比较判断元素是否相同,以及比较元素的大小,然后选择合适的位置插入到树中。所以,如果对map进行遍历(中序遍历)的话,输出的结果是有序的。顺序就是按照operator< 定义的大小排序。
而boost::unordered_map是计算元素的Hash值,根据Hash值判断元素是否相同。所以,对unordered_map进行遍历,结果是无序的。
用法的区别就是,stl::map 的key需要定义operator< 。 而boost::unordered_map需要定义hash_value函数并且重载operator==。对于内置类型,如string,这些都不用操心。对于自定义的类型做key,就需要自己重载operator< 或者hash_value()了。
最后,说,当不需要结果排好序时,最好用unordered_map。
其实,stl::map对于与java中的TreeMap,而boost::unordered_map对应于java中的HashMap。

hash_map ≈ unordered_map

最初的 C++ 标准库中没有类似 hash_map 的实现,但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的,所以它们在功能和性能保证方面都有细微差别。

从 C++ 11 开始,hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突,决定使用替代名称 unordered_map。这个名字其实更具描述性,因为它暗示了该类元素的无序性。

unordered_map 使用

#include <unordered_map>

//取得键和值:
unordered_map<Key,T>::iterator it;
it->first; // same as (*it).first   (the key value)
it->second; // same as (*it).second  (the mapped value) 

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

成员函数:

=迭代器==
begin | 返回指向容器起始位置的迭代器(iterator)
end | 返回指向容器末尾位置的迭代器
cbegin | 返回指向容器起始位置的常迭代器(const_iterator)
cend | 返回指向容器末尾位置的常迭代器

=Capacity=
size 返回有效元素个数
max_size 返回 unordered_map 支持的最大元素个数
empty 判断是否为空

=元素访问=
operator[] 访问元素
at 访问元素(如 m.at(5) = 3.33)

=元素修改=
insert 插入元素
erase 删除元素
swap 交换内容
clear 清空内容
emplace 构造及插入一个元素
emplace_hint 按提示构造及插入一个元素

=操作=
find 通过给定主键查找元素
count 返回匹配给定主键的元素的个数
equal_range 返回值匹配给定搜索值的元素组成的范围

=Buckets==
bucket_count 返回槽(Bucket)数
max_bucket_count 返回最大槽数
bucket_size 返回槽大小
bucket 返回元素所在槽的序号
load_factor 返回载入因子,即一个元素槽(Bucket)的最大元素数
max_load_factor 返回或设置最大载入因子
rehash 设置槽数
reserve 请求改变容器容量

对 c++ unordered_map 源码的解析

如果是大神,还是自己去看源码,毕竟源码之前,了无秘密嘛,不过那个unordered_map的文件啊,我打开的时候就只有一堆头文件,其他容器也是,只有头文件,像我这种的小白,那就看别人分析好的吧哈哈哈。

如果哪天,上面那个链接失效了,没事我已经未雨绸缪了嘿嘿。

顺便呢,我还发现这个博主有不少STL源码剖析的好文章啊,心照不宣心照不宣。

文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。

原文链接:lion-wu.blog.csdn.net/article/details/107298969

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。