unordered_mapset

2024-05-26 22:44
文章标签 unordered mapset

本文主要是介绍unordered_mapset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • Ⅰ. 使用
    • a. unordered_map
    • b. unordered_set
  • Ⅱ. 哈希表
    • a. 闭散列：线性探测
      • 1.仿函数，2.插入，3.删除，4.查找，5.扩容
    • b. 开散列：哈希桶
      • 1.仿函数，2.插入，3.删除，4.查找，5.扩容
  • Ⅲ. 封装实现
    • a. HashTable的封装完善
    • b. unordered_set
    • c. unordered_map

前言：unordered_map & unordered_set 是一对关联式容器，与map，set功能上类似，分别是KV，K的模型，其底层的实现是哈希表，所不同的是里边的存储是无序的

Ⅰ. 使用

a. unordered_map

函数名称函数功能
empty()返回表是否为空
size()返回存表中数据的个数
[ K ] & at( K )返回对应的V
find(K)返回迭代器
count(K)返回表中K的个数
insert({K，V})插入一个键值对，返回一个pair<Iterator,bool>
erase(K)删除KV并返回删除K前K的个数
void test_unordered_map1()
{unordered_map<int, int> um;// 1.有名对象构造pair<int, int> e(1, 1);um.insert(e);// 2.匿名对象构造um.insert(pair<int,int>(2,2));// 3.仿函数构造um.insert(make_pair(3, 3));// 4.多参数的隐式类型转换构造um.insert({ 4,4 });// 迭代器遍历unordered_map<int, int>::iterator it = um.begin();while (it != um.end()){cout << it->first << " " << it->second << endl;}cout << endl;// 迭代器遍历for(auto e: um){cout<<e.first<<" "<<e.second()<<endl;}
}

void test_unordered_map2()
{// 最厉害的为属 [ ]unordered_map<string, int> um;string s[] = { "安徽","河北","河南","河南","广东","河南","河南","广东" ,"河南","河南","广东" };for (auto& str : s){um[str]++;}// 这样就把城市的总次数统计出来了for (auto e : um){cout << e.first << " " << e.second << endl;}
}

b. unordered_set

unordered_set的使用和unordere_map的使用基本上类似，感兴趣的可以去看一下文档

C++文档unordered_set
C++文档unordered_map

Ⅱ. 哈希表

哈希表底层就是vector实现的
1. 每个值里边存放一个 pair，还有一个表示 状态信息 的 枚举常量，就是线性探测哈希表
2. vector里边每个值都挂一个 链表 ，就是哈希桶
3. 有了红黑树，为什么还要有哈希表呢？因为哈希表的 插入，删除，查找 三个操作在理论上都是O(1) 的时间复杂度
（数据碰撞除外），因为采用了值与位置的映射的存储关系，而红黑树的插入，查找，删除 理论上是O(logN) （不考
虑旋转变色）

a. 闭散列：线性探测

1.仿函数，2.插入，3.删除，4.查找，5.扩容

  1. 仿函数 ：将一个对象的所有成员进行转换，转为size_t类型，这样方便进行下标的取模操作进而进行哈希映射，比如string 每个字符串ASC码相加返回，负数直接转化为无符号的整形就变为了整数，再比如一个Person类，可以对每个人的名字，身份证，年龄整合返回，这样的两个人对应数组的映射下标的很小概率相同

  2. 插入：将所给的K值与数组下标产生映射关系，将此值存入到此下标处，一般K都是字符串类，整数，都是整形家族的类型，此时就可以使用 %，用仿函数 将此K转为 size_t 类型，然后模上表的长度，找到映射位置，也有可能此处的位置被占，比如 19 9 都去 模表长为10 的位置，那么此时就需要从此下标处开始继续往后找到第一个没有被占用的下标位置，将值放入，并将状态设置为EXIST

  3. 查找：先使用仿函数 映射出下标，可能该处就是所要查找的值 直接返回，要么就进行线性探测继续往后找，状态为空，找不到，状态不为空先判断，判断一下是否是 存在状态 且 里边的值 为所要查找的值，若是，找到了返回，若不是，继续往后找

  4. 删除：调用查找函数，用函数调用返回的指针，将此处的状态改为删除状态，里边的数据不用抹除，因为我们进行的各种操作先判断的就是状态，而且如果抹除该设为多少呢？（抹除为几都不行，因为你下次插入的可能就是这个值）

  5. 扩容机制：当_n 除 表的长度超过 0.7的时候就开始扩容，大于0.7下一次的插入很容易造成哈希碰撞，小与0.7空间利用不充分；开一个新的vector，大小设为原来的二倍，将状态为存在的值，重新取模进行新表的映射，然后于旧的vector交换

