unordered_map与unordered_set的封装

目录

前言

unordered_set的封装

代码解读

类模板参数

私有嵌套结构 SetKeyOfT

类型别名

公共成员函数

私有成员

insert 函数的详细解读

unordered_map的封装

代码解读

类模板参数

私有嵌套结构 MapKeyOfT

类型别名

公共成员函数

私有成员

operator[] 函数的详细解读

const 版本的 operator[]

前言

unordered_map 和 unordered_set 在 C++ 标准库中是对哈希表的封装。它们是基于哈希桶（开散列）实现的容器，提供了平均常数时间复杂度的插入、查找和删除操作。

  • unordered_map 是一种关联容器，它存储键值对，其中键是唯一的。它使用哈希表来实现，允许快速检索键对应的值。

  • unordered_set 是一种集合容器，它存储唯一的元素。同样基于哈希表实现，用于快速检查元素是否存在于集合中。

以下是 unordered_map 和 unordered_set 的一些关键特性：

  • 哈希表实现：内部使用哈希表来存储元素，这意味着元素是无序的，且通常不保证元素的顺序。

  • 哈希函数：它们使用哈希函数来确定元素在哈希表中的位置。C++ 标准库为常见数据类型提供了默认的哈希函数，也可以为自定义类型提供专门的哈希函数。

  • 处理冲突：当多个元素散列到同一个位置时，unordered_map 和 unordered_set 使用开散列的方法（如分离链接法）来处理冲突。每个哈希桶位置存储一个链表或另一个数据结构，所有散列到该位置的元素都存储在这个结构中。

  • 性能：理想情况下，unordered_map 和 unordered_set 提供了平均常数时间复杂度的操作（O(1)），但最坏情况下可能会退化到线性时间复杂度（O(n)），这通常发生在哈希表的负载因子过高，需要进行重新哈希时。

因此，可以说 unordered_map 和 unordered_set 是对哈希桶的高层抽象，提供了方便的接口来管理基于哈希的元素集合。

unordered_set的封装


namespace My_unordered_set {template <class K, class HashFunc = HashFunc<K>>class unordered_set{private:struct SetKeyOfT{const K& operator()(const K& key){return t;}};public:typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;	//iterator是一个类型，不是实例化的对象typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;iterator begin(){return _table.begin();}const_iterator begin() const{return _table.begin();}iterator end(){return _table.end();}const_iterator end() const{return _table.end();}bool erase(const K& key){return _table.Erase(key);}iterator find(const K& key){return _table.Find(key);}pair<const_iterator, bool> insert(const K& key){//return _table.Insert(key);	//这里返回这个函数，因为它返回pair<iterator, bool>，而我们需要返回pair<const_iterator, bool>auto ret = _table.Insert(key);//用返回的迭代器的成员构造一个const迭代器													//ret.second控制返回是否成功return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);	//构造的这个const_iterator构造完成之后，只能调用const函数（通过Ref与Ptr进行控制）}private:HashTable<K, K, SetKeyOfT, HashFunc> _table;};
}

代码解读

这段代码定义了一个名为 My_unordered_set 的命名空间，其中包含一个模板类 unordered_set。这个类模仿了 C++ 标准库中的 unordered_set，用于存储唯一元素，基于哈希表实现。下面是对这个类的详细解读：

类模板参数

  • K：表示集合中存储的元素类型。
  • HashFunc：表示用于计算哈希值的哈希函数类型，默认为 HashFunc<K>。

私有嵌套结构 SetKeyOfT

这个结构体定义了一个函数对象，它返回其参数的引用。在这个上下文中，它似乎没有被使用，因为它总是返回传入的 key。这可能是一个设计上的失误，因为通常在哈希表中，我们需要一个函数来提取键值。

struct SetKeyOfT
{const K& operator()(const K& key){return key;}
};

类型别名

  • iterator 和 const_iterator：这两个类型别名分别用于定义普通迭代器和常量迭代器。它们是基于 HashTable 类的迭代器类型。

typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;

公共成员函数

  • begin() 和 begin() const：返回一个指向集合中第一个元素的迭代器。
  • end() 和 end() const：返回一个指向集合中最后一个元素之后位置的迭代器。
  • erase(const K& key)：从集合中删除指定的元素，如果元素存在则返回 true，否则返回 false。
  • find(const K& key)：在集合中查找指定的元素，并返回一个迭代器指向该元素，如果未找到则返回 end()。
  • insert(const K& key)：将元素插入集合中，如果元素已存在则不插入，并返回一个 pair，包含一个迭代器指向已存在的或新插入的元素，以及一个布尔值表示插入是否成功。

私有成员

