C++：用红黑树封装map与set-2

Ne0inhk

— 14 min read
C++：用红黑树封装map与set-2
在这里插入图片描述

文章目录

前言

前面我们map与set封装的已经差不多了，接下来还有一些细节需要处理，本片博客主要解决const迭代器以及引发的一些其他问题~😘😘

总后的总结完整的源码封装的源码附上~🥰🥰

想看前面的封装是怎么实现的戳这里哦宝宝~❤️❤️
<(￣︶￣)↗[GO!]

一、红黑树封装map与set中const迭代器

1. 框架的搭建

首先，和以前一样，要写出const迭代器，和以前一样通过控制三个模板参数，从而控制operator*以及operator->的返回值，从而控制普通迭代器与const迭代器。

在这里插入图片描述

改变模板参数，控制返回值：

在这里插入图片描述

2. set实现const迭代器

set的data中储存的是key，而且set是key的模型，我们说key是不可以被改变的，无论你是普通迭代器还是const迭代器，key都不可以被改变。

因此，这里set普通迭代器与set const迭代器都是RBTree::const迭代器，就达到了这样的效果：

在这里插入图片描述
tips：注意这里要加typename，模板类内的东西要在外部使用要告诉编译器哦

因此，我们在封装的时候要这样写：

在这里插入图片描述


这里的iterator是什么呢？是普通的迭代器吗？

答：不是的，这里我们typedef了，这里其实是红黑树中的const_iterator。

3. map实现const迭代器

map与set不同，对于set来说，data中存储的是key，因此直接让它的普通迭代器与const迭代器都是const迭代器。

但是！对于map来说就不一样了，map的data中存储的是
pair<key, calue>，对于pair.first是不可以修改的，对于pair.second是需要修改的，如果直接将普通迭代器与const迭代器都是const迭代器，那么pair.first与pair.second都不能修改了。

因此我们需要想出其他的方法！

这里的解决方法是，将map的pair<key, calue>变为pair<const key, calue>，从一开始就限制key是不能够修改的，因此迭代器正常走就可以了~

在这里插入图片描述

二、operator[ ]

1. operator[ ]要达成的样子

对于map来说，因为map是key-value，因此我们要存在operator[ ]，

  1. 通过[ ]进行插入
  2. 通过[ ]通过key改变value

因此我们实现operator[ ]是一定要借助insert的。
这里我们前面详细分析过，具体的分析过程戳这里哦宝

○( ＾皿＾)っHiahiahia…

2. insert的改变

通过前面的分析我们知道了，为了实现上述的目的，insert的返回值需要变成一个pair，

在这里插入图片描述

因此：

在这里插入图片描述


当然，RBTree.h中的insert改了，对应的map与set也要相应的更改：

以下是我们的测试代码：

jyf::map<int,int> m; m.insert(make_pair(1,1)); m.insert(make_pair(3,3)); m.insert(make_pair(2,2));//bit::map<int, int>::iterator mit = m.begin();auto mit = m.begin();while(mit != m.end()){// 不能修改key，可以修改value//mit->first = 1; mit->second =2; cout << mit->first <<":"<< mit->second << endl;++mit;} cout << endl;//func(m);for(constauto& kv : m){ cout << kv.first <<":"<< kv.second << endl;} cout << endl; jyf::set<int> s; s.insert(5); s.insert(2); s.insert(2); s.insert(12); s.insert(22); s.insert(332); s.insert(7); jyf::set<int>::iterator it = s.begin();while(it != s.end()){// 不应该允许修改key/* if (*it % 2 == 0) { *it += 10; }*/ cout <<*it <<" ";++it;} cout << endl;

但是，但是中的但是，就算我们改完了之后还是编译不通过：

在这里插入图片描述

我们看到这里，map好像没问题了，唯一出问题的就是set，因此我们要解决这个问题。

三. 解决insert里set中的问题

那么set为什么会出问题呢？
问题出在set中普通迭代器与const迭代器都是const迭代器！