#include<vector>enum STate
{EMPTY,EXIST,DELETE,
};template<class K, class V>
struct HashData
{pair<K, V> _kv;STate _state = EXIST;
};template<class K>
struct Hash
{size_t operator()(const K& k){return (size_t)k;}
}; 
template<>
struct Hash<string>
{size_t operator()(const string& s){size_t ret = 0;for (auto ch : s)ret = ret * 131 + ch;return ret;}
};template<class K,class V,class Hash = Hash<K>>
class HashTable
{
public:HashTable(size_t n = 10){_tables.resize(n);}bool insert(const pair<K, V>& kv){if(find(kv.first))return false;if (_n * 10 / _tables.size() >= 7){HashTable<K, V, Hash> newhash(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); ++i){if (_tables[hashi]._state == EXIST)newhash.insert(_tables[hashi]._kv);}_tables.swap(newhash._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){++hashi;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}HashData<K,V>* find(const K& k){Hash hs;size_t hashi = hs(k) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hahsi]._kv.first == k && _tables[hashi]._state == EXIST){return &_tables[hashi];}else{++hashi;hashi %= _tables.size();}}return nullptr;}bool erase(const K& k){HashData<K, V>* ret = find(k);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}}
private:vector<HashData> _tables;size_t _n = 0;
};

b. 开散列：哈希桶

1.仿函数，2.插入，3.删除，4.查找，5.扩容

  1. 仿函数：同线性探测

  2. 插入：用仿函数映射出下标，找到该链表，对链表进行头插（可随便插入，但是头插的效率高）

  3. 删除：用仿函数先映射出下标，找到处于哪个位置的链表，遍历该链表进行此节点的前后链接关系

  4. 查找：用仿函数映射出下标，接下来进行链表的查找

  5. 扩容机制：当所有节点的个数总和 与 vector的大小一样时（负载因子为1），就开始扩容，将每个节点取下来重新映射关系，因为 vector 的空间大小 增大，所以要%一个新表的长度

