C++STL详解(10) -- 使用哈希表封装unordered_set和unordered_map

news/2024/3/29 8:57:48/文章来源:https://blog.csdn.net/m0_63300413/article/details/130352064

文章目录

  • 哈希表模板参数改造
    • 针对模板参数V改造
    • 增加仿函数获取具体数据类型.
  • 哈希表的正向迭代器
    • 正向迭代器中的内置成员:
    • 正向迭代器的成员函数
  • 哈希表插入函数的修改(适用于unordered_map)
  • 一个类型K去做set和unordered_set他的模板参数的必备条件.
  • unordered_set的模拟实现(完整代码)
  • unordered_map的实现(完整代码)
  • 适用于unordered_set和unordered_map的哈希表代码

哈希表模板参数改造

针对模板参数V改造

因为不同容器的类型不同,如果是unordered_map,V代表一个键值对,如果unordered_set,V代表Key值,而底层哈希表并不知道上层容器所要传递的
V模板参数类型,为了与哈希表的模板参数区分,我们将哈希表中的V模板参
数改为T.
在这里插入图片描述

增加仿函数获取具体数据类型.

例如: 在哈希表中当我们使用Find函数进行查找时:
如果上层传递的数据类型为Key值,我们就可以直接与查找数据比较.
如果上层传递的数据类型为pair<K,V>键值对,我们就不可以直接比较,需要利用仿函数获取键值对的first进行比较.
unordered_set仿函数SetKeyOfT代码:

struct SetKeyOfT              //根据map还是set传递不同数据类型给底层.{const K& operator()(const K& key){return key;}};

unordered_map仿函数MapKeyOfT代码:

struct MapKeyOfT                   //根据map还是set传递不同数据类型给底层.{const K& operator()(const pair<K, V>& kv){return kv.first;   //获取pair<K,V>键值对中的first.}};

所以,我们要在哈希表模板参数中增加一个仿函数KeyOfT.
如果是unordered_set,就传 SetKeyOfT类型的仿函数.
如果是unordered_map,就传MapKeyOfT类型的仿函数.

模板参数转换图示如下:
在这里插入图片描述
额外说明:
1: 我们对原先哈希表中的Hash进行了修改,不要缺省值,因为我们肯定是使用上层容器传递不同的仿函数类型,所以在unordered_set与unordered_map中传递仿函数类型.

哈希表的正向迭代器

正向迭代器中的内置成员:

哈希表正向迭代器有两个内置成员:
1: 结点指针
2: 哈希表的指针


template < class K, class T, class Hash, class KeyOfT >
class HashTable;                   //重新声明哈希表类模板.
//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{typedef HashNode<T> Node; //重新定义哈希结点的类型为Node.typedef HashTable<K, T, KeyOfT, HashFunc> HT; //重新定义哈希表的类型为HT.typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //重新定义正向迭代器的类型为Self.Node* _node; //结点指针HT* _pht; //哈希表指针
};

注意:
因为迭代器中要使用到哈希表类型,所以我们在哈希表迭代器前面必须声明一下哈希表类模板.

正向迭代器的成员函数

以下成员函数较为简单,就不另外说明:

_HashIterator( Node* node,HT* pht )  //初始化列表:_node(node), _pht(pht){}T& operator*()                     //解引用运算符重载{return _node->_data;}T* operator->()                 //->运算符重载{return &_node->_data;}bool operator!=( const Self& s ) const  //外面增加const可以使const对象也能调用该成员函数.{return _node != s._node;  //实质上是迭代器中的_node比较}bool operator==( const Self& s )const {return _node == s._node;}

前置++运算符重载:
前置++运算符重载主要有两个步骤:
1: 如果当前结点指针的下一个结点存在,则结点指针指向下一个结点.

2: 如果当前结点指针的下一个结点不存在:
(1): 通过哈希函数计算哈希桶的位置.

(2): 在哈希表中,从哈希桶中的下一个位置开始遍历查找.
如果哈希桶存在,则将结点指针指向该哈希桶.
如果哈希表遍历完还没有找到,则说明这是哈希表中的最后一个数据的迭代器,则结点指针指向空,表明最后一个数据的下一个结点.

