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

C++——哈希unordered_set/unordered_map的封装

news 2024/11/19 10:34:52

目录

前言

二、unordered_set的封装

1.模板参数列表的改造

2. 增加迭代器操作

3. 模板参数的意义

三、unordered_map的封装 

1、“轮子所需要的参数

2、迭代器

四、完整代码

1、HashTable

2、unordered_set

 3、unordered_map

总结

前言

unordered_set和map的介绍在上一篇博客有所提到

C++——深部解析哈希

在编程的世界里，数据结构是构建高效、可扩展程序的基石。C++作为一门功能强大的编程语言，提供了丰富的标准库容器，其中unordered_set和map以其高效的查找和插入操作而广受欢迎。然而，尽管这些容器功能强大，直接使用它们有时可能不够直观或灵活，特别是在需要特定行为或扩展功能时。因此，封装这些容器，以提供更符合特定需求的接口，成为了一种常见的编程实践。
本博客旨在深入探讨如何封装C++中的unordered_set和map，以创建更加灵活、易用的数据结构。通过实例和代码演示，你将学会如何扩展这些容器的功能，以满足项目中的特定需求，同时保持高效性和可维护性。

一、为什么要封装？

提升编程效率：封装unordered_set和map可以简化代码，减少重复劳动。通过创建通用的、可重用的封装，你可以在多个项目中快速部署这些数据结构，而无需每次都从头开始实现。
增强代码可读性：封装后的容器往往具有更清晰的接口和更直观的命名，这使得代码更易于理解和维护。对于团队项目来说，这尤其重要，因为它可以降低新成员理解代码的难度。
优化性能：在某些情况下，直接使用标准库的容器可能不是最优解。通过封装，你可以根据具体需求定制容器的行为，比如调整哈希函数、比较器或添加缓存机制，从而提升性能。
扩展功能：标准库的容器提供了基础功能，但可能无法满足所有需求。封装允许你添加额外的功能，如持久化、线程安全、事件监听等，使容器更加适应复杂的应用场景。

二、unordered_set的封装

1.模板参数列表的改造

代码如下（示例）：

// K:关键码类型
// V: 不同容器V的类型不同，如果是unordered_map，V代表一个键值对，如果是
unordered_set,V 为 K
// KeyOfValue: 因为V的类型不同，通过value取key的方式就不同，详细见
unordered_map/set的实现
// HF: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能
取模
template<class K, class V, class KeyOfValue, class Hash = HashFunc<K> >
class HashBucket;
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};
private:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};

SetKeyOfT是用来获取k的key，用于比较； 

2. 增加迭代器操作

代码如下（示例）：

// 前置声明
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 __HashIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}// ++it 17:05继续Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置size_t hashi = hash(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;}
};

3. 模板参数的意义

我们的Hash模板参数是用来获取key的类型将其转换为整型，方便与在顺序表里找桶的位置；因为string类型的不像整型一样可以直接找到顺序表里放桶的位置；

KeyOfT用来将指针所指向的数据转换为key类型。

三、unordered_map的封装 

1、“轮子所需要的参数

template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};

 因为我们在封装时已经将大部分的模板参数给封装好了，只需要改变MapKeyOfT的()重载即可；

2、迭代器

可以直接复用set封装时实现的；

四、完整代码

1、HashTable

template<>
struct HashFunc<string>
{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};namespace HashBucket
{template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};// 前置声明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 __HashIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;Node* _node;const HT* _ht;__HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}__HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}// ++it 17:05继续Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{// 找下一个不为空的桶KeyOfT kot;Hash hash;// 算出我当前的桶位置size_t hashi = hash(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{template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct __HashIterator;typedef HashNode<T> Node;public:typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;iterator begin(){Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end() const{return const_iterator(nullptr, this);}~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}iterator Find(const K& key){if (_tables.size() == 0)return end();KeyOfT kot;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hash;KeyOfT kot;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}// size_t newsize = GetNextPrime(_tables.size());size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}pair<iterator, bool> Insert(const T& data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size()*2;HashTable<K, V> newht;newht.resize(newsize);for (auto cur : _tables){while (cur){newht.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newht._tables);*///size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);;}size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数};
}

2、unordered_set

#pragma once
#include"HashTable.h"namespace my_unordered_set
{template<class K, class Hash = HashFunc<K>>class unordered_set{public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};void print(const unordered_set<int>& s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;}void test_unordered_set1(){int a[] = { 3, 33, 2, 13, 5, 12, 1002 };unordered_set<int> s;for (auto e : a){s.insert(e);}s.insert(54);s.insert(107);unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;print(s);}}

 3、unordered_map

#pragma once#include "HashTable.h"namespace my_unordered_map
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{public:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:HashBucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};}

总结

封装在于对模板和迭代器的底层逻辑和重写


http://www.mrgr.cn/news/27855.html

相关文章：

  • 全面解读 USB Key：定义、使用场景、加密技术及 Java 实现
  • Design Compiler：Topographical Workshop Lab2
  • OpenTelemetry 赋能DevOps流程的可观测性革命
  • ODC 如何精确呈现SQL耗时 | OceanBase 开发者工具解析
  • mmsegmentation: 安装 并使用自定义数据集进行训练 ·1
  • 如何使用 WebAssembly 扩展后端应用
  • 火语言RPA流程组件介绍--下拉框选择
  • 你可能遗漏的一些C#/.NET/.NET Core知识点
  • 高效网络爬虫设计：多线程抓取网页内容
  • AI学习指南深度学习篇-RMSprop算法流程
  • [产品管理-21]：NPDP新产品开发 - 19 - 产品设计与开发工具 - 详细设计与规格定义
  • linux服务器配置及服务器资源命令使用查看
  • UDP_SOCKET编程实现
  • Vue3 Day4-计算、监视属性
  • 松材线虫多光谱数据集
  • InputDispatcher的调试日志isLoggable动态开放logcat实战使用
  • 【退役之再次线上部署】Spring Boot + VUE + Nginx + MySQL
  • verilog运算符优先级
  • 堆排序，快速排序
  • C#/.NET/.NET Core技术前沿周刊 | 第 5 期（2024年9.9-9.15）
  • Linux: virtual: qemu-kvm: top cpu usage的组成是否包含guest的使用？
  • 窗口嵌入桌面背景层（vb.net，高考倒计时特供版）
  • 基于双PI矢量控制结构和SVPWM的风力发电系统Simulink建模与仿真
  • C++线程库
  • （SERIES12）DM性能优化
  • web开发 之 HTML、CSS、JavaScript、以及JavaScript的高级框架Vue（学习版2）