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

20. C++使用HashTable同时出封装unordered_map和unordered_set

news 2025/5/11 10:00:07

文章目录

      • 模板参数控制
      • 哈希表正向迭代器的实现
        • 接引用和->
        • 判断节点是否同一个
        • ++运算符重载函数
      • HashTable.h
      • MyUnorderedSet.h
      • MyUnorderedMap.h

模板参数控制

unordered_set是K模型的容器，而unordered_map是KV模型的容器

  • 为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T。
template<class K, class T>
class HashTable
  • 如果使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key。
template<class K>
class unordered_set
{
public://...
private:hash_bucket::HashTable<K, K> _ht; //传入底层哈希表的是K和K
};
  • 但如果使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对。
template<class K, class V>
class unordered_map
{
public://...
private:HashTable<K, pair<K, V>> _ht; //传入底层哈希表的是K以及K和V构成的键值对
};

而哈希结点的模板参数也应该由原来的K、V变为T：

  • 上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。
  • 上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。

更改模板参数后，哈希结点的定义如下：

//哈希结点的定义
template<class T>
struct HashData
{HashData<T>* _next;T _data;// 构造HashData(const T& data):_data(data), _next(nullptr){}
};

哈希表正向迭代器的实现

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址。

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{typedef HashNode<T> Node; //哈希结点的类型typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的类型typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的类型Node* _node; //结点指针HT* _pht; //哈希表的地址// 构造__HTIterator(Node* node,HT* ht):_node(node),_pht(ht){}
};
接引用和->
T& operator*()
{//返回哈希结点中数据的引用return _node->_data;
}
T* operator->()
{//返回哈希结点中数据的地址return &_node->_data; 
}
判断节点是否同一个
bool operator!=(const Self& s) const
{return _node != s._node;
} bool operator==(const Self& s) const
{return _node == s._node;
}
++运算符重载函数
  • 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。
  • 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。
Self& operator++()
{if (_node->_next){// 当前桶还有节点，走到下一个节点_node = _node->_next;}else{// 当前桶已经走完了，找下一个桶开始KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]) // 如果桶存在{// 找到了_node = _ht->_tables[hashi];break;}else{// 继续往后找++hashi;}}// 走完了if (hashi == _ht->_tables.size())_node = nullptr;}return *this;
}

HashTable.h

#pragma once
#include <vector>
#include <iostream>static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] =
{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
};inline unsigned long __stl_next_prime(unsigned long n)
{const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = std::lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化
template<>
struct HashFunc<std::string>
{size_t operator()(const std::string& key){size_t hashi = 0;for (auto& e : key){hashi *= 131;hashi += e;}return hashi;}
};namespace hash_bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;// 构造HashNode(const T& data):_data(data),_next(nullptr){}};// 需要前置声明一下HashTabletemplate<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<T>>struct __HTIterator{typedef HashNode<T> Node; //哈希结点的类型typedef HashTable<K, T, KeyOfT, Hash> HT; // 哈希表的类型typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self; //正向迭代器的类型Node* _node; //结点指针const HT* _ht; //哈希表的地址 // 需要是const// 构造__HTIterator(Node* node, const HT* ht) // 注意参数:_node(node),_ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}Self& operator++(){if (_node->_next){// 当前桶还有节点，走到下一个节点_node = _node->_next;}else{// 当前桶已经走完了，找下一个桶开始KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]) // 如果桶存在{// 找到了_node = _ht->_tables[hashi];break;}else{// 继续往后找++hashi;}}// 走完了if (hashi == _ht->_tables.size())_node = nullptr;}return *this;}};// 仿函数不能在这里写缺省参数，必须要在上一层加template<class K, class T, class KeyOfT, class Hash>class HashTable{KeyOfT kot; // 用于取值Hash hs;    // 用于计算typedef HashNode<T> Node;// 须要进行友元声明__HTIterator中的_tables才能访问，并且声明不能有缺省参数template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct __HTIterator;///public:typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;// 迭代器Iterator Begin(){// 找第一个不为空的桶里面的第一个节点for (size_t i = 0; i < _tables.size(); i++){if (_tables[i])return Iterator(_tables[i], this);}return End();}Iterator End(){return Iterator(nullptr, this);} ConstIterator Begin() const{// 找第一个不为空的桶里面的第一个节点for (size_t i = 0; i < _tables.size(); i++){if (_tables[i])return ConstIterator(_tables[i], this);}return End();}ConstIterator End() const {return ConstIterator(nullptr, this);}HashTable(size_t size = __stl_next_prime(0)): _tables(size, nullptr), _n(0){}~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}std::pair<Iterator, bool>Insert(const T& data){// 1、查看哈希表中是否存在该键值的键值对Iterator it = Find(kot(data));if (it != End())return { it , false };// 2、判断是否需要调整哈希表的大小if (_n == _tables.size()){// a. 建立新表std::vector<Node*> newTables(__stl_next_prime(_tables.size() + 1));// b、将原哈希表当中的结点插入到新哈希表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){// 旧表的节点挪动下来插入到映射的新表位置Node* next = cur->_next;   //记录cur的下一个结点size_t hashi = hs(kot(cur->_data)) % newTables.size(); // 通过哈希函数计算出对应的哈希桶编号indexcur->_next = newTables[hashi]; // 节点直接拿下来放到新桶中newTables[hashi] = cur; // 将该结点头插到新哈希表中编号为index的哈希桶中cur = next; // 取原哈希表中该桶的下一个结点}_tables[i] = nullptr;  // 该桶取完后将该桶置空}_tables.swap(newTables);} // 扩容end...size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 进行头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { {newnode, this}, true };}Iterator Find(const K& key){if (_tables.size() == 0) // 哈希表大小为0，查找失败return End();// 通过哈希函数计算出对应的哈希桶编号size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];// 遍历哈希桶while (cur){if (kot(cur->_data) == key)return Iterator(cur, nullptr);cur = cur->_next;}return End();}bool Erase(const K& key){//1、通过哈希函数计算出对应的哈希桶编号index（除数不能是capacity）size_t hashi = hs(kot(key)) % _tables.size();//2、在编号为index的哈希桶中寻找待删除结点Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){//3、若找到了待删除结点，则删除该结点if (kot(cur->_data) == key){//待删除结点是哈希桶中的第一个结点if (prev == nullptr)_tables[hashi] = cur->_next;// 将第一个结点从该哈希桶中移除else// 待删除结点不是哈希桶的第一个结点prev->_next = cur->_next; // 前一个节点的next指向cur的nextdelete cur;--_n; // 4、删除结点后，将哈希表中的有效元素个数减一return true;}// 继续往后找prev = cur;cur = cur->_next;}return false;}private:std::vector<Node*> _tables;size_t _n;};
}

MyUnorderedSet.h

#pragma once#include "HashTable.h"namespace lsl
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:// 用第一个也可以//typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;// 使用这个也可以/*using iterator = typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator;using const_iterator = typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator;*/iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();} const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}std::pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};/测试/// const迭代器void print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;std::cout << *it << " ";++it;}std::cout << std::endl;}void unordered_set_Test(){unordered_set<int> s;s.insert(1);s.insert(5);s.insert(10);s.insert(508);s.insert(333);s.insert(82);for (auto& e : s){std::cout << e << " ";}std::cout << std::endl;print(s);// set不可以修改unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;std::cout << *it << " ";++it;}std::cout << std::endl;}
}

