【C++】unordered系列容器的模拟实现

news/2025/2/27 13:39:32/

文章目录

  • Ⅰ. 前言
  • Ⅱ. 对哈希表的改造
    • 一、模板参数列表的改造
    • 二、哈希表的迭代器
      • ① 迭代器的基础框架
      • ② 迭代器的常见函数实现
      • ③ 哈希表对迭代器的利用
        • ☠ 一个小坑，注意在哈希表中 `typedef ... iterator` 的时候，==记得要将 `typedef` 语句放在 `public` 权限中==，不然 `unordered_map`/`unordered_set` 在取 `iterator` 的时候会没权限！
    • 三、哈希表的桶操作函数
      • ① 返回哈希桶中桶的总个数
      • ② 返回 n 号桶中有效元素的总个数
      • ③ 返回元素 key 所在的桶号
    • 四、哈希表的拷贝构造函数与赋值重载
    • 五、哈希表的析构函数
  • Ⅲ. unordered_set的封装
  • Ⅳ. unordered_map的封装

在这里插入图片描述

Ⅰ. 前言

​ 由哈希表的知识我们可知开散列其实是比闭散列有优势的，所以下面的实现都是基于开散列的基础实现的！

Ⅱ. 对哈希表的改造

一、模板参数列表的改造

​ 从之前的红黑树改造可知，我们得多传一个 KeyOfT ，因为如果我们的 map 或 set 想存不同的数据类型的话，那么 T 取 Key 的方式就不一样了，比如如果是内置类型则直接取，但是如果是 pair 类型，那我们取的其实是 pair 的 first，所以这里我们得增加一个 KeyOfT 的模板参数：

// K:关键码类型
// T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是unordered_set,T 为 K
// KeyOfT: 因为T的类型不同，通过T取key的方式就不同，详细见unordered_map/set的实现
// HashFunc: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class hashtable;

这样子的话我们也要对之前哈希表中的节点数据进行修改：

template <class T>
struct HashNode
{T _data; // 类型为T，变得泛型了HashNode<T>* _next;HashNode(const T& data, HashNode<T>* next = nullptr):_data(data), _next(next){}
};

​ 🔺 注： 记得有了 KeyOfT 后要去改一下 insert 等函数中的一些取 key 的细节，这里以 insert 为例，erase 和 find 都是类似的：

bool insert(const T& data)
{KeyOfT kt; // 取key的仿函数// 检测是否有重复元素Node* ret = find(kt(data)); // 将data中的key取出来if (ret != nullptr)return false;// 检测是否需要扩容_CheckCapacity();HashFunc _hs; // 哈希函数size_t index = _hs(kt(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[index];_tables[index] = newnode;++_n;return true;
}

二、哈希表的迭代器

① 迭代器的基础框架

​ 在实现迭代器之前我们想一想，一个开散列结构在迭代时候，其实遍历一个桶是不难的，但是如何做到两个桶之间的切换呢？

​ 解决方法有很多，比如说每次在遍历到一个桶时候就记录下该桶的下标数，等到链表遍历完再切换到下一个桶，或者说迭代器里面再存一个哈希表，用循环遍历该哈希表的所有桶的同时遍历每个桶的元素（但是空间消耗比较大，因为开辟了一个哈希表）…

​ 我们这里采取另一种方法，就是 迭代器里面再存一个哈希表的指针！

template <class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
struct _HTIterator
{typedef HashNode<T> Node;typedef _HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> iterator;Node* _node; hashtable<K, T, KeyOfT, HashFunc>* _pht; // 哈希表的指针// 构造函数_HTIterator(Node* node, hashtable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){}
};

​ ❓ 问题来了，我们迭代器是声明在哈希表前面的，也就是说我们的哈希表去 typedef 迭代器没问题，但是当我们在迭代器里面声明一个哈希表指针，显然是需要有声明才行，但是由于位置关系，迭代器就找不到哈希表的声明，就会报错啦，那该咋办？

在这里插入图片描述

​ 💡 方法：使用前置声明（要注意的是带有模板参数要将模板参数列表也带上）
在这里插入图片描述

​ 这里看似我们把问题解决了，其实里面还隐含着一些其他的问题：

​ 🚅 因为我们还没有实例化对象，所以问题没有被报出来，但是我们其实可以看到，这里的迭代器声明了一个哈希表，也就是说需要去访问哈希表的成员变量，那么按我们之前所学的知识我们可以知道其他类是不能直接访问一个类的 private 成员的，这里没有报错只是我们还没实例化出对象，一旦实例化就会报错权限问题，那我们该怎么办呢？