  • _table：这是一个 HashTable 类的实例，用于实际存储集合中的元素。

insert 函数的详细解读

在 insert 函数中，我们尝试将一个元素插入到哈希表中。这里有一个需要注意的地方：

auto ret = _table.Insert(key);
return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);

这里，_table.Insert(key) 返回一个 pair<iterator, bool>，其中 iterator 是 HashTable 的迭代器。为了返回 pair<const_iterator, bool>，我们需要将普通的迭代器转换为常量迭代器。这是通过构造一个 const_iterator 来完成的，它接收与普通迭代器相同的参数：节点指针 _node，指向哈希表的指针 _pht，以及哈希值 _hashi。

总的来说，这个 unordered_set 类是一个简化版的哈希集合实现，它基于一个未在此代码段中定义的 HashTable 类。这个类提供了基本的集合操作，如插入、查找和删除元素。

unordered_map的封装


namespace My_unordered_map
{template<typename K, typename V, class HashFunc = HashFunc<K>>		//map是K/V结构class unordered_map{private:struct MapKeyOfT{const K& operator()(const pair<K, V>& kv) {return kv.first;}}public:typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::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();}bool erase(const K& key){return _ht.Erase(key);}iterator find(const K& key){return _ht.Find(key);}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool>  ret = _table.Insert(pair<K, V>(key, V()));	//总是先执行一次插入return ret.first->second;	//使用迭代器重载的操作符（迭代器行为类似节点指针）}const V& operator[](const K& key) const{pair<iterator, bool>  ret = _table.Insert(pair<K, V>(key, V()));	//总是先执行一次插入return ret.first->second;	//使用迭代器重载的操作符（迭代器行为类似节点指针）}private:HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc> _table;	//借助MapKeyOfT类，获取到的键值K是const修饰过的};}

代码解读

这段代码定义了一个名为 My_unordered_map 的命名空间，其中包含一个模板类 unordered_map。这个类模仿了 C++ 标准库中的 unordered_map，用于存储键值对，其中键是唯一的，基于哈希表实现。下面是对这个类的详细解读：

类模板参数

  • K：表示键的类型。
  • V：表示值的类型。
  • HashFunc：表示用于计算键的哈希值的哈希函数类型，默认为 HashFunc<K>。

私有嵌套结构 MapKeyOfT

这个结构体定义了一个函数对象，它用于从一个键值对 pair<K, V> 中提取键 K。

struct MapKeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
}

类型别名

  • iterator 和 const_iterator：这两个类型别名分别用于定义普通迭代器和常量迭代器。它们是基于 HashTable 类的迭代器类型。

typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::const_iterator const_iterator;

公共成员函数

  • begin() 和 end()：返回一个指向映射中第一个键值对的迭代器。
  • begin() const 和 end() const：返回一个指向映射中第一个键值对的常量迭代器。
  • erase(const K& key)：从映射中删除指定键的键值对，如果键存在则返回 true，否则返回 false。
  • find(const K& key)：在映射中查找指定键的键值对，并返回一个迭代器指向该键值对，如果未找到则返回 end()。
  • insert(const pair<K, V>& kv)：将键值对插入映射中，如果键已存在则不插入，并返回一个 pair，包含一个迭代器指向已存在的或新插入的键值对，以及一个布尔值表示插入是否成功。
  • operator[](const K& key)：允许通过键直接访问或插入值。如果键不存在，则插入一个默认构造的值。

私有成员

  • _table：这是一个 HashTable 类的实例，用于实际存储映射中的键值对。

operator[] 函数的详细解读

operator[] 函数允许通过键直接访问或修改映射中的值。如果键不存在，它会插入一个默认构造的值。

V& operator[](const K& key)
{pair<iterator, bool> ret = _table.Insert(pair<K, V>(key, V())); // 总是先执行一次插入return ret.first->second; // 使用迭代器重载的操作符（迭代器行为类似节点指针）
}

在这个函数中，如果键 key 不存在于映射中，它会创建一个默认构造的值 V() 并与键一起插入到哈希表中。Insert 函数返回一个 pair<iterator, bool>，其中 iterator 指向新插入的键值对或已存在的键值对，bool 表示是否成功插入了新的键值对。然后，我们通过 ret.first->second 返回值的引用。

注意，这里有一个潜在的问题：如果 V 类型没有默认构造函数，或者默认构造函数的行为不是期望的，那么这段代码将无法正常工作。

const 版本的 operator[]

const V& operator[](const K& key) const

这个函数与非常量版本相同，但是它返回一个常量引用，这意味着不能通过这个函数修改值。然而，这段代码似乎有一个错误，因为在一个常量成员函数中调用 Insert 是不允许的，因为 Insert 可能会修改映射。正确的做法是在非常量版本中插入元素，然后在常量版本中仅返回已存在元素的引用。

