【C++】攻克哈希表(unordered_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
- 点赞
- 收藏
- 关注作者
评论（0）