​ 💡 方法： 使用友元（与上面的前置声明一样，这里也要带上模板参数列表才完整）

在这里插入图片描述

② 迭代器的常见函数实现

​ 我们会着重讲解 operator++() 的实现，而其他的都是和其他容器类似的，这里就一步带过：

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;
}

operator++()：

​ 回到主题，我们前面说，遍历一个桶其实就是遍历单链表，这是不难的，难的是我们如何在桶之间切换呢？这里我们就用到了==哈希表的指针==！为什么不是哈希表呢？前面说过如果是指针的话，节省空间哈哈哈！

  • 如果 _node->_next 不为空，则说明这个桶还没遍历完，所以继续 遍历到链表的下一个元素 即可。

  • 如果 _node->_next 为空，则说明这个桶已经遍历完了或者不存在元素，则要进行一些处理：

    1. 通过哈希表的指针（因为有了哈希表的指针就能得到哈希表的长度）找到目前桶的位置 index，然后再让其 index++ 就得到下一个桶的位置
    2. 接着循环判断下一个桶是否为空，或者位置 index 是否已经超出了哈希表的长度
      • 若不为空则让 _node 移动到 index 位置
      • 若为空则让 index++ ，直到找到或者出界
    3. 最后出了循环后要判断一下位置 index 是否出界，若出界说明哈希表遍历完成，则直接让 _node = nullptr
      在这里插入图片描述
Self& operator++()
{// 不为空说明还没遍历完该桶if (_node->_next != nullptr){_node = _node->_next;}else // 为空则需要切换桶{KeyOfT kt;HashFunc _hs;// 通过哈希表的指针找到目前桶的位置，然后再让其++就得到下一个桶的位置size_t index = _hs(kt(_node->_data)) % _pht->_tables.size();index++;// 寻找下一个不为空的桶while (index < _pht->_tables.size()){// 不为空则让 _node 移动过来if (_pht->_tables[index] != nullptr){_node = _pht->_tables[index];break;}else // 为空则继续判断下一个桶{index++;}}// 出了循环后要判断是否出界if (index >= _pht->_tables.size())_node = nullptr;}return *this;
}

operator++(int)：

​ 有了 operator++()，我们就可以复用其来实现我们的 后置++ 了，思路和其他容器的迭代器是类似的：

Self operator++(int)
{Self tmp(this->_node, this->_pht);++*this;return tmp;
}

🚗 值得注意的是，我们实现的哈希表是没有 operator--() 和 反向迭代器的，所以我们只需要实现正向迭代器的 operator++() 即可，因为哈希表是无序的，迭代只是为了遍历其中的元素，所以拥有反向迭代器的意义是不大的！

③ 哈希表对迭代器的利用

其实就是实现 begin() 和 end()，以及将 insert 的返回值变成 iterator 等等…

  • 对于 begin() ：

​ 我们不能直接的返回哈希表的首个元素，因为有可能首个桶中是没有元素的，所以我们对 begin 的定义是 第一次元素出现的位置。

🔴 注：这里构造迭代器的时候，返回的第二个参数的哈希表，我们可以用 this 做为参数！