总结来说，这个 unordered_map 类是一个简化版的哈希映射实现，它基于一个未在此代码段中定义的 HashTable 类。这个类提供了基本的映射操作，如插入、查找、删除键值对，以及通过键直接访问值。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1556123.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

如何只修改obsidian图片链接为markdown

如何只修改obsidian图片链接为markdown

如何只修改obsidian图片链接为markdown 前言插件配置 使用注意 前言 适合有一定了解obsidian用法和插件市场&#xff0c;还有相对路径的人 插件 在obsidian插件市场搜索—开梯子 配置 首先使用ctrlp打开命令面板&#xff0c;也可以在左侧通过图标打开命令面板&#xff0c…
阅读更多...
车载电子电气架构--- 车载诊断DTC全覆盖分类

车载电子电气架构--- 车载诊断DTC全覆盖分类

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 屏蔽力是信息过载时代一个人的特殊竞争力，任何消耗你的人和事，多看一眼都是你的不对。非必要不费力证明自己，无利益不试图说服别人，是精神上的节…
阅读更多...
智能制造的人机料法环的内涵

智能制造的人机料法环的内涵

在生产和管理领域，有个很重要的概念叫 “人、机、料、法、环”。 “人” 就是参与其中的人员，他们的技能、态度、责任心等对事情的结果影响很大； “机” 指的是机器设备和工具等，就像干活要用的家伙事儿，好不好用、正不正常直接关系到工作的效率和质量； “料” 呢，就…
阅读更多...
MathType软件7.9最新版本下载超实用指南

MathType软件7.9最新版本下载超实用指南

嗨&#xff0c;各位学霸、研究僧还有教育界的大佬们&#xff01;&#x1f44b; 今天我要给你们安利的不是一道数学题&#xff0c;也不是一本教科书&#xff0c;而是一款让你分分钟爱上数学的神器——MathType软件&#xff01;&#x1f389; #### &#x1f4da; **MathType是什…
阅读更多...
DataX+Crontab实现多任务顺序定时同步

DataX+Crontab实现多任务顺序定时同步

DataX+Crontab实现多任务顺序定时同步 前言 DataX 是一款支持在异构数据源之间离线同步数据的工具， DataX 通过输入一些命令执行 json 配置文件，这样使用起来并不是很方便， DataX 也不支持定时任务调度，它仅支持一次性同步任务。所以 DataX 的这些特点造成了它无法完成一些…
阅读更多...
S7-200 SMART Modbus RTU常见问题

S7-200 SMART Modbus RTU常见问题

1.S7-200 SMART 是否支持 Modbus ASCII 通信模式&#xff1f; STEP 7-Micro/WIN SMART 软件未提供Modbus ASCII 通信模式指令库。S7-200 SMART CPU若用于Modbus ASCII 通信时&#xff0c;则需要用户使用自由口通信模式进行编程。 2.S7-200 SMART CPU 集成的RS485 端口&#xf…
阅读更多...
YOLOv10改进，YOLOv10添加CA注意力机制，二次创新C2f结构，助力涨点

YOLOv10改进，YOLOv10添加CA注意力机制，二次创新C2f结构，助力涨点

改进前训练结果： 二次创新C2f结构训练结果： 摘要 在本文中，提出了一种新的移动网络注意力机制，将位置信息嵌入到信道注意力中称之为“协调注意力”。与渠道关注不同通过 2D 全局池将特征张量转换为单个特征向量，坐标注意力因子将通道注意力转化为两个 1D 特征编码过程…
阅读更多...
STAR数据集：首个用于大型卫星图像中场景图生成大规模数据集

STAR数据集：首个用于大型卫星图像中场景图生成大规模数据集

2024-06-12&#xff0c;在遥感图像领域&#xff0c;由武汉大学等机构联合创建的STAR数据集&#xff0c;标志着场景图生成技术在大规模、高分辨率卫星图像中的新突破。 一、研究背景&#xff1a; 场景图生成(Scene Graph Generation, SGG)技术在自然图像中已取得显著进展&#…
阅读更多...
[C语言]指针和数组

[C语言]指针和数组

目录 1.数组的地址 2.通过指针访问数组 3.数组和指针的不同点 4.指针数组 1.数组的地址 数组的地址是什么&#xff1f; 看下面一组代码 #include <stdio.h> int main() { int arr[5] {5,4,3,2,1}; printf("&arr[0] %p\n", &arr[0]); printf(&qu…
阅读更多...
个人网站，怎么操作才能提升个人网站的流量

个人网站，怎么操作才能提升个人网站的流量

运营个人网站以提升流量是一个综合性的过程&#xff0c;涉及内容优化、技术调整、用户体验提升以及外部推广等多个方面。以下是一些专业建议&#xff0c;旨在帮助个人网站运营者有效提升网站流量&#xff1a; 1.精准关键词研究与优化 -关键词研究&#xff1a;利用工具如谷歌…
阅读更多...
【YOLO学习】YOLOv3详解

