当前位置： 首页 > news >正文

【C++】封装unordered_set和unordered_map

news 2025/5/5 6:53:02

目录

前言：

一：修改参数

二：实现迭代器

三：实现++运算符重载

四：其他运算符的重载

五：实现begin和end

六：实现const类型迭代器 

七：修改Insert返回值

八：重载map的 [ ] 

九：修改HashFunc仿函数

总结：

前言：

我们之前已经讲到过哈希表是如何实现了，相信追剧的小伙伴C++功底已经突飞猛进了，在底层中，不仅有map和set，还有unordered_set和unordered_map，底层正是用我们之前写的哈希表实现的(本篇会跳过很多细节，因为之前已经讲过封装，可以看这篇博客：【C++】通过红黑树封装map和set-CSDN博客)。

这里我们就用之前的哈希表代码，继续在上面封装，将其封装为unordered_set和unordered_map。和红黑树封装一样，内容劲爆，老铁焖做好心理准备，我们开始了！

一：修改参数

还是和之前一样，这里已经做好了它们的头文件，之后需要三个参数，而对于HashTable需要再多加一个模板参数，也就是KeyOfT。KeyOfT的作用就是找是K还是pair的first。我们给出unorderedSet头文件代码：

#pragma once
#include"myHash.h"namespace bit
{template<class K>class unordered_set{public:struct SetOfK{const K& operator()(const K& key){return key;}};//插入函数bool insert(const K& key){return _ht.Insert(key);}//删除函数bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, K, SetOfK> _ht;};
}

map如下：

#include"myHash.h"namespace bit
{template<class K, class V>class unordered_map{public:struct MapOfK{const K& operator()(const pair<K, V>& kv){return kv.first;}};//插入函数bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}//删除函数bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<K, V>, MapOfK> _ht;};
}

这里修改参数应该难不倒各位同学，接下来我们实现迭代器。

二：实现迭代器

我们已经有了之前的经验，迭代器我们通过一个类来实现，所以这次我们直接声明迭代器类(本质还是指针)。

template<class T>
struct HashTableIterator
{using Node = HashNode<T>;using Self = HashTableIterator; //这里可以不写模板参数//构造函数HashTableIterator(Node* node): _node(node){}Node* _node;
};

三：实现++运算符重载

我们是否可以直接让_node = _node->_next就行了呢？

可以看出，这样不行，当前链表走完了，下一步怎么办？此时我们还没有拿到哈希表最开始位置的指针，这时我们需要将哈希表对象指针传递过来。 

template<class T>
struct HashTableIterator
{using Node = HashNode<T>;using Self = HashTableIterator; //这里可以不写模板参数HashTable<K, T, KeyOfT>* _pht;//构造函数HashTableIterator(Node* node): _node(node){}Node* _node;
};

这里是不行的，首先迭代器中的HashTable的这些模板参数根本无法获取，我们必须在HashTableIterator的模板参数中提供。但是此时我们的HashTable在迭代器下方声明定义，编译器器无法识别，所以要在其上面添加其声明。最后我们就算拿到了HashTable的指针，但是我们无法访问其私有成员_table，所以在HashTable中将其声明为友元函数。

并且修改迭代器的构造方法，使其能拿到对应指针；当然因为会重新计算hashi，所以我们需要增加KeyOfT的实例化对象，这里就是kot。

而且我们上面声明了HashTable，在迭代器中使用就要把所有参数都加上，所以我们需要给迭代器再多加一个模板参数——Hash；当然不排除string类型，把Hash也实例化一个对象hs。

//声明HashTable 此时模板参数不需要加缺省值
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct HashTableIterator
{using Node = HashNode<T>;using Self = HashTableIterator; //这里可以不写模板参数KeyOfT kot; //为了计算hashiHash hs;HashTable<K, T, KeyOfT, Hash>* _pht;//构造函数HashTableIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht): _node(node), _pht(pht){}Node* _node;
};

在HashTable中添加声明友元类(先写模板参数，之后友元声明)：

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
public:using Node = HashNode<T>;//声明成友元类 先写模板参数template<class K, class T, class KeyOfT, class Hash>friend struct HashTableIterator;//...
};

此时我们就可以完善++了，我们先判断是否还有_next，否则就根据_node重新计算hashi。

Self& operator++()
{if (_node->_next){_node = _node->_next;}else{//重新计算hashisize_t hashi = hs(kot(_node->_data)) % _pht->_table.size();++hashi; //跳过当前桶while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){//此时遇到不为空的节点_node = _pht->_table[hashi];break;}++hashi;}//当然会走到空if (hashi == _pht->_table.size()){_node = nullptr;}}return *this;
}

四：其他运算符的重载

接下来我们实现 != 、== 、* 、-> 这些运算符的重载：

bool operator==(const Self& s)
{return _node == s._node;
}bool operator!=(const Self& s)
{return _node != s._node;
}T& operator*()
{return _node->_data;
}T* operator->()
{return &_node->_data;
}

因为它们太简单了，这里不多做解释。

五：实现begin和end

我们要实现begin和end，先把HashTable的Begin和End实现，Begin就是找第一个不为空的桶；End和之前一样直接拿空构造即可。因为迭代器需要两个参数的构造方法，第二个参数是HashTable的指针，所以我们传入this即可：

//先将其重命名为 Iterator
typedef HashTableIterator<K, T, KeyOfT, Hash> Iterator;//定义Begin
Iterator Begin()
{//找到一个元素for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){return Iterator(_table[i], this);}}//此时没有元素 返回End即可return End();
}//定义End
Iterator End()
{return Iterator(nullptr, this);
}

之后再map和set中实现begin和end，但是此前先对hash_backet的HashTable的Iterator为iterator(有点绕，不过很简单)，在set中：

//先重命名
typedef typename hash_bucket::HashTable<K, K, SetOfK>::Iterator iterator;iterator begin()
{return _ht.Begin();
}iterator end()
{return _ht.End();
}

六：实现const类型迭代器 

大家知道，按照传统艺能，我们接下来就要将其改变为能够遍历const类型数据的迭代器了，具体细节可以看【C++】通过红黑树封装map和set-CSDN博客 小编的这篇博客，里面对为什么使用以下方法作出了很详细的解释。

还是和之前一样，对迭代器多提供两个参数，一个是引用，一个是指针即可。因为只有 * 和 -> 两个运算符重载返回类型不一样。

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HashTableIterator
{//...Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Node* _node;
};

所以此时在HashTable中我们这样定义迭代器：

typedef HashTableIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

记得我们之前定义的友元迭代器时要多加上两个参数：

//声明成友元类 先写模板参数
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HashTableIterator;

这里我们就可以实现const版本的Begin和End了。

ConstIterator Begin() const
{for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){return ConstIterator(_table[i], this);}}return End();
}ConstIterator End() const
{return ConstIterator(nullptr, this);
}

