c stl 之 unordered-凯发k8官方网

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

首先要include这个unordered_set头文件。
然后就是第六行我们定义了一个整型int的集合，叫myset。
后面几行，我们演示了insert/find/erase的用法。
有两点需要注意：
一是这个容器是个集合，所以重复插入相同的值是没有效果的。大家可以看到我们这里第7行和第9行插入了2次3，实际上这个集合里也只有1个3，第10行输出的结果是2。
二是find的返回值是一个迭代器(iterator)，如果找到了会返回指向目标元素的迭代器，没找到会返回end()。

对于unordered_set，insert/find/erase的平均复杂度是o(1)，但是最坏复杂度是o(n)的，这里n是指容器中元素数量。

有两种情况会出现o(n)复杂度。
1是你的哈希函数太烂了，导致很多不同元素的哈希值都相同，全是碰撞，这种情况复杂度会变成o(n)。但是这种情况一般不用担心，因为对于string以及int double之类的基本数据类型，都有默认的哈希函数，而且默认的哈希函数足够好，不会退化到o(n)。如果是你自定义的哈希函数，那你要小心一点，别写的太差了。
2是如果insert很多数据，会触发rehash。就是整个哈希表重建。这个过程有点类似向vector里不断添加元素，vector会resize。比如你新建一个vector时，它可能只申请了一块最多保存10个元素的内存，当你插入第11个元素的时候，它会自动重新申请一块更大空间，比如能存下20个元素。哈希表也是类似，不过rehash不会频繁发生，均摊复杂度还是o(1)的，也不用太担心。

unordered_set是一个集合，有的时候我们需要一个字典，就是保存一系列key/value对，并且可以按key来查询。比如我们要保存很多同学的成绩，每位同学有一个学号，也有一个分数，我们想按学号迅速查到成绩。这时候我们就可以用unordered_map。

unordered_map同样也提供了增删查函数:
unordered_map::insert
unordered_map::find
unordered_map::erase
这三个函数的平均时间复杂度也是o(1)的。我们可以看一个例子：

首先我们看第2行，要用unordered_map你要先include相应的头文件。
在7行我们定义了一个mymap，它的key是string类型，字符串；value是整形。
第8第9行展示的insert插入，因为我们这里要插入的是一个key/value pair(键值对)，我们要用make_pair函数把一个字符串和一个整数打包成一个pair。
第10行是find查找，find返回的也是一个迭代器，iterator。这里我们懒得写很长的迭代器类型，直接用的auto。auto是c 11标准里的关键字，它会自动推断变量的类型。如果你的编译器不支持c 11，那你还是要老老实实写全:unordered_map::iterator

迭代器指向的是一个pair，所以第11行我们可以用first和second去拿到对应的key和value，这里first是”c ”这个字符串，second是100这个整数。
第13第14行展示了一下erase删除。

值得一提的是，unordered_map重载了[]运算符，我们可以把key放在中括号里，像操作数组一样操作unordered_map：

上面这个程序的输出结果是101。大家可以看一下第8~第10行。我们把”c ”这个key放在中括号里就能直接操作”c ”对应的值。这种写法会让程序更直观。
--------------------- 
作者：夏普通 
来源：csdn 
原文：https://blog.csdn.net/qq_34243930/article/details/81456582 
凯发k8官方网的版权声明：本文为博主原创文章，转载请附上博文链接！

————————————————————————————————————————————————————————

unordered_set与与unordered_map相似,这次主要介绍unordered_set

unordered_set它的实现基于hashtable,它的结构图仍然可以用下图表示,这时的空白格不在是单个value,而是set中的key与value的数据包

有unordered_set就一定有unordered_multiset.跟set和multiset一样,一个key可以重复一个不可以

unordered_set是一种无序集合,既然跟底层实现基于hashtable那么它一定拥有快速的查找和删除，添加的优点.基于hashtable当然就失去了基于rb_tree的自动排序功能

unordered_set无序,所以在迭代器的使用上,set的效率会高于unordered_set

注：

一是这个容器是个集合，所以重复插入相同的值是没有效果的。大家可以看到我们这里第7行和第9行插入了2次3，实际上这个集合里也只有1个3，第10行输出的结果是2。
二是find的返回值是一个迭代器(iterator)，如果找到了会返回指向目标元素的迭代器，没找到会返回end()。