Self& operator++(){if (_node->_next)  //在当前桶中迭代{_node = _node->_next;}//如果该哈希桶迭代完毕,则在哈希表中找下一个哈希桶迭代寻找.else{KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器访问哈希表的私有成员size_t i = hashi + 1;for (;  i < _pht->_table.size(); ++i){if (_pht->_table[i]){_node = _pht->_table[i];break;                       //++完就退出.}}if (i == _pht->_table.size())        //此时,这也说明正式哈希桶迭代器的end.{_node = nullptr;}}return *this;}

哈希表插入函数的修改(适用于unordered_map)

为了支持unordered_map中的[]操作符重载,我们针对哈希表中的插入函数返回值进行修改
(1): 如果哈希表中已有所给数据,则返回已有数据的迭代器与插入结果(失败)所构成的键值对.

(2): 如果哈希表没有所给数据,则将新数据头插该哈希桶组成的单链表上,返回新插入结点指针构造与插入结果(成功)组成的键值对.

插入函数代码如下:

pair< Iterator,bool> Insert(const T& data){Hash hash;KeyOfT kot;		                                                   Iterator ret = Find(kot(data));                    if (ret != end()){return make_pair( ret, false);}if (_size == _table.size())                                //扩容.{//	size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();vector<Node*> newTable;newTable.resize(GetNextPrime(_table.size()), nullptr); Hash hash;//从旧表结点移动映射新表.for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = hash(kot(data)) % _table.size();Node* newNode = new Node(data);newNode->_next = _table[hashi];_table[hashi] = newNode;++_size;return make_pair(Iterator(newNode,this),true);                //如果是新插入的数据,则返回新插入结点构造的迭代器与插入结果组成的pair.}

一个类型K去做set和unordered_set他的模板参数的必备条件.

set容器模板参数:
(1):set模板参数要求能够支持小于比较,例如:二叉搜索树查找成员函数中,我们可以利用compare仿函数将当前结点值与所给值比较,从而决定cur遍历左子树还是右子树,为了能够支持大于比较的,我们可以交换一下实参位置,这也间接支持了大于比较.并且条件判断,进而也支持了等于.
unordered_set容器模板参数要求:
(1)针对于K类型(指针,打浮点数,有符号整型)可以转换为无符号整数取模.对于string,日期类类型,这两个类型与整型类型无关的,此时不可以直接强转为整数,需要相应的提供将该类型转换为整数的仿函数.

(2):K类型对象能够支持等于比较(因为在查找中就是要确定存储的对象与所传的对象是否相等,例如Data日期类),如果不支持需要额外提供等于比较的仿函数.

unordered_set的模拟实现(完整代码)

在上述中,我们已经将unordered_set重点内容讲解完毕,剩下的成员函数只需要复用哈希表中的就可以了.

namespace yzh
{//2:因为我们使用map,set是将实参传给,map,set的所以当string类型取模时要在map,set中写仿函数.template < class K,class Hash = HashFunc<K>> //1:由第二个模板参数决定要存储的数据.class unordered_set{struct SetKeyOfT                                  //根据map还是set传递不同数据类型给底层.{const K& operator()(const K& key){return key;}};public:typedef typename HashBucket::HashTable< K,K,Hash,SetKeyOfT>::Iterator iterator;  //重新定义一下迭代器类型为iterator.iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator,bool> Insert(const K& key){return _ht.Insert(key);}private:HashBucket::HashTable<K,K,Hash,SetKeyOfT> _ht;};void test_set()                      //测试{unordered_set<int> set;set.Insert(1);set.Insert(2);set.Insert(3);unordered_set<int>::iterator it = set.begin();while ( it != set.end() ){cout << *it << " ";++it;}cout << endl;}}

unordered_map的实现(完整代码)

在上述中,我们已经将unordered_map重点内容讲解完毕,剩下的成员函数只需要复用哈希表中的就可以了.

namespace yzh
{template < class K, class V, class Hash = HashFunc<K> >            //由第二个模板参数决定要存储的数据类型,class unordered_map{struct MapKeyOfT                                             //根据map还是set传递不同数据类型给底层.{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashBucket::HashTable< K, pair<K, V>, Hash, MapKeyOfT>::Iterator iterator;//重新定义一下迭代器类型为iterator.iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator,bool> Insert( const pair<K, V>& kv ){return _ht.Insert(kv);}V& operator[]( const K& key  )                      //给一个key,返回V的引用.{pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));   //如果插入失败,返回已有数据的迭代器与返回结果组成的pair.                                                 //如果插入成功,返回新插入数据的迭代器与返回结果组成的pair.return ret.first->second;}private:HashBucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;     //map和set都知道传递什么来类型的仿函数,以及要传递的数据类型.};void test_map(){unordered_map<string, string> dict;dict.Insert(make_pair("sort", "排序"));dict.Insert(make_pair("string", "排序"));unordered_map<string,string>::iterator it = dict.begin();while (it != dict.end()){cout << it->first << ":" << it->second  << endl;++it;}}void testmap1(){unordered_map<string, int> countMap;string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","西瓜","苹果","香蕉" };for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}}

适用于unordered_set和unordered_map的哈希表代码

#include <map>
#include <vector>
#include <string>
#include <string>
#include <iostream>
using namespace std;
template < class K >                   //仿函数的默认值,如果不显示传就会默认调用.
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template< >                                 //1:对于常见类型,为了方便,我们可以对类模板进行特化.
struct HashFunc <string>                    //并且根据实参所传类型,优先走特化版本.	                                     
{size_t operator()(const string& key){size_t  val = 0;for (auto& ch : key) //遍历string,将一个个字母替换成ASCI码进行相加.{val += ch;}return val;}
};
namespace HashBucket
{template < class T >struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template < class K, class T, class Hash, class KeyOfT >class HashTable;template < class K, class T, class Hash, class KeyOfT >struct _HashIterator{typedef HashNode<T> Node;typedef HashTable< K, T, Hash, KeyOfT> HT;typedef _HashIterator< K, T, Hash, KeyOfT> Self;Node* _node;HT* _pht;_HashIterator( Node* node,HT* pht ):_node(node), _pht(pht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_next)  //在当前桶中迭代{_node = _node->_next;}//如果该哈希桶迭代完毕,则在哈希表中找下一个哈希桶迭代寻找.else{KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _pht->_table.size(); //迭代器访问哈希表的私有成员size_t i = hashi + 1;for (;  i < _pht->_table.size(); ++i){if (_pht->_table[i]){_node = _pht->_table[i];break;                       //++完就退出.}}if (i == _pht->_table.size())        //此时,这也说明正式哈希桶迭代器的end.{_node = nullptr;}}return *this;}bool operator!=( const Self& s ) const{return _node != s._node;}bool operator==( const Self& s )const {return _node == s._node;}};template < class K, class T, class Hash, class KeyOfT >struct HashTable{typedef HashNode<T> Node;template < class K, class T, class Hash, class KeyOfT > //为了迭代器能够访问哈希表的私有成员,我们设为迭代器是哈希表的//友元,类模板声明友元需要增加类模板.friend struct  _HashIterator;public:typedef _HashIterator< K, T, Hash, KeyOfT> Iterator;Iterator begin()//获取第一个迭代器{for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){return Iterator( _table[i], this );}}return end();}Iterator end()  //获取最后一个迭代器{return Iterator(nullptr, this);}size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;//素数序列const size_t primeList[PRIMECOUNT] ={53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)         //从这个数组里面取第一个大于prime的值.return primeList[i];}return primeList[i];                 //虽然数据不可能那么大,但是也有可能不会走if判断,// 所以从语法上来说还要考虑所给值prime大于素数数组整个数据的情况.}~HashTable()         //vvector会调用析构函数,但是哈希桶必须自己写.{for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_table[i] = nullptr;}//	cout << "~HushTable()" << endl;}bool  Erase(const K& key){if (_table.size() == 0){return true;}Hash hash;size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}pair< Iterator,bool> Insert(const T& data){Hash hash;KeyOfT kot;//去重Iterator ret = Find(kot(data));                    //如果该数据已经有了,则返回已有数据的迭代器与插入结果构成的pair.if (ret != end()){return make_pair( ret, false);}if (_size == _table.size())                                //扩容.{//	size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();vector<Node*> newTable;newTable.resize(GetNextPrime(_table.size()), nullptr);    //扩容Hash hash;//从旧表结点移动映射新表.for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashi = hash(kot(data)) % _table.size();Node* newNode = new Node(data);newNode->_next = _table[hashi];_table[hashi] = newNode;++_size;return make_pair(Iterator(newNode,this),true);                //如果是新插入的数据,则返回新插入结点构造的迭代器与插入结果组成的pair.}Iterator Find(const K& key){if (_table.size() == 0)        //表为空,就返回nullptr.{return end();}Hash hash;KeyOfT kot;size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return Iterator(cur, this);}cur = cur->_next;}return end();}size_t size(){return _size;}size_t TablesSize()          //表的长度{return  _table.size();}size_t BucketNum()           //有多少个桶被用了.{size_t Num = 0;for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){++Num;}}return Num;}size_t MaxBucketLenth(){size_t maxLen = 0;for (size_t i = 0; i < _table.size(); ++i){size_t len = 0;Node* cur = _table[i];while (cur){++len;cur = cur->_next;}if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _table;size_t _size = 0;};
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_103284.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PySide6/PyQT多线程的使用

前言 上一篇文章介绍了在PySide6中使用多线程去解决PySide6/PyQT的界面卡死问题&#xff0c;这次来具体介绍下多线程在使用上的一些细节。 本文尝试对以下两个问题进行解决&#xff1a; 对 PySide6/PyQT 多线程的使用不熟悉&#xff1b;在 PySide6/PyQT 的应用程序里有耗时任…

【Linux基础IO之 内存文件操作】

目录&#xff1a; 前言一、引入C语言中的文件操作系统文件操作open 位图权限close、write、readlseek C语言中的文件操作函数与系统文件操作函数的联系 三、文件描述符1.文件描述符是什么2.文件缓冲区再谈重定向 四、文件缓冲区分类语言级缓冲区为什么要有两个缓冲区 五、仿写c…

OpenGL入门教程之 变换

引言 这是一个闪耀的时刻&#xff0c;因为我们即将能生产出令人惊叹的3D效果&#xff01; 变换 向量和矩阵变换包括太多内容&#xff0c;但由于学过线性代数和GAMES101&#xff0c;因此不在此做过多阐述。仅阐述包括代码的GLM内容。 GLM的使用 &#xff08;1&#xff09;GLM…

8、接口的高级用法

1、索引类型 我们可以使用接口描述索引的类型和通过索引得到的值的类型&#xff0c;比如一个数组[‘a’, ‘b’]&#xff0c;数字索引0对应的通过索引得到的值为’a’。我们可以同时给索引和值都设置类型&#xff0c;看下面的示例&#xff1a; interface RoleDic {[id: number…

Pinia与Vuex区别、Pinia安装与使用

目录 一、Pinia和Vuex区别 二、Pinia使用state、getters、actions 1、安装使用Pinia 2、State 3、actions 4、getters 三、Pinia划分模块 1、目录结构 2、store/user.js 3、某组件使用 四、Pinia持久化存储 1、安装插件 2、store/index.js 3、store/user.js 4、…

收废品小程序开发中的常见问题及解决方法

常见问题 1. 用户界面设计 小程序的用户界面设计至关重要。设计师需要在用户界面中提供清晰的指示&#xff0c;以便用户可以轻松地找到他们需要的功能。同时&#xff0c;设计师还需要确保用户界面的整体风格与公司的品牌形象相符。 2. 功能开发 开发小程序的功能需要考虑到…

5G网络切片路由选择策略介绍

终端保存的NSSP(Network Slice Selection Policy)策略来源于网络侧。 NSSP规则是将应用程序匹配到S-NSSAI(Single network slice selection assistance information),并将应用程序绑定到现有PDU会话或发起新的PDU会话。 NSSP功能 NSSP的作用就是为应用程序选择S-NSSAI和…

堆的原理解析

看这篇文章需要对比较器有一定的了解&#xff0c;可以看我的这篇文章&#xff1a; 认识比较器_鱼跃鹰飞的博客-CSDN博客 堆的实际存储方式是数组&#xff0c;但是脑海中应该把他想象成一种树的结构 依次加入下标0-8的9个数&#xff08;添加过程中会不断的和父节点大小进行比…

QT Graphics View 绘图架构之场景、视图与图形项简介

1、场景、视图与图形项 采用QPainter 绘图时需要在绘图设备的 paintEvent()事件里编写绘图的程序&#xff0c;实现整个绘图过程。这种方法如同使用 Windows 的画图软件在绘图&#xff0c;绘制的图形是位图&#xff0c;这种方法适合于绘制复杂性不高的固定图形&#xff0c;不能…

基于ResNet-attention的负荷预测

一、attention机制 注意力模型最近几年在深度学习各个领域被广泛使用&#xff0c;无论是图像处理、语音识别还是自然语言处理的各种不同类型的任务中&#xff0c;都很容易遇到注意力模型的身影。从注意力模型的命名方式看&#xff0c;很明显其借鉴了人类的注意力机制。我们来看…

机器人教学中游戏化课程案例尝试

本文内容严格按创作模板发布&#xff1a; 2023年LPL春季赛季后赛正在火热进行中&#xff0c;你们心中的总冠军是哪支队伍呢&#xff1f;作为热爱游戏的程序猿&#xff0c;一起来聊聊你那些有意义的游戏开发经历吧&#xff01; 游戏化ROS机器人课程的优势有以下七点&#xff1a…

android studio RadioButton单选按钮

1.定义 <!--单选按钮--> <TextViewandroid:layout_marginTop"10dp"android:layout_width"match_parent"android:layout_height"wrap_content"android:text"请选择你的性别&#xff1a;"> </TextView> <RadioGrou…

首发支持NOA的单征程3行泊一体域控,这家Tier1开“卷”

NOA正成为智能驾驶下半场的竞争焦点之一。 显然&#xff0c;NOA所处的L2/L2区间&#xff0c;在技术上仍然属于驾驶辅助领域&#xff0c;但在传统L2级ADAS功能的基础上增强了部分场景的功能ODD。在部分政策允许的国家和地区&#xff0c;可以实现有条件的「解放双手」。 高工智…

最佳实践|如何写出简单高效的 Flink SQL?

摘要&#xff1a;本文整理自阿里巴巴高级技术专家、Apache Flink PMC 贺小令&#xff0c;在 Flink Forward Asia 2022 生产实践专场的分享。本篇内容主要分为三个部分&#xff1a; 1. Flink SQL Insight 2. Best Practices 3. Future Works Tips&#xff1a;点击「阅读原文」查…

【Linux】一文读懂HTTP协议:从原理到应用

​&#x1f320; 作者&#xff1a;阿亮joy. &#x1f386;专栏&#xff1a;《学会Linux》 &#x1f387; 座右铭&#xff1a;每个优秀的人都有一段沉默的时光&#xff0c;那段时光是付出了很多努力却得不到结果的日子&#xff0c;我们把它叫做扎根 目录 &#x1f449;HTTP协议…

机器人工程师与孔乙己文学

本文内容严格按创作模板发布&#xff1a; 孔乙已是鲁迅笔下人物&#xff0c;穷困流倒还穿着象征读书人的长衫&#xff0c;迁腐、麻木。最近&#xff0c;大家自我调佩是“当代孔乙己”&#xff0c;学历成为思想负担&#xff0c;找工作时高不成低不就。你可以从以下几个角度说说…

Android---启动页+闪屏页

目录 启动页 闪屏页 启动页 app 在进入首页面的过程中&#xff0c;都会线加载一张图片然后再进入闪屏页。这样&#xff0c;可以给用户很好的体验。 作用&#xff1a;避免加载白屏页面&#xff0c;进行业务的预处理&#xff08;网络检测、数据预加载...&#xff09; 界面组成…

一款纯Web化免费SQL工具,重新定义数据库管理

SQL Studio是一款由麦聪软件研发的多数据库管理工具&#xff0c;提供Windows、Linux 和 MacOS三种版本的软件包&#xff0c;支持中英文两种语言。SQL Studio是用Java编写的&#xff0c;默认使用 JDK 8进行编译。 下载看这里: [SQLStudio] (http://www.maicongs.com/#/home/web)…

.Net Framework 4.6.1+版本的Winform程序开启Web服务,支持Http webapi

Winform程序开启Web服务 背景思路方法1方法2方法3&#xff08;本文使用的方法&#xff09; 实现在winform程序中引入几个nuget包新建一个Startup类&#xff08;叫什么名字都行&#xff09;修改Program文件创建controller 运行效果(打开浏览器&#xff0c;输入如下地址&#xff…

ThinkPHP模型操作上

ThinkPHP模型操作上 前言模型一、创建模型二、模型操作 总结 前言 在mvc架构中&#xff0c;模型的解释是写逻辑代码的地方&#xff0c;其实还可以这样理解&#xff0c;就是一串操作写在一个模型类中&#xff0c;就是你要完成某一项功能&#xff0c;将这个功能的代码写在一个mod…