MyUnorderedMap.h

#pragma once#include "HashTable.h"namespace lsl
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;// 使用这个也可以/*using iterator = typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::Iterator;using const_iterator = typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::ConstIterator;*/ iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){std::pair<iterator, bool> ret = _ht.Insert({ key, V() });return ret.first->second;}private:hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;};/测试/// const迭代器void print(const unordered_map<std::string, std::string>& s){unordered_map<std::string, std::string>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;std::cout << it->first << " " << it->second << std::endl;++it;}std::cout << std::endl;}void unordered_map_Test(){unordered_map<std::string, std::string> s;s.insert({ "string", "字符串" });s.insert({ "left", "左" });unordered_map<std::string, std::string>::iterator it = s.begin();while (it != s.end()){std::cout << it->first << ":" << it->second << std::endl;++it;}print(s);s["sort"];s["left"] = "左边+剩余";s["right"] = "右边";// pair中的first不能被修改unordered_map<std::string, std::string>::iterator it2 = s.begin();while (it2 != s.end()){//it2->first += 'x';//it2->second += 'x';std::cout << it2->first << ":" << it2->second << std::endl;++it2;}}
}
http://www.xdnf.cn/news/314929.html

相关文章：

  • Ubuntu 配置网络接口端点（静态 IP 地址）详细教程
  • 亿级流量系统架构设计与实战（五）
  • mysql集成Qwen大模型MCP计算【附实战代码】
  • 【iOS】源码阅读(三)——内存对齐原理
  • AGV导航控制器技术方案——基于EFISH-SBC-RK3576/SAIL-RK3576的国产化革新‌（新一代工业级自主可控解决方案）‌
  • 战术级微波干扰系统：成都鼎轻量化装备如何实现全频段智能压制？
  • 从字节到链接：用类型化数组生成神奇的对象 URL
  • 如何进行室内VR全景拍摄？
  • Android 有线网开发调试总结
  • 【计算机视觉】OpenCV实战项目：Long-Exposure：基于深度学习的长时间曝光合成技术
  • C26-冒泡排序法
  • Flutter——数据库Drift开发详细教程(五)
  • 二叉平衡树
  • 学习笔记：黑马程序员JavaWeb开发教程(2025.3.29)
  • Linux 驱动开发步骤及 SPI 设备驱动移植示例
  • 基于SpringBoot和PostGIS的应急运输事件影响分析-以1.31侧翻事故为例
  • Docker 容器镜像环境的依赖导出
  • Android 10.0 SharedPreferences in credential encrypted storage are not avai
  • 声波解码器：当40kHz遇见AIoT时代——超声波传感器的“隐形智慧”革命
  • 从明文裸奔到密钥长城：HTTPS加密全链路攻防与CA信任锚点构建
  • 【疑难杂症2025-003】Java-mvn项目在gitlab-ci构建镜像时遇到的问题和解决方案
  • 内网渗透技术全面指南——安全业务视角(基于《内网渗透技术 (吴丽进、苗春雨 主编；郑州、雷珊珊、王伦 副主编)》)
  • stm32常见错误
  • 矩阵扩展-算卷积算法介绍及C语言代码实现
  • Node.js vs 浏览器中的JavaScript：区别全解析
  • QT —— QWidget（2）
  • 【Science Advances】普林斯顿大学利用非相干光打造可重构纳米光子神经网络
  • 全文索引数据库Elasticsearch底层Lucene
  • SafeDrive：大语言模型实现自动驾驶汽车知识驱动和数据驱动的风险-敏感决策——论文阅读
  • 【Pandas】pandas DataFrame expanding