template<class K,class V>
struct HashNode
{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}
};template<class K,class V,class Mod = KOfMod<K>>
class Hash
{typedef HashNode<K, V> Node;
public:Hash(size_t n = 10){_v.resize(n, nullptr);}~Hash(){for (int i = 0; i < _v.size(); i++){Node* cur = _v[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_v[i] = nullptr;}}bool insert(const pair<K, V>& kv){if (find(kv.first)) return false;Mod mod;if (_n == _v.size()){vector<Node*> newv(_n * 2, nullptr);for (int i = 0; i < _n; i++){Node* cur = _v[i];while (cur){Node* next = cur->_next;size_t hashi = mod(cur->_kv.first) % newv.size();cur->_next = newv[hashi];newv[hashi] = cur;cur = next;}_v[i] = nullptr;}_v.swap(newv);}size_t hashi = mod(kv.first) % _v.size();Node* newnode = new Node(kv);newnode->_next = _v[hashi];_v[hashi] = newnode;_n++;return true;}Node* find(const K& k){Mod mod;size_t hashi = mod(k) % _v.size();Node* cur = _v[hashi];while (cur){if (cur->_kv.first == k){return cur;}cur = cur->_next;}return nullptr;}bool erase(const K& k){Mod mod;size_t hashi = mod(k) % _v.size();Node* prev = nullptr;Node* cur = _v[hashi];while (cur){if (cur->_kv.first == k){Node* next = cur->_next;if (prev == nullptr){_v[hashi] = next;}else{prev->_next = next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _v;size_t _n = 0;
};

Ⅲ. 封装实现

a. HashTable的封装完善

#pragma once#include<vector>
#include<string>namespace hash_bucket
{template<class K>struct Hash{size_t operator()(const K& k){return (size_t)k;}};template<>struct Hash <std::string>{size_t operator()(const std::string& str){size_t ret = 0;for (auto ch : str){ret = ret * 131 + ch;}return ret;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};template<class K, class T, class KeyOfT, class Hash>class HashTable;// 哈希表的前置声明template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>struct __HashTable_Iterator{typedef HashNode<T> Node;typedef __HashTable_Iterator<K, T,Ref,Ptr, KeyOfT, Hash> Self;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;__HashTable_Iterator(Node* node,const HashTable<K, T, KeyOfT, Hash>*pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){KeyOfT kot;Hash hs;if (_node->_next){_node = _node->_next;}else{size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();++hashi;for (; hashi < _pht->_tables.size(); hashi++){Node* cur = _pht->_tables[hashi];if (cur){_node = cur;break;}}if (hashi == _pht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};template<class K,class T,class KeyOfT, class Hash>class HashTable{typedef HashNode<T> Node;public:template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>friend struct __HashTable_Iterator;// 将迭代器设为 友元类，方便找位于表中的位置 实现++typedef __HashTable_Iterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HashTable_Iterator<K, T,const T&,const T*, KeyOfT, Hash> const_iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return const_iterator(cur, this);}}return end();}const_iterator end() const{return const_iterator(nullptr, this);}HashTable(size_t n = 10){_tables.resize(n, nullptr);}pair<iterator,bool> insert(const T& data){KeyOfT kot;iterator ret = find(kot(data));if (ret!=end())return make_pair(ret,false);Hash hs;if (_n == _tables.size()){std::vector<Node*> newtables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode,this), true);}iterator find(const K& k){KeyOfT kot;Hash hs;size_t hashi = hs(k) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == k){return iterator(cur,this);}cur = cur->_next;}return end();}bool erase(const K& k){KeyOfT kot;Hash hs;size_t hashi = hs(k) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == k){Node* next = cur->_next;if (prev == nullptr){_tables[hashi] = next;}else{prev->_next = next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:std::vector<Node*> _tables;size_t _n = 0;};
}

b. unordered_set

#pragma once#include"HashTable.h"
namespace zy
{template<class K>class unordered_set{struct SetKeyOfT{const K& operator()(const K& k){return k;}};public:typedef typename hash_bucket::HashTable<K,const K, SetKeyOfT, hash_bucket::Hash<K>>::iterator iterator;typedef typename hash_bucket::HashTable<K,const K, SetKeyOfT, hash_bucket::Hash<K>>::const_iterator const_iterator;iterator begin(){return _hs.begin();}iterator end(){return _hs.end();}const_iterator begin() const{return _hs.begin();}const_iterator end() const{return _hs.end();}pair<iterator,bool> insert(const K& k){return _hs.insert(k);}iterator find(const K& k){return _hs.find(k);}bool erase(const K& k){return _hs.erase(k);}private:hash_bucket::HashTable<K,const K,SetKeyOfT,hash_bucket::Hash<K>> _hs;};void test_unordered_set1(){unordered_set<int> s;s.insert(1001);s.insert(11);s.insert(12);s.insert(23);}void test_unordered_set2(){string s[] = { "sort","left","right" };unordered_set<string> st;for (auto e : s){st.insert(e);}st.insert("parent");st.insert( "parent");}void test_unordered_set3(){unordered_set<int> s;s.insert(1);s.insert(12);s.insert(13);s.insert(21);unordered_set<int>::iterator cit1 = s.begin();unordered_set<int>::const_iterator cit2 = s.begin();}
}

c. unordered_map

#pragma once#include"HashTable.h"
namespace zy
{template<class K , class V>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, hash_bucket::Hash<K>>::iterator iterator;typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, hash_bucket::Hash<K>>::const_iterator const_iterator;iterator begin(){return _hs.begin();}iterator end(){return _hs.end();}const_iterator begin() const{return _hs.begin();}const_iterator end() const{return _hs.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _hs.insert(kv);}iterator find(const K& k){return _hs.find(k);}bool erase(const K& k){return _hs.erase(k);}V& operator[](const K& k){pair<iterator, bool> ret = _hs.insert(make_pair(k, V()));return ret.first->second;}private:hash_bucket::HashTable<K, std::pair<const K, V>,MapKeyOfT,hash_bucket::Hash<K>> _hs;};void test_unordered_map1(){int a[] = { 10001,12,13,25 };unordered_map<int, int> m;for (auto e : a){m.insert({ e,e });}m.insert({ 12,12 });for (auto e : m){cout << e.first << " " << e.second << endl;}}void test_unordered_map2(){string s[] = { "sort","left","right" };unordered_map<string, int> m;for (auto e : s){m.insert({ e,1 });}m.insert({ "parent",1 });m.insert({ "parent",1});for (auto e : m){cout << e.first << " " << e.second << endl;}}void func(const unordered_map<int, int>& m){unordered_map<int, int>::const_iterator it = m.begin();while (it != m.end()){cout << it->first << " " << it->second << endl;++it;}}void test_unordered_map3(){int a[] = { 10001,12,13,25 };unordered_map<int, int> m;for (auto e : a){m.insert({ e,e });}m.insert({ 12,12 });func(m);}void test_unordered_map4(){string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}unordered_map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;++it;}}
}

这篇关于unordered_mapset的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1005797。

相关文章

C++数据结构重要知识点（5）（哈希表、unordered_map和unordered_set封装）

C++数据结构重要知识点（5）（哈希表、unordered_map和unordered_set封装）

1.哈希思想和哈希表 （1）哈希思想和哈希表的区别 哈希（散列、hash）是一种映射思想，本质上是值和值建立映射关系，key-value就使用了这种思想。哈希表（散列表，数据结构），主要功能是值和存储位置建立映射关系，它通过key-value模型中的key来定位数组的下标，将value存进该位置。 哈希思想和哈希表数据结构这两个概念要分清，哈希是哈希表的核心思想。 （2）unordered
阅读更多...
【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set

【C++STL(十四)】一个哈希桶简单模拟实现unordered_map/set

目录 前言 一、改造哈希桶 改造结点类 改造主体  模板参数改造  迭代器(重点) 改造完整哈希桶 unordered_map模拟实现 unordered_set模拟实现 前言 前面的文章都有说unordered_map/set的底层结构就是哈希表，严格来说是哈希桶，那么接下来我们就尝试使用同一个哈希桶来模拟实现一下。整体的逻辑和一棵红黑树封装map/set类似，所以
阅读更多...
详解map、multimap、unordered_map、unordered_multimap

详解map、multimap、unordered_map、unordered_multimap

详解map、multimap、unordered_map、unordered_multimap 相信有不少同学和我一样刚接触C++ STL，被其深深吸引。但是想弄懂每个模板类不是一个容易事。大家应该对vector、list、stack、queue等类比较了解了，所以今天详细介绍下几个很常用很强大但有点不太好懂的类map、multimap、unordered_map、unordered_m
阅读更多...
c++ unordered_set的count方法

c++ unordered_set的count方法

在 C++ 的 std::unordered_set 中，count 方法用于返回集合中与指定值相等的元素的数量。由于 unordered_set 的特性是只允许唯一元素，因此对于任何给定元素，count 方法的返回值只能是 0 或 1。 语法 size_t count(const Key& key) const; key: 要查找的元素。返回值: 如果集合中存在这个元素，返回 1；如果不
阅读更多...
【C++】unordered_set 容器的最全解析（什么是unordered_set?unordered_set的常用接口有那些？）

【C++】unordered_set 容器的最全解析（什么是unordered_set?unordered_set的常用接口有那些？）

目录 一、前言  二、预备知识  💢关联式容器💢  💢键值对💢   💢哈希结构的关联式容器💢   三、unordered_set 详解   🔥unordered_set 的介绍  🔥unordered_set 的构造  🔥unordered_set 的使用  🥝 insert 🍇find  🍍 erase 🍉size  🍋empty  🍓
阅读更多...
【C++STL详解(十三)】unordered系列容器的介绍与使用

【C++STL详解(十三)】unordered系列容器的介绍与使用

目录 前言 一、unordered_map 介绍 使用  构造方式 修改  容量 迭代器 元素访问 查询 桶操作  二、unordered_set 介绍 使用 构造 修改 容量  迭代器（只有单向) 查询 桶操作  三、unordered系列的性能测试 前言 前面提到的map/set是C++98提供的关联式容器，底层结构是红黑树，最差情况下需
阅读更多...
【C++ 第十七章】封装 unordered_map / unordered_set

【C++ 第十七章】封装 unordered_map / unordered_set

声明：上一章讲解了 哈希结构的原理与实现，本章主要将上一章学过的拉链法的哈希结构封装进 unordered_map / unordered_set，所以需要先学过相关知识，才能更好吸收本章知识 上一章的链接：【C++ 第十六章】哈希 1. unordered_map / unordered_set 的 基本结构 之前封装 map 和 set 时，因为 map 的数
阅读更多...
模拟实现STL中的unordered_map和unordered_set

模拟实现STL中的unordered_map和unordered_set

目录 1.unordered_map和unordered_set简介 2.unordered_map和unordered_set设计图 3.迭代器的设计 4.哈希表的设计 5.my_unordered_map和my_unordered_set代码 1.unordered_map和unordered_set简介 unordered_map和unordered_set的使用非常类似于ma
阅读更多...
STL--unordered_set和unordered_map的模拟实现

STL--unordered_set和unordered_map的模拟实现

1.unordered系列关联式容器 在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，在C++11中，STL又提供了4个unordered系列的关联式容器：unordered_map、unordered_set、unordered_mu
阅读更多...
std::unordered_map主键为结构体

std::unordered_map主键为结构体

std::unordered_map为hashmap，如果直接使用结构体作为key值，编译时会报错，需要自己定义结构体的hash值的计算方法。 // 自定义结构体struct MyStruct {size_t handle;size_t getHashValue() {return handle;}}// 定义结构体的hash值计算方法template<>struct std::hash
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2