之后去完善set中的const版本迭代器：

typedef typename hash_bucket::HashTable<K, K, SetOfK>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetOfK>::ConstIterator const_iterator;//... 以下为const版本
const_iterator begin() const
{return _ht.Begin();
}const_iterator end() const
{return _ht.End();
}

之后传统艺能，写一个函数来测试，参数是const类型，之后你就发现编译报错了(注意，这里不是一堆报错，只有一个)，你双击错误发现停留在HashTable的const版本的End方法中，这是为什么？

这就是我们使用const时，End构造迭代器时，传入的this也是const版本，所以我们在迭代器中需要把_pht指针加上const修饰。记得把构造函数中的 _pht*也加上const修饰。

const HashTable<K, T, KeyOfT, Hash>* _pht;//构造函数
HashTableIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht): _node(node), _pht(pht)
{}

之后再次运行代码就不会有问题了。

七：修改Insert返回值

追剧的同学都知道，Insert返回的值可不是bool，而是一个pair类型。其具体细节可以参考【C++】认识map和set-CSDN博客 这篇文章。

所以这里和之前修改代码是致的：

pair<Iterator, bool> Insert(const T& data)
{//先复用Find//Node* ret = Find(kv.first);Node* ret = Find(kot(data));  //这里要找的是Kif (ret){//存在 无需插入return make_pair(Iterator(ret, this), false);}//...return make_pair(Iterator(newNode, this), true);
}