如下图：

在这里插入图片描述

那这里怎么解决呢？

首先我们来套一层：

用pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret来接收Insert的返回值，因此在ret中，pair的iterator是普通的iterator。

然后又用ret.first 与 ret.second来构造pair返回，也就是说pair是不能直接构造的时候这里first用const迭代器来构造，因此需要套一层，最后用普通迭代器构造cosnt迭代器。

pair<iterator,bool>insert(const K& key){ pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);return pair<iterator,bool>(ret.first, ret.second);}

但是只是这样还是编译不通过，还是老问题~

这是因为我们没有提供用普通迭代器构造const迭代器的构造函数：
解决方案如下：

在这里插入图片描述


这样我们的编译就可以通过了：

在这里插入图片描述

四. 解决map中的operator[ ]

V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;}

以下是测试代码：

jyf::map<string, string> dict; dict.insert(make_pair("sort","xxx")); dict["left"];// 插入for(constauto& kv : dict){ cout << kv.first <<":"<< kv.second << endl;} cout << endl; dict["left"]="左边";// 修改 dict["sort"]="排序";// 修改 dict["right"]="右边";// 插入+修改for(constauto& kv : dict){ cout << kv.first <<":"<< kv.second << endl;} cout << endl;

运行结果为：

在这里插入图片描述

总结用红黑树封装map与set代码