对于unordered_set，insert/find/erase的平均复杂度是o(1)，但是最坏复杂度是o(n)的，这里n是指容器中元素数量。
 

template<class _value,

class _hash = hash<_value>,

class _pred = std::equal_to<_value>,

class _alloc = std::allocator<_value> >

class unordered_set

: public __unordered_set<_value, _hash, _pred, _alloc>

{

typedef __unordered_set<_value, _hash, _pred, _alloc> _base;

...

}　　

 

参数1 _value key和value的数据包

参数2 _hash hashfunc获取hashcode的函数

参数3 _pred 判断key是否相等

参数4 分配器

下面介绍一下unordered_set的基本使用,最后我会分享一下我的测试代码

---

 

一 定义

//定义

unordered_set<int> c1;

//operator=

unordered_set<int> c2;

c2 = c1;

 

 

---

 

二 容量操作

//判断是否为空

c1.empty();

//获取元素个数 size()

c1.size();

//获取最大存储量 max_size()

c1.max_size();

 

---

 

三 迭代器操作

//返回头迭代器 begin()

unordered_set<int>::iterator ite_begin = c1.begin();

//返回尾迭代器 end()

unordered_set<int>::iterator ite_end = c1.end();

//返回const头迭代器 cbegin()

unordered_set<int>::const_iterator const_ite_begin = c1.cbegin();

//返回const尾迭代器 cend()

unordered_set<int>::const_iterator const_ite_end = c1.cend();

//槽迭代器

unordered_set<int>::local_iterator local_iter_begin = c1.begin(1);

unordered_set<int>::local_iterator local_iter_end = c1.end(1);

---

 

四 基本操作

//查找函数 find() 通过给定主键查找元素

unordered_set<int>::iterator find_iter = c1.find(1);

//value出现的次数 count() 返回匹配给定主键的元素的个数

c1.count(1);

//返回元素在哪个区域equal_range() 返回值匹配给定搜索值的元素组成的范围

pair<unordered_set<int>::iterator, unordered_set<int>::iterator> pair_equal_range = c1.equal_range(1);

//插入函数 emplace()

c1.emplace(1);

//插入函数 emplace_hint() 使用迭代器

c1.emplace_hint(ite_begin, 1);

//插入函数 insert()

c1.insert(1);

//删除 erase()

c1.erase(1);//1.迭代器 value 区域

//清空 clear()

c1.clear();

//交换 swap()

c1.swap(c2);

---

 五 篮子操作

//篮子操作 篮子个数 bucket_count() 返回槽（bucket）数

c1.bucket_count();

//篮子最大数量 max_bucket_count() 返回最大槽数

c1.max_bucket_count();

//篮子个数 bucket_size() 返回槽大小

c1.bucket_size(3);

//返回篮子 bucket() 返回元素所在槽的序号

c1.bucket(1);

// load_factor 返回载入因子，即一个元素槽（bucket）的最大元素数

c1.load_factor();

// max_load_factor 返回或设置最大载入因子

c1.max_load_factor();

---

 

六 内存操作

// rehash 设置槽数

c1.rehash(1);

// reserve 请求改变容器容量

c1.reserve(1000);

---

 

七 hash func

//hash_function() 返回与hash_func相同功能的函数指针

auto hash_func_test = c1.hash_function();

//key_eq() 返回比较key值得函数指针

auto key_eq_test = c1.key_eq();

for(auto it=v.begin();it!=v.end();it) //auto是c 11标准里的关键字，它会自动推断变量的类型。 //如果你的编译器不支持c 11， //那你还是要老老实实写全:unordered_map::iterator //v.begin()返回的是一个指针类型所以想要具体的值还需要在前面加上* set.find(key) //如果key不存在，那么返回set.end() class solution { public:vector<int> twosum(vector<int>& nums, int target) {unordered_map<int,int> map;for(int i=0;i<nums.size();i){auto it=map.find(target-nums[i]);if(it!=map.end()) return {it->second,i};map[nums[i]]=i;//或者 map.insert(make_pair(nums[i],i));}return {};} };

上面这一段代码中注意以下几点

1.使用find(key)方法时，参数是key,同样的也是返回指针类型 2.key值保存在it->first中,value保存在it->second中 3.当我们使用insert方法插入键值对的时候需要在使用键值对函数make_pair() 4.我们还可以直接使用map[key]=value的方法 与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是凯发k8官方网为你收集整理的c stl 之 unordered_set 使用（包括unordersd_map）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。