精华内容
下载资源
问答
  • unordered_set

    2020-02-06 14:34:08
    将vector 的元素添加至unordered_set vector<string> wordDict; unordered_set<string> m(wordDict.begin(), wordDict.end());

    将vector 的元素添加至unordered_set

    vector<string> wordDict;
    unordered_set<string> m(wordDict.begin(), wordDict.end());
    
    展开全文
  • unordered_set unordered_multiset unordered_map unordered_multimap 特性 unordered_set/unordered_multiset性质和set/multiset一样,只是不支持lower_bound()操作,但是它的erase(), []的时间复杂度为O(1),即不...

    unordered_set unordered_multiset unordered_map unordered_multimap

    特性
    unordered_set/unordered_multiset性质和set/multiset一样,只是不支持lower_bound()操作,但是它的erase(), []的时间复杂度为O(1),即不能实现查找操作,但是增删改减的时间复杂度降低
    unorered_map/unordered_multimap也是类似,同上

    展开全文
  • unordered_set 1.unordered_set和set的使用方法很像,除了unordered_set的元素时无序的。 2.模板参数是: template<class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, ...

    unordered_set

    1.unordered_set和set的使用方法很像,除了unordered_set的元素时无序的。

    2.模板参数是:

    template<class Value, 
    		 class HashFcn = hash<Value>, 
    		 class EqualKey = equal_to<Value>, 
    		 class Alloc = alloc>
    

    能看到HashFcn的默认类型就是标准库内置hash模板类的一个偏特化的版本。而如果标准库的hash没有针对Value的偏特化版本,用户自己就必须提供一个自定义的重载了()符号的仿函数类

    默认的比较函数equal_to<Value>也可能不符合使用要求,因为它本质上就是调用Value重载的==符号。假如输入的是一个c风格的字符串,Value是const char*,直接用==号比较,效果是指针进行比较,不是我们想要的。所以需要自定义一个类,在类里面用strcmp实现。

    3.内部使用hashtable。

    hashtable的模板参数是:

    template <class Value, 
    		  class Key, 
    		  class HashFcn, 
    		  class ExtractKey, 
    		  class EqualKey, 
    		  class Alloc>
    

    unordered_set元素的键值就是实值,实值就是键值,所以使用的hashtable的Key和Value模板参数都是unordered_set模板参数中的Value,而ExtractKey就是identity<Value>

    4.构造函数

    默认构造函数,使用大小为100的表格,当然它会被增大成一个质数。

    对于只提供表格大小的构造函数,会用模板参数里的类HashFcn默认构造一个对象,用模板参数里的型别EqualKey默认构造一个对象,,来初始化内置的hashtable类型。用户也可以自己提供一个HashFcn类型的对象和EqualKey类型的对象来作为构造函数的参数。

    参数为两个迭代器的版本,实际上是调用了底层hashtable的insert_unique函数。

    unordered_map

    1.unordered_map和map的使用方法很像,除了unordered_map的元素是无序的。

    2.模板参数是:

    template<class Value, 
    	     class T, 
    	     class HashFcn = hash<Value>, 
    	     class EqualKey = equal_to<Value>, 
    	     class Alloc = alloc>
    

    HashFcn类型和EqualKey类型都和unordered_set一样,有时候可能需要用户提供。

    3.内部还是使用hashtable。

    hashtable的模板参数是:

    template <class Value, 
    		  class Key, 
    		  class HashFcn, 
    		  class ExtractKey, 
    		  class EqualKey, 
    		  class Alloc>
    

    这里的Value是键值对,所以hashtable的Value类型应该是pair<const Key, T>。注意这里的键的类型是const类型,这和map中一样,不允许修改键

    ExtractKey类型使用select1st<pair<const Key, T>>,实际上就是选出pair类型的first成员。

    参数为两个迭代器的版本,实际上是调用了底层hashtable的insert_unique函数。

    4.和map一样,也重载了[]符号:

    T& operator[](const key_type& key) {
    	return rep.find_or_insert(value_type(key, T())).second;
    }
    

    hashtable的find_or_insert函数返回的是Value类型,而在3中我们知道,在unordered_map中,这个Value被定义成pair<const Key, T>,因此,取出它的second成员返回。

    unordered_multiset

    1.unordered_multiset和unordered_set的唯一区别在于,它的插入操作使用的是insert_equal,而后者使用的是insert_unique

    unordered_multimap

    1.unordered_multimap和unordered_map的区别在于,它的插入操作使用insert_equal,而后者使用的是insert_unique。并且它没有重载的[]符号。

    展开全文
  • C++ unordered_set

    万次阅读 多人点赞 2019-09-15 17:56:52
    目录 1.定义 2.基本的函数 2.1.unordered_set构造 ...unordered_set本质是使用hash散列的方式存储数据,是一种使用hash值作为key的容器,所以当有频繁的搜索、插入和移除拥有常数时间。unor...

    目录

     

    1.定义

    2.基本的函数

    2.1.unordered_set构造

    2.2.添加新的元素(注意无法插入相同元素)

    2.3.查找元素

    2.4.查找桶接口

    2.5.观察器

    2.6.清除元素

    2.7.其他函数


    1.定义

    unordered_set本质是使用hash散列的方式存储数据,是一种使用hash值作为key的容器,所以当有频繁的搜索、插入和移除拥有常数时间。unordered_set存储原理是声明一个有n个桶的数据结构,计算加入到unordered_set的新的值hash,然后计算hash%n后的值x,将新的值加入到桶x中。当桶x中已经有了元素,就直接链接在后边。当数据结构中的元素满足一定数量时我们要扩充桶的数量,并重新构建桶结构。

    2.基本的函数

    2.1.unordered_set构造

    • std::unordered_set<std::string> c:初始化容器
    • std::unordered_set<std::string> c{ "aaa", "bbb", "ccc" }:初始化容器,并将"aaa", "bbb", "ccc"加入到容器中
    • std::unordered_set<std::string> c{ 16 }:初始化容器,并设置16个桶

    2.2.添加新的元素(注意无法插入相同元素)

    • c.insert("dddd"):向容器添加元素”dddd"
    • a.insert({ "aaa","bbbb","cccc" }):向容器添加元素"aaa","bbbb","cccc"
    • a.insert(b.begin(), b.end()):b是一个存储着和a相同类型元素的向量,可将b中所有元素添加到a中

    2.3.查找元素

    • a.find("eeee"):查找元素"eeee",返回结果为a.end()则表明没有找到,否则返回所对应元素
    • a.count("eeee"):查找元素"eeee"在a中有几个(由于unordered_set中没有相同的元素,所以结果通常为0或1)

    2.4.查找桶接口

    • a.bucket_count():返回数据结构中桶的数量
    • a.bucket_size(i):返回桶i中的大小
    • a.bucket(“eeee"):返回元素"eeee"在哪个桶里

    2.5.观察器

    • a.hash_function()("aaa"):返回"aaa"所对应的hash值
    • a.key_eq()("aaa","aaaa") :当元素相同时返回true,否则返回false

    2.6.清除元素

    • a.clear():清除a中所有元素
    • a.erase("aaa"):清除元素"aaa"

    2.7.其他函数

    • a.size():返回a中总的元素个数
    • a.max_size():返回a中最大容纳元素
    • a.empty():判断a中是否为空

    (未完待续)

     

    展开全文
  • unordered_map和unordered_set的模拟实现 (一)哈希表的特性及概念 定义: 哈希表(Hash table,也叫散列表),是根据关键字值(key,value)直接进行访问的数据结构。也就是说,它通过把关键字映射到表中一个位置来...
  • <p>Obviously, by nature of unordered sets, there is no <code>try_emplace</code> method in <a href="https://en.cppreference.com/w/cpp/container/unordered_set">unordered_set</a>. <p>Thanks!</p><p>该提问...
  • unordered_map,map,unordered_set, set 都属于关联容器, 容器中的元素 按关键字来保存和查找访问。 map、set 的实现方式是红黑树,采用 < 比较运算符组织元素(有序)。 unordered_map、unordered_set是根据...
  • unordered_set:自动删除重复元素,使得集合内元素各不相同 unordered_set<int> q; q.insert(1); q.insert(2); q.insert(1); q.insert(1); q.insert(1); cout << q.size() << endl; // 2 ...
  • set对应unordered_set,map对应unordered_map。 set与unordered_set区别和map与unordered_map区别类似: set实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,因此map内部所有的...
  • C++ STL 之 unordered_set 使用(包括unordersd_map)

    万次阅读 多人点赞 2018-12-21 12:29:49
    unordered_set可以把它想象成一个集合,它提供了几个函数让我们可以增删查: unordered_set::insert unordered_set::find unordered_set::erase 这个unorder暗示着,这两个头文件中类的底层实现----Hash。 也是因为...
  • 一 unordered_map 底层实现完全由hash表代替,所以没有自动排序,适合用于只查找元素...unordered_set> int main() { unordered_map<int, int> unmap; for (int i = 0; i < 30; i++) { unmap.insert
  • unordered_map&&unordered_set

    2020-02-20 14:51:22
    unordered_set 底层实现 ​ 在STL中,C++11引入了unordered_map、unordered_set、unordered_multimap、unordered_multimap。尽管不是名字不是哈希表,但是底层仍然是。相比于map等,这个查找的平均时间更加快。看看...
  • 中,而unordered_set在头文件#include<unorder_set>中。 (2) map 会按照键值对的键 key 进行排序(set里面会对按照集合中的元素大小进行从小到大的排序),而unordered_map (或者 unordered_set )省去了这...
  • MSVC版本unordered_set和unordered_map容器

    千次阅读 2020-05-15 22:31:00
    文章目录unordered_set容器1. unordered_set容器的概述2. unordered_set容器的构造和赋值3. 刨析_Hash底层原理3.1 存储结构3.2 存储过程4. unordered_set提供的接口5. unordered_multiset容器6. unordered_map和...
  • <p>std::unordered_set and boost::unordered_set have very similar performance. So, we can reduce boost dependency by replacing them. <h4>PR validation: <p>Passed on basic runTheMatrix test. 该提问来源...
  • 这里写目录标题一、unordered_map与map的区别二、unordered_set和set的区别三、总结 一、unordered_map与map的区别 unordered_map和map类似,都是存储的key-value的值,可以通过key快速索引到value。不同的是...
  • unordered_set需要头文件#include <unordered_set> 二者都是基于哈希实现的,无序,因此增删改查的时间复杂度是 O(1),比map和set快,它们是基于平衡二叉树(红黑树)实现的,动态维护有序序列,时间复杂度 O...
  • unordered_set 文章目录模拟实现unordered_map&unordered_set1. std::unordered_map 的定义与特性2. 构造 std::unordered_map:3. 赋值操作4. 迭代器操作5. 容量操作6. 访问操作7. 插入操作8. 删除操作9. 查找...
  • unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。 unordered_set 容器具有以下几个特性: 不再以键值对的形式存储数据,而是直接存储数据的...
  • map、set、unordered_map、unordered_set在C++中使用频率较高的几种数据存储结构,因此,熟练掌握其基本的方法对于深入学习C++就先得尤为重要 1、map 2、set 3、unordered_map 4、unordered_set
  • unordered_set 简介2. unordered_set 使用3. unordered_multiset 简介4. unordered_multiset 使用 1. unordered_set 简介 散列容器(bash container)是一种非常重要的容器类型,它内部使用hash散列表代替二叉树...
  • unordered_map与unordered_set unordered_map与unordered_set大体上与map和set的特性是相同的, 但是unordered系列的关联式容器是无顺序的, 这是因为他的底层结构为哈希表,而且由于哈希表的性能略高于红黑树, 因此...
  • unordered_set用法

    万次阅读 2018-05-31 23:25:41
    unordered_set与与unordered_map相似,这次主要介绍unordered_setunordered_set它的实现基于hashtable,它的结构图仍然可以用下图表示,这时的空白格不在是单个value,而是set中的key与value的数据包有unordered_set就...
  • unordered_set是C++中的哈希,如果想让自定义的class作为key(unordered_set<key,value>)来使用unordered_set,需要实现: (1) 哈希函数,需要实现一个class重载operator(),将自定义class变量映射到一个size...
  • unordered_set使用介绍

    千次阅读 2019-09-17 13:37:10
    unordered_set C++ 11,新的关联容器:unordered_set 基本介绍 set和map内部实现是基于RB-Tree,而unordered_set和unordered_map内部实现是基于哈希表。 unordered_set 容器类型的模板定义在 <unordered_set&...
  • 拿神盾与积木游戏这道题来讲,按照正常情况,我使用了unordered_set和auto,然后结果使劲报错: 解决方法1: 在导入所有的unordered_xx包的时候,添加tr1,然后使用 using namespace std::tr1如: #include<tr1/...
  • unordered_set 是一个封装哈希表的无序容器,其中每个元素仅可出现一次。 unordered_multiset 是一个封装哈希表的无序容器,其中每个元素可出现任意次。 unordered_set 和 unordered_multiset 均定义于头文件 <...
  • 在C++11中,STL又提供了4个unordered系列的关联式容器,这四个容器与红黑树结构的关联式容器使用方式基本类似,只是其底层结构不同,本文中只对unordered_map和unordered_set进行介绍。 一:unordered_map和...
  • set和map基于红黑树,自动排序 unordered_set和unordered_map基于哈希表,无序(unordered) set —— key = value set<x> map —— key + value map<x,y>

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,325
精华内容 1,330
热门标签
关键字:

unordered_set