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++11 之新增容器 array、foward_list、tuple、unordered_(multi)map/set】应知应会

【C++11 之新增容器 array、foward_list、tuple、unordered_(multi)map/set】应知应会

C++11 标准中新增了多个容器，这些容器为 C++ 程序员提供了更多的选择，以满足不同的编程需求。以下是对这些新容器的介绍和使用案例： std::array 介绍： std::array 是一个固定大小的数组容器，它在栈上分配内存，并提供了类似于标准库容器的接口。它提供了更好的类型安全性和范围检查，同时保持了与原生数组相似的性能。std::array 的大小必须在编译时确定，并且不能更改。
阅读更多...
C++ 关联容器使用 map, unordered_map, set, unordered_set, multiset, unordered_multiset

C++ 关联容器使用 map, unordered_map, set, unordered_set, multiset, unordered_multiset

关联容器是否有序是否关联值是否可重复访问时间set是否否对数map是是否对数multiset是否是对数multimap是是是对数unordered_map否是否常数unordered_set否否否常数unordered_multiset否否是常数unordered_multimap否是是常数 #include <map>#include <set>#i
阅读更多...
C++——unordered_map讲解

C++——unordered_map讲解

文章目录 unordered_map讲解1. 引入头文件2. 基本概念3. 声明和初始化4. 基本操作插入元素访问元素删除元素查找元素迭代器 5. 注意事项6. 总结 unordered_map讲解 <unordered_map> 是 C++ 标准库中的一个头文件，提供了哈希表的实现，即无序关联容器。std::unordered_map 是一种关联容器，它使用哈希表来存储键值
阅读更多...
C++中map，hash_map,unordered_map,unordered_set区别与联系

C++中map，hash_map,unordered_map,unordered_set区别与联系

一、hash_map、unordered_map 这两个的内部结构都是采用哈希表来实现。区别在哪里？unordered_map在C++11的时候被引入标准库了，而hash_map没有，所以建议还是使用unordered_map比较好。 哈希表的好处是什么？查询平均时间是O(1)。顾名思义，unordered，就是无序了。无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈
阅读更多...
离散化——unordered_map

离散化——unordered_map

学习一下unordered_map的用法，上海区域赛前才第一次见这个东西，看到和map用法一样自信觉得能用，然而场上卡住了，现在滚过来学一下orz【虽然事后发现G题根本不需要用这个东西。 学过哈希的都很容易理解离散化，无非就是数据过大开不了那么大的数组时，但其实中间有很多浪费掉的空间，那么映射到另一个数组中就可以了。 以前常用的c++离散化是 // a[i] 为初始数组,下标范围为 [1,
阅读更多...
C++|哈希结构封装unordered_set和unordered_map

C++|哈希结构封装unordered_set和unordered_map

上一篇章，学习了unordered系列容器的使用，以及哈希结构，那么这一篇章将通过哈希结构来封装unordered系列容器，来进一步的学习他们的使用以及理解为何是如此使用。其实，哈希表的封装方式和红黑树的封装方式形式上是差不多的，如果有了红黑树的封装理解经验，我相信在理解哈希封装的过程会减少负担的。当然，在使用哈希结构中采用的是更具代表的哈希桶，接下来进行封装。 一、改造哈希表 1.1模
阅读更多...
c++|unordered系列关联式容器(unordered_set、unordered_map介绍使用+哈希结构)

c++|unordered系列关联式容器(unordered_set、unordered_map介绍使用+哈希结构)

目录 一、unordered_set的介绍与使用  1.1unordered_set介绍 1.2unordered_set使用  2.2.1构造   2.2.2容量  2.2.3修改 二、unordered_map的介绍与使用 2.1unordered_map介绍 2.2unordered_map使用  2.2.1构造  2.2.2容量  2.2.3修改   三、底层结构
阅读更多...
c++ 哈希 unordered_map unordered_set 的学习

c++ 哈希 unordered_map unordered_set 的学习

1. unordered 系列 在 c++98 中， STL 提供了底层是红黑树结构的一系列关联式容器，set 和 map 的查询效率可以达到 log2N，红黑树最差的情况也只是需要比较红黑树的高度次，当节点数量非常多时，查找一个节点还需要比较几十次，效果也不是太理想，最理想的查询是，进行很少次的比较次数就能将元素找到。 因此在 c++11 中，STL 又提供了 unordered 系列，uno
阅读更多...
Linux下map hash_map和unordered_map效率比较

Linux下map hash_map和unordered_map效率比较

原理介绍 map介绍 Map是STL[1]的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树（一种非严格意义上的平衡二叉树），这颗树具有对数据自动排序的功能，所以在map内部所
阅读更多...
c++中 unordered_map 与 unordered_set 用法指南

c++中 unordered_map 与 unordered_set 用法指南

unordered_map 与 unordered_set 区别与联系 unordered_map 和 unordered_set 都是 C++ 标准模板库（STL）中的容器，它们使用哈希表作为底层数据结构，提供了快速的查找、插入和删除操作。下面是它们之间的联系与区别： 联系 底层实现：两者都基于哈希表实现，利用了哈希函数来分布元素。性能特点：它们都提供平均时间复杂度为 O(1) 的查找、插入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2