RBTree.h
#pragmaonce#include<iostream>usingnamespace std;enumColour{ RED, BLACK };template<classT>structRBTreeNode{ RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col; T _data;RBTreeNode(const T& data):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_data(data){}};template<classT,classPtr,classRef>struct__TreeIterator{typedef RBTreeNode<T> Node;typedef __TreeIterator<T, Ptr, Ref> Self;// 解决insert中set的问题typedef __TreeIterator<T, T*, T&> iterator;__TreeIterator(const iterator& it):_node(it._node){}; Node* _node;__TreeIterator(Node* node):_node(node){} Ref operator*(){return _node->_data;} Ptr operator->(){return&(_node->_data);}booloperator!=(const Self& s){return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;} Self&operator++(){if(_node->_right !=nullptr){ Node* curleft = _node->_right;while(curleft->_left){ curleft = curleft->_left;} _node = curleft;}else{// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点 Node* cur = _node; Node* parent = _node->_parent;while(parent){if(parent->_left == cur){break;}else{ cur = parent; parent = parent->_parent;}} _node = parent;}return*this;} Self&operator--(){if(_node->_left){ Node* subRight = _node->_left;while(subRight->_right){ subRight = subRight->_right;} _node = subRight;}else{// 孩子是父亲的右的那个节点 Node* cur = _node; Node* parent = cur->_parent;while(parent && cur == parent->_left){ cur = cur->_parent; parent = parent->_parent;} _node = parent;}return*this;}};template<classK,classT,classKeyOfT>classRBTree{typedef RBTreeNode<T> Node;public:// 同一个类模板，传的不同的参数实例化出的不同类型typedef __TreeIterator<T, T*, T&> iterator;typedef __TreeIterator<T,const T*,const T&> const_iterator; iterator begin(){ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returniterator(leftMin);} iterator end(){returniterator(nullptr);} const_iterator begin()const{ Node* leftMin = _root;while(leftMin && leftMin->_left){ leftMin = leftMin->_left;}returnconst_iterator(leftMin);} const_iterator end()const{returnconst_iterator(nullptr);} Node*Find(const K& key){ Node* cur = _root; KeyOfT kot;while(cur){if(kot(cur->_data)< key){ cur = cur->_right;}elseif(kot(cur->_data)> key){ cur = cur->_left;}else{return cur;}}returnnullptr;} pair<iterator,bool>Insert(const T& data){// 树为空，直接插入然后返回if(_root ==nullptr){ _root =newNode(data);// 根节点必须是黑色 _root->_col = BLACK;returnmake_pair(iterator(_root),true);} Node* cur = _root; Node* parent =nullptr; KeyOfT kot;while(cur){// 小于往左走if(kot(data)<kot(cur->_data)){ parent = cur; cur = cur->_left;}elseif(kot(data)>kot(cur->_data))// 大于往右走{ parent = cur; cur = cur->_right;}else{returnmake_pair(iterator(cur),false);}} cur =newNode(data);// 其他结点初始颜色为红色 cur->_col = RED;// 记录cur用于改变颜色后还能找到cur来返回 Node* newnode = cur;// 链接if(kot(cur->_data)<kot(parent->_data)){ parent->_left = cur;}else{ parent->_right = cur;} cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while(parent && parent->_col == RED){// 首先我们要找到grandfather Node* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif(parent == grandfather->_left){// 说明uncle在右边 Node* uncle = grandfather->_right;// uncle存在且为红if(uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续向上调整 cur = grandfather; parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else// uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if(cur == parent->_left){// g// p// cRotateR(grandfather);// 调整颜色 parent->_col = BLACK; grandfather->_col = RED;}else// 左右双旋{// g// p// cRotateL(parent);RotateR(grandfather);// 调整颜色 cur->_col = BLACK; grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}}else//(parent == grandfather->_right) // 如果parent是grandfather->_right{// 说明uncle在左边 Node* uncle = grandfather->_left;// uncle存在且为红if(uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色 parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;// 继续向上调整 cur = grandfather; parent = cur->_parent;}else// uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if(cur == parent->_right){// g// p// cRotateL(grandfather);// 调整颜色 parent->_col = BLACK; grandfather->_col = RED;}else// 右左双旋{// g// p// cRotateR(parent);RotateL(grandfather);// 调整颜色 cur->_col = BLACK; grandfather->_col = RED;}break;}}}// 这里保证根为黑色 _root->_col = BLACK;returnmake_pair(iterator(newnode),true);}// 左单旋voidRotateL(Node* parent){ Node* cur = parent->_right; Node* curleft = cur->_left;// 重新链接 parent->_right = curleft;if(curleft)// 如果curleft存在{ curleft->_parent = parent;} cur->_left = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ _root = cur; cur->_parent =nullptr;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 右单旋voidRotateR(Node* parent){ Node* cur = parent->_left; Node* curright = cur->_right; parent->_left = curright;if(curright){ curright->_parent = parent;} cur->_right = parent; Node* ppnode = parent->_parent; parent->_parent = cur;if(ppnode ==nullptr){ cur->_parent =nullptr; _root = cur;}else{if(ppnode->_left == parent){ ppnode->_left = cur;}else{ ppnode->_right = cur;} cur->_parent = ppnode;}}// 检查是否构建正确boolCheckColour(Node* root,int blacknum,int benchmark){if(root ==nullptr){if(blacknum != benchmark)returnfalse;returntrue;}if(root->_col == BLACK){++blacknum;}if(root->_col == RED && root->_parent && root->_parent->_col == RED){ cout <<kot(root->data)<<"出现连续红色节点"<< endl;returnfalse;}returnCheckColour(root->_left, blacknum, benchmark)&&CheckColour(root->_right, blacknum, benchmark);}boolIsBalance(){returnIsBalance(_root);}boolIsBalance(Node* root){if(root ==nullptr)returntrue;if(root->_col != BLACK){returnfalse;}// 基准值int benchmark =0; Node* cur = _root;while(cur){if(cur->_col == BLACK)++benchmark; cur = cur->_left;}returnCheckColour(root,0, benchmark);}private: Node* _root =nullptr;};
myset.h
#pragmaonce#include"RBTree.h"namespace jyf {template<classK>classset{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator iterator;typedeftypenameRBTree<K, K, SetKeyOfT>::const_iterator const_iterator; iterator begin()const{return _t.begin();} iterator end()const{return _t.end();} pair<iterator,bool>insert(const K& key){ pair<typenameRBTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);return pair<iterator,bool>(ret.first, ret.second);}private: RBTree<K, K, SetKeyOfT> _t;};}
mymap.h
#pragmaonce#include"RBTree.h"namespace jyf {template<classK,classV>classmap{structMapKeyOfT{const K&operator()(const pair<const K, V>& kv){return kv.first;}};public:typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;typedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin(){return _t.begin();} iterator end(){return _t.end();} const_iterator begin()const{return _t.begin();} const_iterator end()const{return _t.end();} V&operator[](const K& key){ pair<iterator,bool> ret =insert(make_pair(key,V()));return ret.first->second;} pair<iterator,bool>insert(const pair<K, V>& kv){return _t.Insert(kv);}private: RBTree<K, pair<const K, V>, MapKeyOfT> _t;};}
test.cpp
#include<iostream>#include<string>usingnamespace std;#include"mymap.h"#include"myset.h"//void func(const jyf::map<int, int>& m)//{// //auto mit = m.begin();// jyf::map<int, int>::const_iterator mit = m.begin();// while (mit != m.end())// {// // 不能修改key，不能修改value// //mit->first = 1;// //mit->second = 2;//// cout << mit->first << ":" << mit->second << endl;// ++mit;// }// cout << endl;//}intmain(){ jyf::map<int,int> m; m.insert(make_pair(1,1)); m.insert(make_pair(3,3)); m.insert(make_pair(2,2));//bit::map<int, int>::iterator mit = m.begin();auto mit = m.begin();while(mit != m.end()){// 不能修改key，可以修改value//mit->first = 1; mit->second =2; cout << mit->first <<":"<< mit->second << endl;++mit;} cout << endl;//func(m);for(constauto& kv : m){ cout << kv.first <<":"<< kv.second << endl;} cout << endl; jyf::set<int> s; s.insert(5); s.insert(2); s.insert(2); s.insert(12); s.insert(22); s.insert(332); s.insert(7); jyf::set<int>::iterator it = s.begin();while(it != s.end()){// 不应该允许修改key/* if (*it % 2 == 0) { *it += 10; }*/ cout <<*it <<" ";++it;} cout << endl;//for (const auto& e : s)//{// cout << e << " ";//}//cout << endl; jyf::map<string, string> dict; dict.insert(make_pair("sort","xxx")); dict["left"];// 插入for(constauto& kv : dict){ cout << kv.first <<":"<< kv.second << endl;} cout << endl; dict["left"]="左边";// 修改 dict["sort"]="排序";// 修改 dict["right"]="右边";// 插入+修改for(constauto& kv : dict){ cout << kv.first <<":"<< kv.second << endl;} cout << endl;return0;}