iterator begin()
{for (size_t i = 0; i < _tables.size(); ++i){// 若出现不为空则直接返回对应的迭代器if (_tables[i] != nullptr){return iterator(_tables[i], this);}}return end();
}
  • 对于 end() ：
iterator end()
{return iterator(nullptr, this);
}
  • 对于 insert() ：

​ 🐰 这里有一些细节，就是要将 ret 的类型从 Node* 转化为 iterator，并且将 ret != nullptr 转化为 ret != end()

pair<iterator, bool> insert(const T& data)
{KeyOfT kt;// 检测是否有重复元素iterator ret = find(kt(data));if (ret != end())return make_pair(ret, false);// 检测是否需要扩容_CheckCapacity();HashFunc _hs; // 哈希函数size_t index = _hs(kt(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[index];_tables[index] = newnode;++_n;return make_pair(iterator(newnode, this), true);
}
  • 对于 find() ：
iterator find(const K& key)
{if (_tables.size() == 0)return iterator(nullptr, this);KeyOfT kt;HashFunc _hs; // 哈希函数size_t index = _hs(key) % _tables.size();Node* cur = _tables[index];while (cur != nullptr){if (kt(cur->_data) == key)return iterator(cur, this);cur = cur->_next;}return iterator(nullptr, this);
}
☠ 一个小坑，注意在哈希表中 typedef ... iterator 的时候，记得要将 typedef 语句放在 public 权限中，不然 unordered_map/unordered_set 在取 iterator 的时候会没权限！

三、哈希表的桶操作函数

① 返回哈希桶中桶的总个数

// 返回哈希桶中桶的总个数
size_t bucket_count() const 
{return _tables.size();
}

② 返回 n 号桶中有效元素的总个数

// 返回n号桶中有效元素的总个数
size_t bucket_size(size_t n) const
{size_t count = 0;Node* cur = _tables[n];while (cur != nullptr){count++;cur = cur->_next;}return count;
}

③ 返回元素 key 所在的桶号

// 返回元素key所在的桶号
size_t bucket(const K& key) const
{HashFunc hs;return hs(key) % _tables.size();
}

四、哈希表的拷贝构造函数与赋值重载

​ 拷贝构造函数：

hashtable(const hashtable<K, T, KeyOfT, HashFunc>& s)
{_tables.resize(s._tables.size());for (size_t i = 0; i < _tables.size(); ++i){Node* tmp = s._tables[i];while (tmp != nullptr){Node* copy = new Node(tmp->_data);// 头插copy->_next = _tables[i];_tables[i] = copy;tmp = tmp->_next;}}// 记得将有效个数也拷贝过去_n = s._n;
}

​ 🔴 但是此时我们会发现有报错：

在这里插入图片描述

​ 我勒个去，什么情况，我们没删除什么东西啊！为啥会报错勒？

​ 原因其实因为 如果我们写了构造函数（包括拷贝构造函数），那么编译器就不会生成默认的构造函数，那么在 unordered_map 和 unordered_set 中去找 _ht 调用构造函数的时候，就找不到了，自然就无法构造出来！

在这里插入图片描述

​ 为了解决这个问题，我们可以自己写个构造函数，但是其实没必要，因为默认生成的构造函数会帮我们去调用 vector 的构造函数，而 _n 则是内置类型给它个缺省值即可，那么我们怎么生成一个编译器默认生成的构造函数呢？

💡 方法如下：

// 告诉编译器使用默认的构造函数
hashtable() = default;

​ 这样子问题就解决了！

​ 赋值重载函数：

​ 赋值重载就不用多说啦，直接用现代写法！

// 赋值重载
hashtable<K, T, KeyOfT, HashFunc>& operator=(hashtable<K, T, KeyOfT, HashFunc> s)
{swap(_n, s._n);_tables.swap(s._tables);return *this;
}

五、哈希表的析构函数

​ 我们需要 遍历每个桶里面的元素，将其分别释放：

~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;}
}

Ⅲ. unordered_set的封装

​ 有了哈希表的框架其实我们对两个 unordered 系列的封装就非常简单了，直接调用哈希表的函数去替我们完成即可！

​ ♻️ 这里的重点和细节仍然是 KeyOfT 的用法而已，具体的可以参考 map 和 set 实现的讲解，这里不过多叙述！

#pragma once
#include "HashTables.h"
namespace liren
{template <class K, class HashFunc = Hash<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:// 取哈希表中的iterator，因为哈希表还没实例化，所以要用typename指定typedef typename LinkHash::hashtable<K, K, SetKeyOfT, HashFunc>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){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);}size_t bucket_count() const{return _ht.bucket_count();}size_t bucket_size(size_t n) const{return _ht.bucket_size(n);}size_t bucket(const K& key){SetKeyOfT kt;return _ht.bucket(key);}private:LinkHash::hashtable<K, K, SetKeyOfT, Hash<K>> _ht;};void testset(){unordered_set<int> st;int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };for (auto e : a)st.insert(e);auto it = st.begin();while (it != st.end()){cout << *it << " ";++it;}cout << endl;for (auto e : a)st.erase(e);}
}

Ⅳ. unordered_map的封装

#pragma once
#include "HashTables.h"namespace liren
{template <class K, class V, class HashFunc = Hash<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:// 取哈希表中的iterator，因为哈希表还没实例化，所以要用typename指定typedef typename LinkHash::hashtable<K, pair<K, V>, MapKeyOfT, HashFunc>::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){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);}size_t bucket_count() const{return _ht.bucket_count();}size_t bucket_size(size_t n) const{return _ht.bucket_size(n);}size_t bucket(const K& key){return _ht.bucket(key);}private:LinkHash::hashtable<K, pair<K, V>, MapKeyOfT, Hash<K>> _ht;};void testmap1(){unordered_map<int, int> mp;int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };for (auto e : a)mp.insert(make_pair(e, e));auto it = mp.begin();while (it != mp.end()){cout << it->first << ":" << it->second << " ";++it;}cout << endl;/*for (auto& e : mp){e.second = 1;cout << e.second << " ";}*///mp[24] = 1;/*for (auto e : a)mp.erase(e);*/it = mp.begin();while (it != mp.end()){cout << it->first << ":" << it->second << " ";it++;}cout << endl;}void testmap2(){unordered_map<int, int> mp;int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };for (auto e : a)mp.insert(make_pair(e, e));auto it = mp.begin();while (it != mp.end()){cout << it->first << ":" << it->second << " ";++it;}cout << endl;cout << mp.bucket_count() << endl;cout << mp.bucket_size(4) << endl;cout << mp.bucket_size(0) << endl;it = mp.begin();while (it != mp.end()){cout << mp.bucket(it->first) << endl;++it;}}
}

在这里插入图片描述


http://www.ppmy.cn/news/1575257.html

相关文章

【Python爬虫(83)】探秘an网数据爬取：合法合规下的技术探索

【Python爬虫(83)】探秘an网数据爬取：合法合规下的技术探索

【Python爬虫】专栏简介&#xff1a;本专栏是 Python 爬虫领域的集大成之作&#xff0c;共 100 章节。从 Python 基础语法、爬虫入门知识讲起&#xff0c;深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑&#xff0c;覆盖网页、图片、音频等各类数据爬取&#xff…
阅读更多...
基于Springboot的小说网站【附源码】

基于Springboot的小说网站【附源码】

基于Springboot的小说网站 效果如下&#xff1a; 系统主页面 书库信息页面 书籍详情页面 推荐信息页面 小说推荐页面 书库信息页面 小说排行榜页面 系统管理页面 研究背景 随着互联网技术的快速发展&#xff0c;网络文学逐渐成为一种新兴的文学形式&#xff0c;吸引了大量读…
阅读更多...
async和await解决回调函数地狱

async和await解决回调函数地狱

目录 目的&#xff1a; 文件名称&#xff1a; 代码解释&#xff1a; 代码&#xff1a; 使用方法&#xff1a; 结论&#xff1a; 以下是代码的详细介绍&#xff0c;以及如何使用它。 目的&#xff1a; 这个示例展示了如何使用 async 和 await 语法来解决传统回调函数&am…
阅读更多...
单片机 Bootloade与二进制文件的生成

单片机 Bootloade与二进制文件的生成

单片机的 Bootloader 是一种特殊的程序&#xff0c;负责在单片机上电后初始化硬件、更新用户应用程序&#xff08;固件&#xff09;&#xff0c;并将控制权移交给用户程序。以下是其运行机制和关键流程的详细说明&#xff1a; 1、单片机 Bootloader 的核心作用 固件更新&…
阅读更多...
【Linux】调试工具GDB的使用及案例讲解

【Linux】调试工具GDB的使用及案例讲解

Linux系列 文章目录 Linux系列前言一、gdb的使用背景二、gdb的使用总结 本篇主要针对小白讲解&#xff0c;可以很多地方比较咯嗦 前言 GDB是Linux下一款强大的调试工具。GDB可以调试C、C、Java等语言&#xff0c;对于在Linux下工作的程序员来说&#xff0c;GDB是必不可少的调试…
阅读更多...
一文2500字从0到1实现压测自动化！

一文2500字从0到1实现压测自动化！

大家好&#xff0c;我是小码哥&#xff0c;最近工作有点忙&#xff0c;一直在实现压测自动化的功能&#xff0c;今天来分享一下实现思路 我所在的业务线现在项目比较少了&#xff0c;所以最近一个月我都没有做业务测试&#xff0c;需求开发完后RD直接走免测就上线&#xff0c;…
阅读更多...
蓝桥杯18582-真人鉴定器

蓝桥杯18582-真人鉴定器

蓝桥杯18582-真人鉴定器 介绍 真人鉴定功能是一种常见的网络安全措施&#xff0c;用于保护网站免受机器人或自动化程序的恶意攻击。该功能基于人类视觉能力&#xff0c;要求用户在访问网站时通过切换右边轮播图&#xff0c;识别与左边要求的图片个数相符的图片&#xff0c;并…
阅读更多...
STM32-智能台灯项目

STM32-智能台灯项目

一、项目需求 1. 红外传感器检测是否有人&#xff0c;有人的话实时检测距离&#xff0c;过近则报警&#xff1b;同时计时&#xff0c;超过固定时间则报警&#xff1b; 2. 按键 1 切换工作模式&#xff1a;智能模式、按键模式、远程模式&#xff1b; 3. 智能模式下&#xff0c;根…
阅读更多...
最新文章

Copyright @ 2022~2023