尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
map, set的封装
map, set的封装1、共用同一棵树2、提取Key值的仿函数3、第一个模板参数Key4、Iterator5、Key值不支持修改6、map的重载[]7、析构实现了红黑树我们就要对红黑树做进一步封装map, set以能够供实际工程上的使用。对红黑树封装成map, set我们参考SGI-STL30版本的源代码。我们对封装的要求是(实现红黑树)实现共用同一棵树实现提取Key值的仿函数实现iterator和const_iterator实现Key值不支持修改的方式实现map的重载[]1、共用同一棵树我们知道数据结构set存储数据采用的是key策略而map存储数据采用的是key-value策略。而实际上STL30版本实现的map, set使用了同一种红黑树。那么STL30是如何做到同一棵红黑树实现两种不同存储数据的方式的呢如上图这是STL30用红黑树封装map时向红黑树rb_tree中传递的模板参数。第二个模板参数是value_typevalue_type其实是一个重命名这个重命名恰好是map节点存储的pair数据的类型。我们再观察STL30实现的rb_tree以及rb_tree节点的定义向rb_tree的模板参数Value处传入map的pairKey, Value类型那么最终编译器就会实例化出存储数据类型为pairKey, Value的红黑树节点类型。整个实例化过程是这样的同理我们也可以简单图示用红黑树实例化出set类的过程事实上我们可以借助STL30的做法自己来简单封装红黑树为map, set。2、提取Key值的仿函数在某些场景下我们需要提取Key值。比如实现insert()插入一个节点的方法时为了向下搜寻新节点的位置我们必须将新节点与每一层的某一个节点进行Key值的比较。而此刻我们封装map, set时事先不知道节点数据类型到底是什么也就不能轻易地直接让节点数据直接比较。我们可以在map, set内定义一个仿函数然后通过模板参数传入红黑树中在比较Key值之前将Key值提取出来以map为例给出提取data中Key值的全过程对“提取Key值的仿函数”一节内容的勘误向RBTree中直接传入提取Key值仿函数的模板名是不对的因为只传入了模板名编译器不知道你想实例化哪个版本的仿函数。所以要实例化即填入模板参数。建议把仿函数写在map, set的外部并且类型写成struct更规范3、第一个模板参数Key我们给底层的RBTree设置的模板参数列表的第一个位置是用来传递Key值类型的因为我们会实现诸如Find(), Erase()的方法。比如Find()需要直接传入Key类型的值以进行查找。为了方便区分我们干脆再传入一个Key类型。4、IteratorRBTree迭代器的实现思路与链表非常相似都是将节点指针封装成一个类然后重载相关运算符的行为。*解引用与-解引用!与重载如何重载即如何找到RBTree的后继分三种情况如果当前节点存在右子树那么后继为右子树的最左节点。如果当前节点不存在右子树而当前节点恰好是其父节点的左孩子那么后继为父节点。如果当前节点不存在右子树而当前节点是其父节点的右孩子这时应向祖先溯源直至找到孩子是父亲的左节点然后返回这个父亲。Begin()和End()如何实现Begin()找到RBTree中序最左节点即可如何实现End()目前我们的做法是返回nullptr构造的迭代器const迭代器的创建也是很重要的我们可以参考链表的const迭代器制作RBTree的const迭代器。map, set的迭代器就是RBTree迭代器的封装。5、Key值不支持修改mao, set中Key值是不支持修改的。我们可以在传入底层RBTree的模板参数上加上const但是要注意传入RBTree的T类型要与传入RBTreeIterator的T类型保持一致上图在封装RBTree迭代器为map, set迭代器时添加了typename。这是因为RBTree还没有实例化那么RBTreeIterator也就还没有实例化。这里添加typename是告诉编译器这是一个类类型而不是静态成员变量。下面验证const迭代器有效性时也遇到了要添加typename的情况这里也告诉了编译器这是一个类型。虽然模板参数给的是一个不确定的T但是加上typename相当于请求编译器通过编译。未来调用模板函数时编译器就可以通过传入的参数推导出T是什么类型进而实例化出一个确定的const迭代器类型。6、map的重载[]我们先回忆一下map的重载[]是什么(*((this-insert(make_pair(k,mapped_type()))).first)).second// mapped_type其实就是Key-Value策略里的Value值使用map的重载[]首先是试图向底层RBTree插入一个节点如果没找到存有相同Key值的节点那么就执行insert()插入方法也就是插入成功。然后insert()返回被插入节点的迭代器和bool值(true)进而通过这个迭代器找到节点最终找到Value值。如果找到了存有相同Key值的节点那么插入失败。insert()返回被找到存有相同Key值的节点的迭代器(和false)通过这个迭代器找到Value值。我们应该将insert()改造成这样然后修改对应的函数返回值即可。注意到需要向上调整节点颜色的情况。此时cur并不一定是新插入的节点。在这种场景下我们需要另外记录新插入节点{的地址)。接着外层set, map的insert()也要跟着修改。7、析构析构主要采取递归的思路。当然我们也可以理清这些需求的思路其它思路也可以以完善map, setoperator–拷贝构造函数代码
RELATED