🥰🥰🥰到这里就结束啦，创作不易，如果感觉对您有帮助的话，求求一个一键三连，谢谢各位大佬~🥰🥰🥰

在这里插入图片描述

Read more

假网站排全网第二，真官网翻五页都找不到！NanoClaw创始人破防：SEO之战，我快要输了

假网站排全网第二，真官网翻五页都找不到！NanoClaw创始人破防：SEO之战，我快要输了

整理 | 苏宓 出品 | ZEEKLOG（ID：ZEEKLOGnews） 自从 OpenClaw 爆火之后，各种“Claw”项目接连出现，其中以安全优化版 NanoClaw 最为知名。它的核心代码仅有 4000 行，却获得了 AI 大牛 Andrej Karpathy 的点赞。 可谁也没想到，这款口碑极佳的开源项目，近来竟被一个仿冒网站抢了风头。 投诉无门之下，NanoClaw 创始人 Gavriel Cohen 在 X 社交平台上无奈发文怒斥：谷歌搜索错误地将假网站排在真官网前面，不仅破坏了项目声誉，还埋下了严重的安全隐患，而他费尽心力，却只能哀叹一句——“我正在为自己的开源项目打 SEO 战，但我快要输了。” 那么，NanoClaw 究竟发生了什么？又是怎么走红的？事情还要从 OpenClaw

