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

【AI大模型】DeepSeek + 通义万相高效制作AI视频实战详解

【AI大模型】DeepSeek + 通义万相高效制作AI视频实战详解

目录 一、前言 二、AI视频概述 2.1 什么是AI视频 2.2 AI视频核心特点 2.3 AI视频应用场景 三、通义万相介绍 3.1 通义万相概述 3.1.1 什么是通义万相 3.2 通义万相核心特点 3.3 通义万相技术特点 3.4 通义万相应用场景 四、DeepSeek + 通义万相制作AI视频流程 4.1 DeepSeek + 通义万相制作视频优势 4.1.1 DeepSeek 优势 4.1.2 通义万相视频生成优势 4.2

By Ne0inhk
【DeepSeek微调实践】DeepSeek-R1大模型基于MS-Swift框架部署/推理/微调实践大全

【DeepSeek微调实践】DeepSeek-R1大模型基于MS-Swift框架部署/推理/微调实践大全

系列篇章💥 No.文章01【DeepSeek应用实践】DeepSeek接入Word、WPS方法详解：无需代码，轻松实现智能办公助手功能02【DeepSeek应用实践】通义灵码 + DeepSeek：AI 编程助手的实战指南03【DeepSeek应用实践】Cline集成DeepSeek：开源AI编程助手，终端与Web开发的超强助力04【DeepSeek开发入门】DeepSeek API 开发初体验05【DeepSeek开发入门】DeepSeek API高级开发指南（推理与多轮对话机器人实践）06【DeepSeek开发入门】Function Calling 函数功能应用实战指南07【DeepSeek部署实战】DeepSeek-R1-Distill-Qwen-7B：本地部署与API服务快速上手08【DeepSeek部署实战】DeepSeek-R1-Distill-Qwen-7B：Web聊天机器人部署指南09【DeepSeek部署实战】DeepSeek-R1-Distill-Qwen-7B：基于vLLM 搭建高性能推理服务器10【DeepSeek部署实战】基于Ollama快速部署Dee

By Ne0inhk

DeepSeek各版本说明与优缺点分析_deepseek各版本区别

DeepSeek各版本说明与优缺点分析 DeepSeek是最近人工智能领域备受瞩目的一个语言模型系列，其在不同版本的发布过程中，逐步加强了对多种任务的处理能力。本文将详细介绍DeepSeek的各版本，从版本的发布时间、特点、优势以及不足之处，为广大AI技术爱好者和开发者提供一份参考指南。 1. DeepSeek-V1：起步与编码强劲 DeepSeek-V1是DeepSeek的起步版本，这里不过多赘述，主要分析它的优缺点。 发布时间： 2024年1月 特点： DeepSeek-V1是DeepSeek系列的首个版本，预训练于2TB的标记数据，主打自然语言处理和编码任务。它支持多种编程语言，具有强大的编码能力，适合程序开发人员和技术研究人员使用。 优势： * 强大编码能力：支持多种编程语言，能够理解和生成代码，适合开发者进行自动化代码生成与调试。 * 高上下文窗口：支持高达128K标记的上下文窗口，能够处理较为复杂的文本理解和生成任务。 缺点： * 多模态能力有限：该版本主要集中在文本处理上，缺少对图像、语音等多模态任务的支持。 * 推理能力较弱：尽管在自然语言

By Ne0inhk

用DeepSeek和Cursor从零打造智能代码审查工具：我的AI编程实践

💂 个人网站:【 摸鱼游戏】【神级代码资源网站】【星海网址导航】摸鱼、技术交流群👉 点此查看详情 引言：AI编程革命下的机遇与挑战 GitHub统计显示，使用AI编程工具的开发者平均效率提升55%，但仅有23%的开发者能充分发挥这些工具的潜力。作为一名全栈工程师，我曾对AI编程持怀疑态度，直到一次紧急项目让我彻底改变了看法。客户要求在72小时内交付一个能自动检测代码漏洞、优化性能的智能审查系统，传统开发方式根本不可能完成。正是这次挑战，让我探索出DeepSeek和Cursor这对"黄金组合"的惊人潜力。 一、工具选型：深入比较主流AI编程工具 1.1 为什么最终选择DeepSeek+Cursor？ 经过两周的对比测试，我们发现不同工具在代码审查场景的表现差异显著： 工具代码理解深度响应速度定制灵活性多语言支持GitHub Copilot★★★☆★★★★★★☆★★★★Amazon CodeWhisperer★★☆★★★☆★★★★★★☆DeepSeek★★★★☆★★★★★★★☆★★★★☆Cursor★★★☆★★★★☆★★★★★★★★ 关键发现： * Dee

By Ne0inhk