【YOLO学习】YOLOv3详解

文章目录 1. 网络结构1.1 结构介绍1.2 改进 2. 训练与测试过程3. 总结 1. 网络结构 1.1 结构介绍 1. 与 YOLOv2 不同的是&#xff0c;YOLOv3 在 Darknet-19 里加入了 ResNet 残差连接&#xff0c;改进之后的模型叫 Darknet-53。在 ImageNet上 实验发现 Darknet-53 相对于 ResN…
阅读更多...
数据结构与算法篇（树 - 常见术语）

数据结构与算法篇（树 - 常见术语）

目录 一、什么是树&#xff1f; 二、相关术语 根结点 边 叶子结点 兄弟结点 祖先结点 结点的大小 树的层 结点的深度 结点的高度 树的高度 斜树 一、什么是树&#xff1f; 树是一种类似于链表的数据结构&#xff0c;不过链表的结点是以线性方式简单地指向其后继结…
阅读更多...
ORB-SLAM复现时遇到的问题（复现失败，切莫当做教程）

ORB-SLAM复现时遇到的问题（复现失败，切莫当做教程）

背景 本人的环境&#xff1a;使用ubuntu20.04&#xff0c;opencv4 问题 进行Build DBoW2. Go into Thirdparty/DBoW2/ and execute:时&#xff0c;运行make时出错 我安装的opencv4&#xff0c;在 OpenCV 3 和更高版本中&#xff0c;头文件的路径可能已更改。例如&#xff0…
阅读更多...
[单master节点k8s部署]32.ceph分布式存储（三）

[单master节点k8s部署]32.ceph分布式存储（三）

基于ceph rbd生成pv 在集群中认证ceph 用下面代码生成ceph的secret .创建 ceph 的 secret&#xff0c;在 k8s 的控制节点操作&#xff1a; 回到 ceph 管理节点创建 pool 池&#xff1a; [rootmaster1-admin ~]# ceph osd pool create k8stest 56 pool k8stest created [rootm…
阅读更多...
免费音频剪辑软件大揭秘：让声音创作更轻松

免费音频剪辑软件大揭秘：让声音创作更轻松

在精神娱乐越发丰富的现在&#xff0c;音频内容的创作和编辑变得越来越重要。无论是专业的音乐制作人&#xff0c;还是自媒体创作者&#xff0c;都可能需要一款功能强大且易于使用的音频剪辑软件来处理音频素材。今天我们一同来探讨有什么好用的免费音频剪辑软件吧。 1.福昕音…
阅读更多...
golang gin入门

golang gin入门

gin是个小而精的web开发框架 官方文档 安装 go get -u github.com/gin-gonic/gin最简单的起手代码 package mainimport ("net/http""github.com/gin-gonic/gin" )func main() {r : gin.Default()r.GET("/ping", func(c *gin.Context) {c.JSON…
阅读更多...
Java IO流全面教程

Java IO流全面教程

此笔记来自于B站黑马程序员 File 创建对象 public class FileTest1 {public static void main(String[] args) {// 1.创建一个 File 对象&#xff0c;指代某个具体的文件// 路径分隔符// File f1 new File("D:/resource/ab.txt");// File f1 new FIle("D:\\…
阅读更多...
nodejs 构建高性能服务器的关键技术

nodejs 构建高性能服务器的关键技术

nodejs 构建高性能服务器的关键技术 演示地址 演示地址 源码地址 源码地址 获取更多 获取更多 在现代 Web 开发中&#xff0c;Node.js 已成为构建高性能、可扩展网络应用的首选平台之一。它的非阻塞 I/O 模型与事件驱动架构使其能够在处理大量并发请求时表现出色&#xff0…
阅读更多...
【C++11】新特性

【C++11】新特性

前言&#xff1a; C11 是C编程语言的一个重要版本&#xff0c;于2011年发布。它带来了数量可观的变化&#xff0c;包含约 140 个新特性&#xff0c;以及对 C03 标准中约600个缺陷的修正&#xff0c;更像是从 C98/03 中孕育出的新语言 列表初始化 C11 中的列表初始化&#xff0…
阅读更多...
【自用】王道文件管理强化笔记

【自用】王道文件管理强化笔记

文章目录 操作系统引导:磁盘初始化文件打开过程角度1文件的打开过程角度2 内存映射的文件访问 操作系统引导: ①CPU从一个特定主存地址开始&#xff0c;取指令&#xff0c;执行ROM中的引导程序(先进行硬件自检&#xff0c;再开机) ②)将磁盘的第一块–主引导记录读入内存&…
阅读更多...
最新文章

Copyright @ 2022~2023