之后修改set和map中的insert即可。

八：重载map的 [ ] 

这里 [ ] 是复用的insert，具体细节可以看【C++】通过红黑树封装map和set-CSDN博客 这篇文章，这里不再赘述，直接上代码：

V& operator[](const K& key)
{iterator it = insert(make_pair(key, V())).first;return it->second;
}

九：修改HashFunc仿函数

如果我们传入的是指针该怎么办？我们应该修改HashFunc这个仿函数，但是我们目前的map和set类中没有这个模板参数，其模板参数在HashTable中，但是我们又不可能跳过map和set给HashTable传入这个仿函数，所以就有问题，我们在写HashTable的时候最后的Hash模板参数不能提供默认的参数，否则有问题，所以我们应该对set和map增加模板参数。

//这里提供第三个默认模板参数
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{//...typedef typename hash_bucket::HashTable<K, pair<K, V>, MapOfK, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<K, V>, MapOfK, Hash>::ConstIterator const_iterator;//...
private:hash_bucket::HashTable<K, pair<K, V>, MapOfK, Hash> _ht;
};

因为我们已经把HashFunc写为全局函数了，所以就这样使用，把HashTable中的缺省模板参数删除即可。

总结：

终于又解决了一个大问题，这里我们C++的水平应该就很强了，之后我们要学习一些有关C++11的新特性，并进入Linux篇，继续学习关于信号等知识，大家敬请期待吧！

http://www.xdnf.cn/news/277723.html

相关文章：

  • 如何快速获取GPU参数，并解读其性能？
  • 【翻译、转载】【译文】图解模型上下文协议（MCP）
  • Day3：设置页面全局渐变线性渐变背景色uniapp壁纸实战
  • SALOME源码分析: SolverLab
  • 【Trae+LucidCoder】三分钟编写专业Dashboard页面
  • LabVIEW温控系统热敏电阻滞后问题
  • C++类_嵌套类
  • 【题解】CF196D (哈希)
  • 强化学习机器人模拟器——RobotApp：一个交互式强化学习模拟器
  • stm32卡在SystemClock_Config()；的解决方法
  • 华为鸿蒙PC：开启国产操作系统自主化新纪元
  • 【网络】什么是串口链路（Serial Link）？
  • python hasattr()
  • 深入了解 OpenIddict：实现 OAuth 2.0 和 OpenID Connect 协议的 .NET 库
  • 《算法导论(第4版)》阅读笔记：p6-p6
  • 可信执行环境(TEE)：保障数据安全的核心技术
  • 【深入浅出MySQL】之数据类型介绍
  • Git推送大文件导致提交回退的完整解决记录
  • n8n工作流自动化平台的实操：生成统计图的两种方式
  • Solr 与 传统数据库的核心区别
  • 前端面试宝典---性能优化
  • OpenLayers：侦听缩放级别的变化
  • 消息队列MQ
  • OpenStack HA高可用集群Train版-0集群环境准备
  • postgresql数据库基本操作
  • 基于开源AI大模型AI智能名片S2B2C商城小程序源码的私域流量稳定性构建研究
  • 个性化推荐：大数据引领电子商务精准营销新时代
  • NPP库中libnppig模块介绍
  • 大连理工大学选修课——图形学：第六章 三维变换和三维观察
  • Langchain4j基于ElasticSearch的向量数据库配置后，启动报错