简介

很明显,这两个头文件分别是map、set头文件对应的unordered版本。 所以它们有一个重要的性质就是:

乱序
如何乱序

这个unorder暗示着,这两个头文件中类的底层实现----Hash。
也是因为如此,你才可以在声明这些unordered模版类的时候,传入一个自定义的哈希函数,准确的说是哈希函数子(hash function object)。

具有相同相同哈希值的元素被放在同一个桶(bucket)中。

为何乱序

在提供映射、集合功能的情况下,侧重于元素的快速获取。

用树结构(红黑树、二叉搜索树等)实现的map、set,在查找、获取、修改元素的时候,通常需要从根结点自上而下一次遍历树结构,因此时间复杂度为线性 ;
而通过哈希表实现, 只要哈希函数以及桶的大小选取得当,时间复杂度会是常数(只需要调用一次函数,并进行小幅度的查找)。

单向迭代器

哈希表的实现复杂了该容器上的双向遍历,似乎没有一种合适的方法能够做到高效快速。
因此,unorder版本的map和set只提供前向迭代器(非unorder版本提供双向迭代器)。

少了什么函数

lower_bound
upper_bound
普通版本的map和set,它们是有序容器,对每一个元素都能都能判断它应该在哪个之前、在哪个之后;
而该版本的容器则不一样,因为它们是乱序的,不能确定每个元素的先后顺序。 因此,容器没有足够的信息来计算这两个边界(然而元素的相等性比较依旧是可行的)。

多了什么函数

出于实现的概念,该版本的类模版必不可少的多了些特殊的函数。

桶相关(Bucket)

bucket_count : 桶数量。
max_bucket_count : 最大桶数量。
bucket_size : 桶大小,即容量。
bucket : 定位给定元素的桶位置。
哈希策略

load_factor : 返回load factor,即容器当前元素数量与桶数量之比。
max_load_factor : 返回或设置最大load factor。
rehash : 设置桶的数量,并重新对元素进行哈希映射。
reserve : 请求保留桶的数量至给定值。
注意到,没有函数能改变桶的容量,可能桶也是动态增长的。

Observers

hash_function : 返回哈希函数(在声明时作为参数传入,或默认的位于funtional头文件中的hash)。
key_eq : 返回key的相等性谓词,情况与hash_function相似。

-------------------------------------------------------------------------------------

C++ 11标准当中新增加了四个无序关联容器,分别是 
unordered_map 映射 
unordered_multimap 多重映射 
unordered_set 集合 
unordered_multiset 多重集合

与普通的map和set的基本功能一样,但是内部实现方式却完全不同。 
map与set的实现方式为红黑树 
unordered_map和unordered_set的实现方式为哈希函数,所以无序关联容器不会根据key值对存储的元素进行排序。

<>unordered_map

插入操作:
 
*
#include<bits/stdc++.h>

*
using namespace std;

*
typedef pair<string,size_t> pss;

*
int main()

*
{

*
ios::sync_with_stdio(false);

*  
*
unordered_map<string,size_t> u_map;

*
pss p1={"efg",2};

*  
*
string s="abc";

*
u_map[s]++;//使用下标插入

*  
*
u_map.insert(p1);//使用nsert函数插入一个pair

*  
*
u_map.insert({{"www",2},{"wqwe",3}});//插入一个初始化列表

*  
*  
*
vector<pss> vp={{"wrrr",2},{"ttt",3}};

*  
*
u_map.insert(vp.begin(),vp.end());//插入一个迭代器范围

*  
*
for(auto x:u_map)

*
cout<<x.first<<" "<<x.second<<endl;

*
return 0;

*
}

查找与删除操作

查找函数:find

与其他容器当中的find方法相同,参数内容可以是迭代器,也可以是key值。 
返回内容为迭代器,如果查找内容不存在,则返回迭代器尾部。
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*
auto it=u_map.find("qq");

*
if(it!=u_map.end())

*
cout<<it->first<<" "<<it->second<<endl;

*  
删除函数:earse

与其他容器当中的erase方法相同,参数中内容可以是迭代器,也可以是key值。
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*
u_map.erase("www");//直接按照key值删除