相关推荐

Blender操作可视化神器:Screencast Keys让你的教程制作轻松10倍

Blender操作可视化神器:Screencast Keys让你的教程制作轻松10倍

Blender操作可视化神器:Screencast Keys让你的教程制作轻松10倍 【免费下载链接】Screencast-Keys Blender Add-on: Screencast Keys 项目地址: https://gitcode.com/gh_mirrors/sc/Screencast-Keys 还在为Blender教程录制时观众看不清你的操作步骤而烦恼吗&…

📅 2026/9/11 23:14:57
交易所密钥管理:多重签名与多方计算技术解析与实践指南

交易所密钥管理:多重签名与多方计算技术解析与实践指南

1. 项目概述:为什么密钥管理是交易所的“命门”?在加密货币的世界里,流传着一句老话:“Not your keys, not your coins.”(不是你的密钥,就不是你的币)。这句话道出了资产所有权的核心——密钥即…

📅 2026/10/14 11:36:46
VC++窗口程序开发指南:从WinMain到消息循环的完整实现

VC++窗口程序开发指南:从WinMain到消息循环的完整实现

1. 项目概述:从零构建一个VC窗口程序如果你刚接触VC,想在VS2010这个经典环境中创建一个最基础的窗口程序,可能会被一堆陌生的术语和步骤搞懵。什么WinMain、窗口类、消息循环,听起来就头大。别担心,这篇指南就是为你准…

📅 2026/10/13 12:12:23
MORE NEWS

更多资讯

📰

低压电工证几年一复审在哪考最靠谱?别再交冤枉钱了

低压电工证几年一复审在哪考最靠谱?别再交冤枉钱了 怕考不过白交培训费?低压电工证几年一复审, 在哪考 直接决定你能不能顺利拿证,也关系到你以后的就业和薪资。很多电工师傅都遇到过,培训费交了,考试不过,钱打水漂。今天就从一个许昌劳务班组负责人…

📰

工地太忙根本没时间复习考试?电工证怎么样的?怎么报名最省心?

工地太忙根本没时间复习考试?电工证怎么样的?怎么报名最省心? 工地太忙根本没时间复习考试,这是大多数一线作业人员的真实写照。特别是像你这样刚毕业、刚进工地的应届生,面对繁重的施工任务,还要抽时间备考电工证,简直是雪上加霜。但你得明白,…

📰

特种作业操作证巴中怎么考?学历不高怕报不上名?这些干货帮你搞定!

特种作业操作证巴中怎么考?学历不高怕报不上名?这些干货帮你搞定! 你是不是也这样,想考特种作业操作证,但又担心自己学历不高,报不上名?其实, 特种作业操作证巴中…

📰

人在国外 电工证复审最新内部消息:工地太忙根本没时间复习考试

人在国外 电工证复审最新内部消息:工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,这几乎是所有一线电工在复审时的真实写照,尤其是那些 人在国外…

📰

开封电工证查寻怎么查电子证书

开封电工证查寻怎么查电子证书 你是不是也遇到过这种情况,证书过期了,但又不知道怎么复审延期?这种时候,找到正确的信息和流程就显得格外重要,特别是现在很多地方都在推行电子证书, 开封电工证查寻 和电子证书的管理,也变得更加高效和透明了。…

📰

办理电工证兰州:证书过期了不知道怎么复审延期?通过率揭秘全在这里

办理电工证兰州:证书过期了不知道怎么复审延期?通过率揭秘全在这里 证书过期了不知道怎么复审延期?兰州地区的电工证办理和复审流程,其实没有你想象的那么复杂,但如果不了解规则,确实会让人头疼。尤其是很多工人朋友在操作证到期后,才发现自己不知道该…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