AI 助理
备案控制台
开发者社区 云原生 文章 正文

【C++进阶】十、用哈希表对unordered_set和unordered_map进行封装

2023-04-20 155
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录一、改造哈希表1.1 节点定义 1.2 哈希表迭代器相关1.3 哈希表接口相关二、unordered_set模拟实现代码三、unordered_map模拟实现代码

目录

一、改造哈希表

1.1 节点定义

1.2 哈希表迭代器相关

1.3 哈希表接口相关

二、unordered_set模拟实现代码

三、unordered_map模拟实现代码

一、改造哈希表

使用的代码是之前篇章哈希表的代码，改造后哈希表代码如下：

#pragma once#include <vector>#include <string>//开散列（哈希桶）template<classT>structHashNode{
T_data;
HashNode<T>*_next;
HashNode(constT&data)
        :_data(data)
        , _next(nullptr)
    {}
};
//仿函数template<classK>structHashFunc{
size_toperator()(constK&key)
    {
return (size_t)key;
    }
};
//仿函数特化template<>structHashFunc<string>{
size_toperator()(conststring&key)
    {
size_thash=0;
for (autoch : key)
        {
hash*=131;//BKDRHash算法hash+=ch;
        }
returnhash;
    }
};
//声明HashTable，不声明__HTIerator的_ht变量找不到标识符template<classK, classT, classHash, classKeyOfT>classHashTable;
template<classK, classT, classRef, classPtr, classHash, classKeyOfT>struct__HTIerator{
typedefHashNode<T>Node;
typedef__HTIerator<K, T, Ref, Ptr, Hash, KeyOfT>Self;
typedefHashTable<K, T, Hash, KeyOfT>HT;
//成员变量Node*_node;
HT*_ht;
//构造函数__HTIerator(Node*node, HT*ht)
        :_node(node)
        ,_ht(ht)
    {}
Refoperator*()
    {
return_node->_data;
    }
Ptroperator->()
    {
return&_node->_data;
    }
booloperator!=(constSelf&s)const    {
return_node!=s._node;
    }
Self&operator++()
    {
if (_node->_next)//当前桶没有走完，迭代遍历当前桶        {
_node=_node->_next;
        }
else//当前桶走完了，要找下一个桶的第一个        {
KeyOfTkot;
Hashhash;
size_thashi=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<classK, classT, classHash, classKeyOfT>classHashTable{
typedefHashNode<T>Node;
//要给__HTIerator类设置成友元，否则__HTIerator类无法访问HashTable的私有成员，ps；_ht->_tables.size()template<classK, classT, classRef, classPtr, classHash, classKeyOfT>friendstruct__HTIerator;
public:
typedef__HTIerator<K, T, T&, T*, Hash, KeyOfT>iterator;
//构造HashTable()
        :_n(0)
    {
_tables.resize(10);//默认开10个空间    }
//析构~HashTable()
    {
for (size_ti=0; i<_tables.size(); ++i)
        {
//释放每一个桶Node*cur=_tables[i];
while (cur)
            {
Node*next=cur->_next;
deletecur;
cur=next;
            }
_tables[i] =nullptr;
        }
    }
iteratorbegin()
    {
for (size_ti=0; i<_tables.size(); ++i)
        {
if (_tables[i])
            {
returniterator(_tables[i], this);
            }
        }
returniterator(nullptr, this);
    }
iteratorend()
    {
returniterator(nullptr, this);
    }
//插入pair<iterator, bool>Insert(constT&data)
    {
KeyOfTkot;
iteratorit=Find(kot(data));
if (it!=end())//查询插入的值是否已经存在        {
returnmake_pair(it, false);//存在插入失败        }
//大于标定负载因子，就需要扩容//这里负载因子标定为 1if (_tables.size() ==_n)
        {
//创建一个新的哈希表，新哈希表的大小设置为原哈希表的2倍vector<Node*>newTables;
newTables.resize(_tables.size() *2);
//将原哈希表当中的结点插入到新哈希表for (size_ti=0; i<_tables.size(); ++i)
            {
Node*cur=_tables[i];
while (cur)//桶不为空                {
Node*next=cur->_next;
size_thashi=Hash()(kot(cur->_data)) %newTables.size();
//节点头插到新表cur->_next=newTables[hashi];
newTables[hashi] =cur;
cur=next;//取该桶的下一个节点                }
//该桶取完后将该桶置空_tables[i] =nullptr;
            }
//交换这两个哈希表_tables.swap(newTables);
        }
//不需要扩容，进行插入size_thashi=Hash()(kot(data)) %_tables.size();
//头插Node*newNode=newNode(data);
newNode->_next=_tables[hashi];
_tables[hashi] =newNode;
//有效数据+1++_n;
returnmake_pair(iterator(newNode, this), true);
    }
//查找iteratorFind(constK&key)
    {
size_thashi=Hash()(key) %_tables.size();//计算key的哈希地址Node*cur=_tables[hashi];
//遍历这个桶进行查找while (cur)
        {
if (KeyOfT()(cur->_data) ==key)//查找成功            {
returniterator(cur, this);
            }
cur=cur->_next;
        }
//该桶遍历完，查找失败returnend();
    }
//删除boolErase(constK&key)
    {
size_thashi=Hash()(key) %_tables.size();//计算key的哈希地址Node*prev=nullptr;//用于记录 cur的前一个节点Node*cur=_tables[hashi];
while (cur)
        {
if (KeyOfT()(cur->_data) ==key)//找到需要删除的节点            {
if (cur==_tables[hashi])//头删                {
_tables[hashi] =cur->_next;
                }
else//中间删除                {
prev->_next=cur->_next;
                }
deletecur;
--_n;
returntrue;
            }
else//迭代遍历            {
prev=cur;
cur=cur->_next;
            }
        }