By Ne0inhk
曝Windows 12将于今年发布？以AI为核心、NPU成「硬件门槛」，网友吐槽：“不想要的全塞进来了”

曝Windows 12将于今年发布？以AI为核心、NPU成「硬件门槛」，网友吐槽：“不想要的全塞进来了”

整理 | 郑丽媛 出品 | ZEEKLOG（ID：ZEEKLOGnews） 当年，微软一句“Windows 10 将是最后一个版本”的表态，让不少用户以为 Windows 进入了“只更新、不换代”的时代。但几年过去，现实却完全不同。 在 Windows 11 发布之后，如今关于 Windows 12 的传闻再次密集出现。从内部代号、代码片段，到硬件厂商的暗示与 OEM 预热标签，种种线索拼在一起，勾勒出一个明显的趋势——这不会只是一次常规升级，而更像是一次围绕 AI 的平台级重构。 更关键的是，这次争议，可能远比当年 TPM 2.0 更大。 精准卡位 Windows 10 退场的时间？

By Ne0inhk
“裸奔龙虾”数量已达27万只，业内人士警告；AI浪潮下，中传“砍掉”翻译等16个专业；薪资谈判破裂，三星电子8.9万人要罢工 | 极客头条

“裸奔龙虾”数量已达27万只，业内人士警告；AI浪潮下，中传“砍掉”翻译等16个专业；薪资谈判破裂，三星电子8.9万人要罢工 | 极客头条

「极客头条」—— 技术人员的新闻圈！ ZEEKLOG 的读者朋友们好，「极客头条」来啦，快来看今天都有哪些值得我们技术人关注的重要新闻吧。（投稿或寻求报道：[email protected]） 整理 | 郑丽媛 出品 | ZEEKLOG（ID：ZEEKLOGnews） 一分钟速览新闻点！ * “裸奔龙虾”已高达27万只！业内人士警告：一旦黑客入侵，敏感信息一秒搬空 * 阿里云 CTO 周靖人代管千问模型一号位，刘大一恒管理更多团队 * 中国传媒大学砍掉翻译、摄影等 16 个本科专业，直言教育要面向人机分工时代 * 雷军放话：小米将很快推出 L3、L4 的驾驶 * 消息称原理想汽车智驾一号位郎咸朋具身智能赛道创业 * vivo 前产品经理宋紫薇创业，瞄准 AI 时尚Agent，获亿元融资 * MiniMax 发布龙虾新技能，股价暴涨超 23% * 薪资谈判破裂，三星电子

By Ne0inhk
Python热度下滑、AI能取代搜索引擎？TIOBE最新榜单揭晓！

Python热度下滑、AI能取代搜索引擎？TIOBE最新榜单揭晓！

整理 | 屠敏 出品 | ZEEKLOG（ID：ZEEKLOGnews） 日前，TIOBE 发布了最新的 3 月编程语言榜单。整体来看，本月排名变化不算大，但榜单中仍然出现了一些值得关注的小波动。  AI 工具能帮大家秒懂最新编程语言趋势？ 由于 2 月天数较少，3 月的榜单整体变化有限。借着这次发布，TIOBE CEO Paul Jansen 也回应了一个最近被频繁讨论的问题：为什么 TIOBE 指数仍然依赖搜索引擎统计结果？在大语言模型流行的今天，直接询问 AI 哪些编程语言最流行，是不是更简单？ 对此，Jansen 的回答是否定的。 他解释称，TIOBE 指数本质上统计的是互联网上关于某种编程语言的网页数量。而大语言模型的训练数据同样来自这些网页内容，因此从信息来源来看，两者并没有本质区别。换句话说，LLM 的判断，本质上也是建立在这些网页数据之上的。 Python 活跃度仍在下降

By Ne0inhk