*  
*
for(auto x:u_map)

*
cout<<x.first<<" "<<x.second<<endl;

<>桶管理

由于无序关联容器的实现是基于hash函数,那么就需要解决冲突问题,解决冲突的办法比较常用有开放地址法和拉链法。在C++的unordered_map当中,采用的是”桶”的方法,也就是出现冲突的元素都存放在一个桶里。用拉链法的图来做个例子

在unordered_map当中所使用的哈希策略可以通过函数重载由用户自定义。

遍历每个桶,并输出桶中的元素
 
*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*  
*
for(auto i=0;i<u_map.bucket_count();i++)

*
{

*
for(auto it=u_map.begin(i);it!=u_map.end(i);it++)//迭代器中添加参数,选择桶的编号

*
{

*
cout<<"bucket: "<<i<<" "<<it->first<<" "<<it->second<<endl;

*
}

*  
*
}

如何查看要存入的内容经过hash函数处理以后的hash值?可以使用hash_function函数。
 
*
typedef unordered_map<string,size_t> string_int_map

*
unordered_map<string,size_t> u_map;

*
vector<pss> vp={{"wrrr",2},{"ttt",3},{"www",3},{"qq",10}};

*
u_map.insert(vp.begin(),vp.end());

*  
*
string_int_map::hasher fn=u_map.hash_function();

*  
*
for(auto it=vp.begin();it!=vp.end();it++)

*
{

*
cout<<it->first<<"的哈希值是: "<<fn(it->first)<<endl;

*
}

<>自定义类型

在unordered_map当中对结构体或者是class进行操作需要重载==运算符,同时自定义hash函数。
 
*
#include<bits/stdc++.h>

*
using namespace std;

*  
*
struct node

*
{

*
string name;

*
int number;

*
node(){}

*
bool operator==(const node& n) const//重载==运算符

*
{

*
return name==n.name;

*
}

*
};

*  
*
struct myhash//自定义hash函数

*
{

*
size_t operator()(const node &n) const

*
{

*
return n.name.size();//按照名字的长度当做hash值

*
}

*
};

*
int main()

*
{

*
ios::sync_with_stdio(false);

*  
*
unordered_map<node,size_t,myhash> u_map;

*  
*
node n;

*
n.name="mike";

*
n.number=100;

*  
*
u_map.insert({n,10});

*  
*  
*
return 0;

*
}

如果结构体或者类当中使用系统当中按照某个成员作为来取hash值的,可以进行如下操作 

例如定义了一个结构体,里面有num和res两个int型成员,现在我想把这个结构体存储到unordered_set当中,其中hash的值按照res的哈希函数来实现,又不想自己写,希望能用系统自带的对int处理的hash函数。
 
*
typedef unordered_set<int> usi;

*  
*
struct node

*
{

*
int num;

*
int res;

*
node(int n,int r){ num = n, res = r;}

*
bool operator==(const node& n) const//重载==运算符

*
{

*
return res==n.res;

*
}

*
};

*
struct myhash

*
{

*
size_t operator()(const node &n) const

*
{

*
usi::hasher fn= usi().hash_function();

*
//usi是一个unordered_set<int>

*
//选取它的哈希函数作为我们定义结构体当中的哈希函数

*
return fn(n.res);//处理res值后返回即可

*
}

*
};

*
//声明的时候这样使用unordered_set<node,myhash>

unordered_set的操作与性质与unordered_map大致类似。

在效率上,hash的操作时间复杂度是O(1),但是在真实的情况下,需要对hash的函数进行详细的设计,否则效率和内存方面的开销会很大。

技术
©2019-2020 Toolsou All rights reserved,
java实现抢红包功能2021年2月程序员工资统计,平均15144元可怕的不是堕落,而是清楚自己在堕落java简单的抽奖算法,抽奖DemoPYTHON入门期末复习汇总惹什么猫都别惹熊猫!「功夫熊猫」20年对人类拿下4血软件测试之BUG描述JS 的骚操作程序员因拒绝带电脑回家被开除,获赔 19.4 万元vue组件页面高度根据屏幕大小自适应