//删除失败returnfalse;
    }
private:
vector<Node*>_tables;//指针数组, 哈希表size_t_n;//用于记录表中有效数据的个数};

哈希表模板参数的控制：unordered_set是K模型的容器，而unordered_map是KV模型的容器

HashTable类的模板参数介绍：

template<class K, class T, class Hash, class KeyOfT>

模板参数K（key）用于查找和删除数据，模板参数T用于存储数据，如果上层是unordered_set，T则是key，如果上层是unordered_map，T则是键值对pair

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

image.png

模板参数Hash是一个哈希函数，在哈希表已经有过详细解释

image.png

模板参数KeyOfT 是一个仿函数，用于获取数据，由上层的 unordered_set 和

unordered_map 独立实现

image.png

1.1 节点定义

数据类型是泛型，由上层传入才确定是Key 或键值对pair 

template<classT>structHashNode{
T_data;
HashNode<T>*_next;
HashNode(constT&data)
        :_data(data)
        , _next(nullptr)
    {}
};

1.2 哈希表迭代器相关

迭代器模板参数如下

template<classK, classT, classRef, classPtr, classHash, classKeyOfT>

哈希表的迭代器与其他容器的迭代器有所不同，哈希表的迭代器增加了一个 HashTable 的指针，不增加这个变量是无法完成哈希表的迭代器的，这也意味着 const 版本的迭代器需要重新写在另一个类，不能复用普通迭代器的代码完成const 迭代器

image.png

构造迭代器时，不仅需要对应哈希结点的指针，还需要该哈希结点所在哈希表的地址

//构造函数__HTIerator(Node*node, HT*ht)
    :_node(node)
    ,_ht(ht)
{}

前置++

  • 若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点
  • 若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点
Self&operator++()
{
if (_node->_next)//当前桶没有走完，迭代遍历当前桶    {
_node=_node->_next;
    }
else//当前桶走完了，要找下一个桶的第一个    {
KeyOfTkot;
Hashhash;
size_thashi=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;
}
};

其他都与之前一致，就不解释了

1.3 哈希表接口相关

详细介绍在哈希表篇章，这里不解释了，这里只是对它的进口进行了封装

二、unordered_set模拟实现代码

都是调用哈希表接口，不解释了

#include "HashTable.h"namespacefy{
template<classK, classHash=HashFunc<K>>classunordered_set    {
structSetKeyOfT        {
constK&operator()(constK&key)
            {
returnkey;
            }
        };
public:
//没有实例化，没办法到HashTable里面找iterator，所以typename就是告诉编译器这里是一个类型，实例化以后再去取typedeftypenameHashTable<K, K, Hash, SetKeyOfT>::iteratoriterator;
//typedef typename HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;iteratorbegin()
        {
return_ht.begin();
        }
iteratorend()
        {
return_ht.end();
        }
/*const_iterator begin()const{return }*/boolerase(constK&key)
        {
return_ht.Erase(key);
        }
pair<iterator, bool>insert(constK&key)
        {
return_ht.Insert(key);
        }
private:
HashTable<K, K, Hash, SetKeyOfT>_ht;
    };
voidTest_unorderSet()
    {
unordered_set<int>us;
us.insert(4);
us.insert(14);
us.insert(8);
us.insert(2);
us.insert(18);
us.insert(2);
us.insert(234);
us.insert(24);
us.insert(11);
us.insert(666);
unordered_set<int>::iteratorit=us.begin();
while (it!=us.end())
        {
cout<<*it<<" ";
++it;
        }
cout<<endl;
us.insert(5);
us.insert(16);
us.erase(4);
us.erase(4);
us.erase(2);
us.erase(11);
us.erase(666);
us.erase(234);
    }
}

文章内容都是炒旧饭，没啥介绍的，文章就到这

----------------我是分割线---------------

文章到这里就结束了，下一篇即将更新

文章标签：
C++
容器
存储
关键词：
C++哈希表
unordered_set Map
C++ map
C++ set
C++ set map
枫叶先生_
目录
相关文章
陌陌谣
|
4月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下，局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段，已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”，实时捕获每台电脑屏幕上的操作动态。然而，面对海量监控数据，实现高效数据存储与快速检索，已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法，深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”，并通过详尽的代码示例，展现其强大功能与应用价值。
陌陌谣
106 2
码字猴儿
|
3月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些？
for...of循环在遍历Set和Map时的注意事项有哪些？
码字猴儿
258 121
ephemerals__
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
173 2
游客akle7anmklvj6
|
6月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中，公司局域网管理至关重要。哈希表作为一种高效的数据结构，通过哈希函数将关键值（如IP地址、账号）映射到数组索引，实现快速的插入、删除与查找操作。例如，在员工登录验证和设备信息管理中，哈希表能显著提升效率，避免传统线性查找的低效问题。本文以C++为例，展示了哈希表在局域网管理中的具体应用，包括设备MAC地址与IP分配的存储与查询，并探讨了优化哈希函数和扩容策略，确保网络管理高效准确。
游客akle7anmklvj6
102 1
游客vumine6cengps
|
2月前
|
存储 算法 PHP
数组去重性能优化：为什么Set和Object哈希表的效率最高
在处理数组去重问题时，使用 `Set` 和 `Object` 哈希表是高效的解决方案。它们基于哈希表实现，插入和查找操作的时间复杂度为 `O(1)`，相比传统嵌套循环的 `O(n²)` 方法性能优势显著。`Set` 能保持元素插入顺序，适用于需要顺序的场景；`Object` 则通过键的唯一性实现去重，适合无需顺序的场景。两者均能在大规模数据中实现高效的去重操作，是数组去重最优选择。
游客vumine6cengps
129 0
ephemerals__
|
6月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现，内部元素按键自动升序排列，存储键值对，支持通过键访问或修改值；而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能，并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别，强调了`map`在处理键值关系时的优势。
ephemerals__
334 73
hahaha无
|
3月前
|
存储 缓存 Java
c++的哈希表、哈希桶的介绍与实现
这一篇文章大致实现详细介绍什么是哈希，然后再介绍什么是哈希表，怎么代码实现哈希表，然后再介绍哈希桶，怎么代码实现哈希桶，最后再介绍他俩有什么细节上的差别，与代码的一些细节优化。
hahaha无
84 0
hahaha无
|
3月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后，我们的底层代码已经完成了，这时候已经是一个底层STL的红黑树了，已经已符合库里面的要求了，这时候我们是需要给他穿上对应的“衣服”，比如穿上set的“衣服”，那么这个穿上set的“衣服”，那么他就符合库里面set的要求了，同样map一样，这时候我们就需要实现set与map了。因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
hahaha无
46 0
hahaha无
|
3月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别，注意事项
set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列。set当中存储元素的value都是唯一的，不可以重复，因此可以使用set进行去重。set默认是升序的，但是其内部默认不是按照大于比较，而是按照小于比较。set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
hahaha无
199 0

热门文章

最新文章

  • 1
    应用程序无法正常启动（0xc0000005）？C++报错0xC0000005如何解决？使命召唤17频频出现闪退，错误代码0xC0000005（0x0）
  • 2
    Microsoft Visual Basic/C++ Runtime，Visual C++ 运行库合集（VCRedistPack）
  • 3
    C++语言中指针变量int和取值操作ptr详细说明。
  • 4
    C++面试周刊(3):面试不慌,这样回答指针与引用，青铜秒变王者
  • 5
    Java、Python、C++支持jenkins和SonarQube(全集)
  • 6
    Java、Python、C++支持jenkins和SonarQube（一）
  • 7
    Java、Python、C++支持Jenkins和SonarQube（二）
  • 8
    Java、Python、C++支持jenkins和SonarQube(四)
  • 9
    Java、Python、C++支持Jenkins和SonarQube(三)
  • 10
    【MySQL】init_connect='SET NAMES utf8'，是干什么的？底层原理是什么？
  • 1
    Spark RDD 中的 map 和 flatMap 转换有什么区别？
    803
  • 2
    Map——全国省市区EXCEL表格（包含code）
    160
  • 3
    Map——使用BIGEMAP+geojson获取乡镇行政边界数据
    618
  • 4
    js中map属性
    113
  • 5
    Map集合
    125
  • 6
    Go 语言为什么不支持并发读写 map？
    131
  • 7
    【python笔记】高阶函数map、filter、reduce
    219
  • 8
    go 语言中 map 的相关知识
    98
  • 9
    ES6新特性（四）: Set 和 Map
    124
  • 10
    Go - 使用 sync.Map 来解决 map 的并发操作问题
    149

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    2025云栖大会，阿里云百炼邀请您的参与和见证