《C++进阶之STL》【set/map 模拟实现】

【set/map 模拟实现】目录

• 前言：
• ------------标准介绍------------
  • 1. 标准库中的set/map是怎么实现的呢？
  • 2. 为什么需要两个模板参数（Key & Value）？
• ------------模拟实现------------
  • 头文件：
    • RBTree.h
    • Myset.h
    • Mymap.h
  • 测试文件：Test.cpp
  • 运行结果
• ------------基本操作------------
  • 一、前置++操作
    • 1. 本质
    • 2. 步骤
    • 3. 图示
    • 4. 解释
  • 二、前置--操作
    • 1. 本质
    • 2. 步骤
    • 3. 图示
    • 4. 解释
• ------------代码解释------------
  • 片段一：仿函数的设计
  • 片段二：迭代器的设计
    • 1. begin()迭代器接口函数
    • 2. end()迭代器接口函数
    • 3. 迭代器不可修改性的适配

往期《C++初阶》回顾：

《C++初阶》目录导航

往期《C++进阶》回顾：
/------------ 继承多态 ------------/
【普通类/模板类的继承 + 父类&子类的转换 + 继承的作用域 + 子类的默认成员函数】
【final + 继承与友元 + 继承与静态成员 + 继承模型 + 继承和组合】
【多态：概念 + 实现 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索树】
【AVL树】
【红黑树】
【set/map 使用介绍】

前言：

hi~ 小伙伴们大家好呀！(ﾉ･ω･)ﾉﾞ
首先温馨提醒一下，今天可是充满感恩与敬意的教师节哦~ (๑•̀ㅂ•́)و✧
在此也向所有在学习路上给予我们指导和帮助的老师们道一声：节日快乐，您辛苦了！ʕ•̀ω•́ʔ♡

言归正传，书接上回我们详细介绍的 【set/map 使用介绍】，相信大家已经对 set 和 map 的基本概念、常用接口以及实际应用场景有了清晰的认识~ (≧ڡ≦*)ゞ而今天，我们的学习重点将更进一步，深入探讨 【set/map 模拟实现】 ！
有了二叉搜索树、AVL 树以及红黑树这些前置知识的铺垫，从理论上来说，模拟实现 set 和 map 已经不再是遥不可及的难题~
但是，大家可千万不能因此掉以轻心！在实际的模拟实现过程中，封装细节的处理可谓是重中之重，里面其实藏着不少需要仔细琢磨的考究之处哦~ (ﾟ∀ﾟ)☆

------------标准介绍------------

1. 标准库中的set/map是怎么实现的呢？

在 SGI - STL30 版本的源代码里，map 和 set 相关的实现代码分布在 map、set、stl_map.h、stl_set.h、stl_tree.h 等几个头文件中。

下面我们就看一看 map 和 set 实现结构框架的部分核心内容：

/*---------------------- set/map 容器的声明于包含----------------------*/// set 容器相关声明与包含#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_set.h>#include<stl_multiset.h>// map 容器相关声明与包含#ifndef__SGI_STL_INTERNAL_TREE_H#include<stl_tree.h>#endif#include<stl_map.h>#include<stl_multimap.h>/*---------------------- set/map 类模板定义----------------------*/// stl_set.h 中 set 类模板定义template<classKey,classCompare= less<Key>,classAlloc= alloc>classset{public:// typedefs:typedef Key key_type;typedef Key value_type;private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing set};// stl_map.h 中 map 类模板定义template<classKey,classT,classCompare= less<Key>,classAlloc= alloc>classmap{public:// typedefs:typedef Key key_type;typedef T mapped_type;typedef pair<const Key, T> value_type;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t;// red-black tree representing map};/*----------------------红黑树 节点基类/类模板 定义----------------------*/// stl_tree.h 中红黑树节点基类定义struct__rb_tree_node_base{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr; color_type color; base_ptr parent; base_ptr left; base_ptr right;};template<classKey,classValue,classKeyOfValue,classCompare,classAlloc= alloc>classrb_tree{protected:typedefvoid* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;typedef rb_tree_node* link_type;typedef Key key_type;typedef Value value_type;public:// insert用的是第二个模板参数左形参 pair<iterator,bool>insert_unique(const value_type& x);// erase和find用第一个模板参数做形参 size_type erase(const key_type& x); iterator find(const key_type& x);protected: size_type node_count;// keeps track of size of tree link_type header;};// stl_tree.h 中红黑树节点类模板定义template<classValue>struct__rb_tree_node:public__rb_tree_node_base{typedef __rb_tree_node<Value>* link_type; Value value_field;};

红黑树（rb_tree）泛型设计思想解析

通过对框架的分析，我们能看到 SGI STL 源码中 rb_tree 的泛型设计非常巧妙它不直接写死“仅支持 key 搜索” 或 “仅支持 key/value 搜索”而是通过第二个模板参数 Value 灵活控制：红黑树节点（__rb_tree_node）中实际存储的数据类型，由 Value 决定

这样一颗红黑树，既能适配 set 的 “纯 key 搜索场景”，也能适配 map 的 “key/value 搜索场景”。

set & map 对 rb_tree 的实例化差异set 的场景：当 set 实例化 rb_tree 时，给第二个模板参数传入纯 key 类型（如：set<int> 中，Value 就是 int）红黑树节点直接存储 key，自然适配 “仅按 key 搜索、不重复存储” 的需求map 的场景：当 map 实例化 rb_tree 时，给第二个模板参数传入键值对类型 pair<const Key, T>（如：map<int, string> 中，Value 是 pair<const int, string>）红黑树节点存储完整的键值对，从而支持 “按 key 关联 value” 的搜索逻辑

注意事项：关于 value_type 的特殊含义源码里的模板参数常用 T 代表 “节点存储的数据类型（即这里的 Value）”而 rb_tree 内部定义的 value_type，并非我们日常说的 “key/value 里的 value”，而是红黑树节点实际存储的数据的类型（对 set 是 key 类型，对 map 是 pair<const Key, T> 类型 ）

2. 为什么需要两个模板参数（Key & Value）？

很多小伙伴们可能会疑惑：既然 rb_tree 的第二个参数 Value 已经决定了节点存储的数据类型，为什么还要单独传第一个参数 Key，尤其是set，这两个模板参数都是⼀样的，这是为什么呢？

核心原因在于 find/erase 等操作的入参需求：对 set 和 map 来说：find/erase 函数的参数是 Key 类型（按 key 查找、删除），而非完整的节点数据（Value 类型）对 set 而言：Key 和 Value 类型相同（节点存 key，操作也用 key），所以两个模板参数看似冗余，但是这样做主要是为了和map容器保持统一的接口对 map 而言：Key（操作入参类型）和 Value（节点存储的键值对类型）完全不同 ——map 插入的是 pair 对象，但查找、删除只用 Key

因此：Key 模板参数的意义是 为 find/erase 等函数提供形参类型，让红黑树能统一支撑 set（Key 与 Value 同类型）和 map（Key 与 Value 不同类型）的场景。

简而言之：SGI STL 通过模板参数的分层职责（Value 控制节点存储类型，Key 控制操作入参类型 ）让 rb_tree 成为一套 “万能骨架”，向上完美适配 set（纯 key 场景）和 map（key/value 场景），体现了泛型编程的灵活性与复用性

------------模拟实现------------

头文件：

RBTree.h

#pragmaonce//任务1：包含需要使用的头文件#include<iostream>#include<vector>#include<time.h>usingnamespace std;//任务2：定义节点颜色的“枚举”enumColour{ RED,// 红色节点 BLACK // 黑色节点};//任务3：定义红黑树的节点的“结构体模板”template<classT>structRBTreeNode{/*--------------------------成员变量--------------------------*///1.节点存储的数据//2.左子节点的指针//3.右子节点的指针//4.父节点的指针 //5.节点的颜色 T _data; RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; Colour _col;/*--------------------------成员函数--------------------------*///实现：红黑树节点的“构造函数”RBTreeNode(const T& data):_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}/* 注意事项：“封装set和map时候底层实现的红黑树”和“之前我们直接实现的红黑树”的模板的区别 * 1. 封装set和map时的红黑树：template<class T> * 2. 直接实现的红黑树：template <class K,class V> * * 解释：通过上面两种模板的对比，我们可以很直观的看出来两种实现的“模板参数的数量是不同的” * 封装set和map时的红黑树只使用一个模板参数，是因为我们要利用这个红黑树不仅要实现set还要实现map * 所以说：模板参数T不仅可以是：键key；还可以是：键值对pair<K,V> */};//任务4：定义红黑树迭代器的“结构体模板” ---> 支持双向遍历template<classT,classRef,classPtr>structRBTreeIterator{/*--------------------------类型别名--------------------------*///1.重命名红黑树节点的类型：RBTreeNode<T> ---> Nodetypedef RBTreeNode<T> Node;//2.重命名红黑树迭代器的类型：RBTreeIterator<T,Ref,Ptr> ---> Selftypedef RBTreeIterator<T, Ref, Ptr> Self;/*--------------------------成员变量--------------------------*///1.当前指向的节点 Node* _node;//2.红黑树的根节点 Node* _root;/*--------------------------成员函数--------------------------*///1.实现：红黑树迭代器“构造函数”RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}//2.实现：“*运算符的重载” Ref operator*(){return _node->_data;}/* 注意事项： * 1. 函数的返回值：引用 * 2. 函数的函数体：直接返回当前指针指向的节点中存储的“数据”即可 *///3.实现：“->运算符的重载” Ptr operator->(){return&_node->_data;}/* 注意事项： * 1. 函数的返回值：指针 * 2. 函数的函数体：直接返回当前指针指向的节点中存储的“数据的地址”即可 *///4.实现：“==运算符的重载”booloperator==(const Self& s)const{return _node == s._node;}/* 注意事项： * 1. 函数的形式参数：常量的迭代器 * 2. 函数的函数体：直接判断“当前指针”和“传入的迭代器的指针”是否相等即可 *///5.实现：“!=运算符的重载”booloperator!=(const Self& s)const{return _node != s._node;}//6.实现：“前置++运算的重载” ---> 作用：找中序遍历下一个节点 Self operator++(){//情况1：当前节点的右子树“不为空”---> 中序下一个节点是“右子树的最左节点（右子树最小值）”if(_node->_right){/*------------准备------------*///1.定义右子树的最左节点（右子树的最小节点）的指针 Node* min = _node->_right;/*------------寻找------------*///2.使用while循环找到“右子树的最左节点”while(min->_left){ min = min->_left;}/*------------赋值------------*///3.让当前节点指向右子树的最左节点 _node = min;}//情况2：当前节点的右子树“为空”---> 中序下一个节点是“向上查找第一个祖先，且当前节点是该祖先的左子节点”else{/*------------准备------------*///1.定义当前节点的指针 Node* current = _node;//2.定义当前节点的父节点的指针 Node* parent = _node->_parent;//或者写成：Node* parent = current->_parent;/*------------寻找------------*///3.使用while循环找到“当前节点是该节点的祖先节点的左子节点的那个祖先节点”while(parent && current == parent->_right){//3.1：更新当前节点：之前的当前节点的父节点作为现在的当前节点 current = parent;//3.2：更新父节点：之前的祖父节点最为现在的当前节点的父节点 parent = parent->_parent;//或者写成：parent = current -> _parent;}/*注意事项：上面的while循环中的判断条件为什么是“(parent && parent->_right)” * 1. current == parent->_right： * 我们的目的是找到“当前节点是该祖先节点的左子节点的祖先节点”,所以说， * 如果当前遍历到节点是“右子节点”的话，就还要进行寻找 * 2. parent： * 当在不断的寻找的过程中current变成根节点话，这说明current又回到的根节点， * 这一棵红黑树已经被遍历完成了，找不到满足上面要求的根节点了，parent就会更新为nullptr， * 跳出了while循环 *//*------------赋值------------*///4.让当前节点指向该祖先节点 _node = parent;}return*this;}//7.实现：“前置--运算符的重载” ---> 作用：找中序遍历前一个节点 Self operator--(){//情况1：当前节点为空 ---> 中序前一个节点是“整棵树最右边的节点（最后一个节点）”if(_node ==nullptr){/*------------准备------------*///1.定义指向整棵树最右边的节点 Node* last = _root;/*------------寻找------------*///2.使用while循环找到“整棵树最右变的节点”while(last && last->_right)//注意：这里的while循环条件要添加“last”{ last = last->_right;}/*------------赋值------------*///3.让当前节点指向整棵树的最右节点 _node = last;}/* 注意事项1：为什么实现“前置++运算符”的时候没有讨论当前节点为空的情况，但是实现“前置--运算符”的时候要进行讨论呢？ * 回答：当指向红黑树的节点的指针为空指针的时候 * 1. 如果使用的是“前置++”遍历红黑树的话（迭代器正向遍历），此时说明红黑树中节点都已经遍历完毕了 * 2. 如果使用的是“前置--”遍历红黑树的话（迭代器反向遍历），此时说明红黑树中一个节点都还没访问呢 * 所以说：这里实现“当前节点为空”的情况就是为了处理“--end()”的情况 *//* 注意事项2：上面的情况1中while的循环条件要添加last，而情况2中while的循环条件中不添加max？ * 回答：这是一个非常细节的问题，那下面我们详细的解释一下这是为什么？ * 1. 首先是情况1：可能会有这棵树为空树的情况，也就是说last = _root =nullptr * 2. 其次是情况2：_node->_left确保存在，因此max = _node->_left必然非空，循环只需检查max->_right是否为空，无需担心max本身为空 * *///情况2：当前节点的左子树“不为空”---> 中序前一个节点是“左子树的最右节点（左子树最大值）”elseif(_node->_left){/*------------准备------------*///1.定义左子树的最右节点（左子树的最大节点）的指针 Node* max = _node->_left;/*------------寻找------------*///2.使用while循环找到“左子树的最右节点”while(max->_right){ max = max->_right;}/*------------赋值------------*///3.让当前节点指向左子树的最右节点 _node = max;}//情况3：当前节点的左子树“为空”---> 中序下一个节点是“向上查找第一个祖先，且当前节点是该祖先的右子节点”else{/*------------准备------------*///1.定义当前节点的指针 Node* current = _node;//2.定义当前节点的父节点的指针 Node* parent = _node->_parent;/*------------寻找------------*///3.使用while循环找到“当前节点是该节点的祖先节点的右子节点的那个祖先节点”while(parent && current == parent->_left){//3.1：更新当前节点：之前的当前节点的父节点作为现在的当前节点 current = parent;//3.2：更新父节点：之前的祖父节点最为现在的当前节点的父节点 parent = parent->_parent;//或者写成：parent = current -> _parent;}/*------------赋值------------*///4.让当前节点指向该祖先节点 _node = parent;}return*this;}};//任务5：定义红黑树的“类模板”template<classK,classT,classKeyOfT>classRBTree{private:/*--------------------------成员变量--------------------------*/ RBTreeNode<T>* _root =nullptr;//红黑树根节点的指针/*--------------------------类型别名--------------------------*///1.重命名红黑树节点的类型：RBTreeNode<T> ---> Nodetypedef RBTreeNode<T> Node;/*--------------------------成员函数（私有）--------------------------*///1.实现：“获取树的高度”int_Height(Node* root){/*------------处理“特殊情况 + 递归出口”------------*/if(root ==nullptr){return0;}/*------------处理“正常情况”------------*///1.递归计算出左子树的高度int leftHeight =_Height(root->_left);//2.递归计算出右子树的高度int rightHeight =_Height(root->_right);//3.树的高度 = 左子树/右子树中的最大高度 + 1return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}//2.实现：“获取节点的数量”intSize(Node* root){/*------------处理“特殊情况 + 递归出口”------------*/if(root ==nullptr){return0;}/*------------处理“正常情况”------------*///树中节点的数量 = 左子树节点的数量 + 右子树节点的数量 + 1return_Size(root->_left)+_Size(root->_right)+1;}public:/*--------------------------类型别名--------------------------*///2.重命名红黑树“普通迭代器”的类型：RBTreeIterator<T, T&, T*> ---> Iteratortypedef RBTreeIterator<T, T&, T*> Iterator;//3.重命名红黑树“常量迭代器”的类型：RBTreeIterator<T, const T&, const T*> ---> ConstIteratortypedef RBTreeIterator<T,const T&,const T*> ConstIterator;/* 注意事项：这里我们要将上面的两个迭代器添加到RBTree类模板的public访问权限下面 * 因为：在封装set和map时候我们要重新对这两个迭代器进行重命名 *//*--------------------------成员函数（公有）--------------------------*///1.实现：“获取树的普通起始迭代器” ---> 中序遍历第一个节点，即最左节点 Iterator Begin(){//1.定义指向当前节点的指针 Node* current = _root;//2.使用while循环找到最左节点while(current && current->_left)//注意：这里条件中有一个current为了防止根节点是空节点{ current = current->_left;}//3.返回最左节点的迭代器returnIterator(current, _root);}//2.实现：“获取树的普通终止迭代器” ---> 指向假想的尾后节点 Iterator End(){returnIterator(nullptr, _root);}//3.实现：“获取树的常量起始迭代器” ConstIterator Begin()const{//1. Node* current = _root;//2.while(current && current->_left){ current = current->_left;}//3.returnConstIterator(current, _root);}//4.实现：“获取树的常量终止迭代器” ConstIterator End()const{returnConstIterator(nullptr, _root);}//5.实现：“查找操作” Node*Find(const K& key)//注意：根据键key进行查找，类似二叉搜索树中查找操作{//1.定义进行遍历节点的指针 Node* curr = _root;//2.使用while循环查找对应节点while(curr){//情况1：当前遍历到的节点的键 < 要查找的键 ---> “继续向当前节点的右子树中查找”//if (curr->_kv.first < key)if(kot(curr->_data)< key){ curr = curr->_right;}//情况2：当前遍历到的节点的键 > 要查找的键 ---> “继续向当前节点的左子树中查找”//else if (curr->_kv.first > key)elseif(kot(curr->_data)> key){ curr = curr->_left;}//情况3：当前遍历到的节点的键 = 要查找的键 ---> “找到了要查找的键”else{return curr;}}//3.跳出了循环，说明没有找到的键为key的节点returnnullptr;}//6.实现：“插入操作”//bool Insert(const pair<K, V>& kv) //直接实现的红黑树（其实就是当红黑树中只插入“键值对”时候的情况） pair<Iterator,bool>Insert(const T& data)//封装set和map时候的红黑树（其实就是当红黑树中既有可能插入“键”又有可能插入“键值对”时候的情况）{/*--------处理“特殊情况 + 递归出口”--------*/if(_root ==nullptr){//1.创建新节点//_root = new Node(kv);  _root =newNode(data);//2.将新节点染色为黑色 (*相比AVL树多了这一步骤*) _root->_col = BLACK;//3.返回true即可//return true;//3.返回“迭代器 + 布尔值”的二元组return{Iterator(_root,_root),true};//自动走隐式类型转换//return pair<Iterator, bool>(Itertor(_root,_root), true); //显示指定了类型}/*--------处理“正常情况”--------*//*----------------第一阶段：准备阶段----------------*///1.创建一个指向当前节点的指针 Node* current = _root;//2.创建一个指向当前节点的父节点的指针 Node* parent =nullptr;//3.创建一个用于提取键的函数对象 KeyOfT kot;/*----------------第二阶段：查找阶段----------------*/while(current)//循环查找插入位置{//情况1：当前遍历到的节点的键 < 要插入的键 ---> “继续寻找”//if (current->_kv.first < kv.first) if(kot(current->_data)<kot(data)){//1.更新当前遍历节点的父节点  parent = current;//不同之处1：这里的需要更新parent指针的位置 //原因：下面我们要在curr指针指向的位置进行插入操作，所以我们需要记录当前遍历到节点的父节点//2.继续去右子树中寻找 current = current->_right;}//情况2：当前遍历到的节点的键 > 要插入的键 ---> “继续寻找”//else if (current->_kv.first > kv.first)elseif(kot(current->_data)>kot(data)){ parent = current; current = current->_left;//继续去左子树中寻找}//情况3：当前遍历到的节点的键 = 要插入的键 ---> “键已存在”---> 查找插入位置失败else{//return false;return{Iterator(current,_root),false};}}//注意：能执行到此处，说明在第二阶段成功跳出了while循环，并非因return false终止程序，//这意味着已找到插入节点的位置，那下面就让我们插入节点吧/*----------------第三阶段：插入阶段----------------*///1.创建要插入的节点//current = new Node(kv); current =newNode(data);//2.重新定义指针指向新插入的节点 (*注意这一步的细节*) Node* newNode = current;//解释：current可能会继续向上更新，所以说其可能指向的不一定是新插入的节点，需要使用newnode指针唯一的指向//3.将新节点染为红色 (*相比AVL树多了这一步骤*) current->_col = RED;//4.将新节点连接到二叉搜索树中 ---> 注意并不能简单的进行插入操作要先判断：// “新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到父节点的左子节点还是右子节点”//情况1：新节点的键 < 父节点的键//if (kv.first < parent->_kv.first)if(kot(data)<kot(parent->_data)){ parent->_left = current;}//情况2：新节点的键 > 父节点的键else//注意：这里使用else表面上看是：满足key >= parent->_key条件的情况都可以执行下面的代码{//但其实key = parent->_key这种情况在上面的第二阶段中已经被的return false排除掉了 parent->_right = current;}/*------------------声明：如果是普通的二叉搜索树，到这里插入操作就已经算作是结束了，但是对于平衡二叉搜索树还有步骤------------------*//*----------------第四阶段：连接阶段----------------*///1.更新新插入节点的父节点 current->_parent = parent;//这里之所以要进行更新是因为，红黑树节点的存储了三个指针，也就是其底层是用“三叉链”的结构进行存储的/*----------------第五阶段：调整阶段----------------*/while(parent && parent->_col == RED)//不断地进行调整，直至：“parent为空节点”或“parent节点颜色为黑色”{//1.获取祖父节点（父节点的父节点） Node* grandfather = parent->_parent;//2.处理需要进行调整的场景//场景一：父节点是祖父节点的左孩子节点if(parent == grandfather->_left){//情况1：叔叔节点“存在”且为“红色” ---> “变色处理” Node* uncle = grandfather->_right;if(uncle && uncle->_col == RED){/*-------第一步：变色处理-------*///1.将“父节点”染为“黑色”//2.将“叔叔节点”染为“黑色”//3.将“祖父节点”染为“红色” parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;//注意：处理完上面这一种仅仅需要变色的情况之后，调整还没结束还需要向上继续进行检查/*-------第二步：向上检查-------*///1.“祖父节点”变为“当前节点” current = grandfather;//2.“父节点”变为“祖父节点的父节点” parent = grandfather->_parent;//或者写成：parent = current->_parent;}//情况2：叔叔节点“不存在”或为“黑色” ---> “旋转处理”else{//情况2.1：当前节点是父节点的左孩子 ---> “右单旋”if(current == parent->_left){/*-------第一步：旋转处理-------*///1.右单旋“祖父节点”RotateR(grandfather);/*-------第一步：变色处理-------*///1.将“父节点”染为“黑色”//2.将“祖父节点”染为“红色” parent->_col = BLACK; grandfather->_col = RED;}//情况2.2：当前节点是父节点的右孩子 ---> “左右双旋”else{/*-------第一步：旋转处理-------*///1.先左单旋“父节点”RotateL(parent);//2.再右单旋“祖父节点”RotateR(grandfather);/*-------第二步：变色处理-------*///1.将“当前节点”染为“黑色”//2.将“祖父节点”染为“红色” current->_col = BLACK; grandfather->_col = RED;}//处理完上面的两种需要进行旋转的情况之后，就可以跳出while循环了break;}}//场景二：父节点是祖父节点的右孩子节点 (注意：场景二其实和场景一的本质是一样的，区别在于两者由于镜像的关系所以两者的旋转操作的是相反的)else{//情况1：叔叔节点“存在”且为“红色” ---> “变色处理” Node* uncle = grandfather->_left;if(uncle && uncle->_col == RED){/*-------第一步：变色处理-------*///1.将“父节点”染为“黑色”//2.将“叔叔节点”染为“黑色”//3.将“祖父节点”染为“红色” parent->_col = BLACK; uncle->_col = BLACK; grandfather->_col = RED;//注意：处理完上面这一种仅仅需要变色的情况之后，调整还没结束还需要向上继续进行检查/*-------第二步：向上检查-------*///1.“祖父节点”变为“当前节点” current = grandfather;//2.“父节点”变为“祖父节点的父节点” parent = grandfather->_parent;//或者写成：parent = current->_parent;}//情况2：叔叔节点“不存在”或为“黑色” ---> “旋转处理”else{//情况2.1：当前节点是父节点的右孩子 ---> “左单旋”if(current == parent->_right){/*-------第一步：旋转处理-------*///1.左单旋“祖父节点”RotateL(grandfather);/*-------第一步：变色处理-------*///1.将“父节点”染为“黑色”//2.将“祖父节点”染为“红色” parent->_col = BLACK; grandfather->_col = RED;}//情况2.2：当前节点是父节点的左孩子 ---> “右左双旋”else{/*-------第一步：旋转处理-------*///1.先右单旋“父节点”RotateR(parent);//2.再左单旋“祖父节点”RotateL(grandfather);/*-------第二步：变色处理-------*///1.将“当前节点”染为“黑色”//2.将“祖父节点”染为“红色” current->_col = BLACK; grandfather->_col = RED;}//处理完上面的两种需要进行旋转的情况之后，就可以跳出while循环了break;}}//场景二结束}//调整阶段结束//1.根节点强制染黑 _root->_col = BLACK;//2.返回新节点的迭代器和插入成功的标识//return true;return{Iterator(newNode,_root),true};}//Insert函数结束//7.实现：“右单旋操作”voidRotateR(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的左子节点的“指针”//2.记录parent的左子节点的右子节点的“指针”//3.记录parent的父节点的“指针” Node* subL = parent->_left; Node* subLR = parent->_left->_right;//或者写成：Node* subLR = subL->_right; Node* pParent = parent->_parent;/*---------------第二阶段：调整阶段---------------*///1.调整parent和subLR的关系 parent->_left = subLR;if(subLR)//注意细节：subLR不一定存在，所以这里为了判断防止对空指针进行解引用，先使用if对subLR指针进行一个判断{ subLR->_parent = parent;}//2.调整parent和subL的关系 parent->_parent = subL; subL->_right = parent;//3.调整根节点或祖父节点的子树指向//情况1：parent节点是根节点 ---> 调整根节点if(parent == _root){//1.调整根节点 _root = subL;//注意：这里的调整根节点要写成：_root = subL，千万不要写成了subL = _root;//2.更新subL的父节点 subL->_parent =nullptr;//或者写成：_root->_parent =nullptr;}//情况2：parent节点不是根节点 ---> 调整祖父节点的子树指向else{//1.调整祖父节点的子树指向if(parent == pParent->_left){ pParent->_left = subL;}else{ pParent->_right = subL;}//2.更新subL的父节点 subL->_parent = pParent;}////4.更新平衡因子 ---> 右单旋后subL和parent的平衡因子均为0//subL->_bf = 0;//parent->_bf = 0;//注意：对于红黑树由于没有使用“平衡因子”所以旋转结束后并不需要更新平衡因子}//8.实现：“左单旋操作”voidRotateL(Node* parent){/*---------------第一阶段：准备阶段---------------*///1.记录parent的右子节点的“指针//2.记录parent的右子节点的左子节点的“指针”//3.记录parent的父节点的“指针” Node* subR = parent->_right; Node* subRL = parent->_right->_left;//或者写成：Node* subLR = subL->_left; Node* pParent = parent->_parent;/*---------------第二阶段：调整阶段---------------*///1.调整parent和subRL的关系 parent->_right = subRL;if(subRL){ subRL->_parent = parent;}//2.调整parent和subR的关系 parent->_parent = subR; subR->_left = parent;//3.调整根节点或祖父节点的子树指向//情况1：parent节点是根节点 ---> 调整根节点if(pParent ==nullptr)//或者写成：parent == _root{//1.调整根节点 _root = subR;//2.更新subL的父节点 subR->_parent =nullptr;//或者写成：_root->_parent = nullptr;}//情况2：parent节点不是根节点 ---> 调整祖父节点的子树指向else{//1.调整祖父节点的子树指向if(parent == pParent->_left){ pParent->_left = subR;}else{ pParent->_right = subR;}//2.更新subL的父节点 subR->_parent = pParent;}////4.更新平衡因子 ---> 左单旋后subR和parent的平衡因子均为0//subR->_bf = 0;//parent->_bf = 0;}//9.实现：“获取树的高度”intHeight(){return_Height(_root);}//10.实现：“获取节点的个数”intSize(){return_Size(_root);}};

Myset.h

#pragmaonce#include"RBTree.h"namespace mySpace {//任务：定义set容器的类模板template<classK>classset{private:/*--------------------------成员函数（私有）--------------------------*///1.实现：仿函数“从元素中提起键” （注意：set中容器中元素本来就是键）structSetKeyOfT{//1.重载()运算符const K&operator()(const K& key){return key;}};/*--------------------------成员变量--------------------------*/ RBTree<K,const K, SetKeyOfT> _t;/* 注意事项： * 1. 底层数据结构：红黑树 * 2. 模板参数： * K ---> “键类型” * const K ---> “值类型”，set中键就是值，且不可修改 * setKeyOfT ---> “键提取器”， */public:/*--------------------------类型别名--------------------------*///1.重新定义红黑树的“普通迭代器”：Iterator ---> iteratortypedeftypenameRBTree<K,const K, SetKeyOfT>::Iterator iterator;//2.重新定义红黑树的“常量迭代器”：ConstIterator ---> const_iterartortypedeftypenameRBTree<K,const K, SetKeyOfT>::ConstIterator const_iterator;/*--------------------------成员函数（公有）--------------------------*///1.实现：“获取树的普通起始迭代器” iterator begin(){return _t.Begin();}//2.实现：“获取树的普通终止迭代器” iterator end(){return _t.End();}//3.实现：“获取树的常量起始迭代器” const_iterator begin()const{return _t.Begin();}//4.实现：“获取树的常量终止迭代器” const_iterator end()const{return _t.End();}//5.实现：“插入操作” pair<iterator,bool>insert(const K& key){return _t.Insert(key);}};}

Mymap.h

#pragmaonce#include"RBTree.h"namespace mySpace {//任务：定义map容器的类模板template<classK,classV>classmap{private:/*--------------------------成员变量（私有）--------------------------*///1.实现：仿函数“从元素中提取键”structMapKeyOfT{//1.重载()运算符const K&operator()(const pair<K, V>& kv){return kv.first;}};/*--------------------------成员变量--------------------------*/ RBTree<K, pair<const K, V>, MapKeyOfT> _t;/* 注意事项： * 1. 底层数据结构：红黑树 * 2. 模板参数： * K ---> “键类型” * pair<const K, V> ---> “值类型”，map中键不可修改，值可以进行修改 * MapKeyOfT ---> “键提取器” */public:/*--------------------------类型别名--------------------------*///1.重新定义红黑树的“普通迭代器”：Iterator ---> iteratortypedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;//2.重新定义红黑树的“常量迭代器”：ConstIterator ---> const_iterartortypedeftypenameRBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;/*--------------------------成员变量（公有）--------------------------*///1.实现：“获取树的普通起始迭代器” iterator begin(){return _t.Begin();}//2.实现：“获取树的普通终止迭代器” iterator end(){return _t.End();}//3.实现：“获取树的常量起始迭代器” const_iterator begin()const{return _t.Begin();}//4.实现：“获取树的常量终止迭代器” const_iterator end()const{return _t.End();}//5.实现：“插入操作” pair<iterator,bool>insert(const pair<K,V>& kv){return _t.Insert(kv);}//6.实现：“下标运算符重载” V&operator[](const K& key){//1.先调用insert接口函数尝试插入新键值对 pair<iterator,bool> ret =insert({ key,V()});//2.再返回键值对的第二个元素return ret.first->second;/* * ret：二元组 ---> 使用.运算符访问 * ret.first：迭代器 --->使用->运算符访问 */}/* 注意事项： * 1.当键存在时：返回对应值的引用 * * 2.当键不存在时：插入新键值对，并返回其引用 */};}

测试文件：Test.cpp

#define_CRT_SECURE_NO_WARNINGS1#include"Myset.h"#include"Mymap.h"//1.实现：“反向打印set容器中的元素的函数”（演示逆向迭代器的使用）voidPrint(const mySpace::set<int>& s){//1.定义指向set容器终止位置的迭代器 mySpace::set<int>::const_iterator it = s.end();//2.从end()开始逆向遍历到begin()while(it != s.begin()){--it; cout <<*it <<" ";} cout << endl;}intmain(){ cout <<"--------------------测试set的功能--------------------"<< endl; mySpace::set<int> s;/*------------------测试：插入的功能------------------*/ s.insert(5);//红黑树会自动维护元素的有序性 s.insert(1); s.insert(3); s.insert(2); s.insert(6);/*------------------测试：迭代器的使用------------------*///1.定义set容器的迭代器 mySpace::set<int>::iterator sit = s.begin();// *sit += 10; // 错误：Set元素不可修改（类型为const K）//2.使用正向迭代器遍历set（中序遍历，元素按升序排列） cout <<"使用迭代器进行遍历set容器中的元素"<< endl;while(sit != s.end()){ cout <<*sit <<" ";++sit;} cout << endl;//3.使用范围for循环遍历set（底层使用迭代器实现） cout <<"使用范围for循环遍历set容器中的元素"<< endl;for(auto& it : s){ cout << it <<" ";} cout << endl;//*------------------测试：逆向迭代器的功能------------------*/ cout <<"反向打印set容器中的元素"<< endl;Print(s); cout <<"--------------------测试map的功能--------------------"<< endl; mySpace::map<string, string> dict;/*------------------测试：插入的功能------------------*/ cout <<"向map容器中插入的三个键值对的内容是："<< endl; dict.insert({"sort","排序"}); dict.insert({"left","左边"}); dict.insert({"right","右边"});for(auto& kv : dict){ cout << kv.first <<":"<< kv.second << endl;} cout << endl;/*------------------测试：下标访问运算符的功能------------------*/ cout <<"修改left + 插入insert、string + 将所有的键值对的值都加上一个！ 之后map容器中的内容是："<< endl;//1.使用[]运算符修改已有键的值 dict["left"]="左边，修改";//2.使用[]运算符插入新键值对（若键不存在） dict["insert"]="插入";//3.使用[]访问不存在的键，会插入默认值（空字符串） dict["string"];/*------------------测试：迭代器的使用------------------*///1.定义map容器的迭代器 mySpace::map<string, string>::iterator mit = dict.begin();//2.使用正向迭代器遍历Map（键按升序排列）while(mit != dict.end()){// mit->first += 'x'; // 错误：键（first）不可修改 mit->second +='!';// 正确：值（second）可修改 cout << mit->first <<":"<< mit->second << endl;++mit;} cout << endl;return0;}

运行结果

------------基本操作------------

一、前置++操作

1. 本质

红黑树的前置++操作对应中序遍历的下一个节点（后继节点），实现逻辑基于中序遍历的顺序规则。中序遍历顺序为：左子树 → 根节点 → 右子树

对于红黑树中的任意节点，其后继节点（即 ++操作的结果）遵循以下规则：若当前节点有右子树：后继节点是右子树的最左节点（即：右子树中的最小值）若当前节点无右子树：后继节点是第一个向上找到的父节点，且当前节点位于该父节点的左子树若找不到这样的父节点，则后继为end()（通常用哨兵节点或nullptr表示）

2. 步骤

迭代器 ++ 不需要全局视角，只需关注==当前中序遍历的 “局部下一个结点”==，分两种情况处理：

情况 1：当前结点的右子树“不为空”
说明当前结点已访问完毕，下一个要访问的是右子树的中序第一个结点（即右子树的最左结点 ），直接取右子树的最左结点即可

情况 2：当前结点的右子树“为空”
说明当前结点及所在子树已访问完毕，下一个结点需要沿着 “当前结点到根” 的祖先路径向上找若当前结点是 “父结点的左孩子”：根据中序逻辑（左 → 根 → 右 ），下一个访问的结点就是父结点。
（例：it 指向 25，25 是 30 的左孩子且 25 右子树为空 → 下一个访问 30 ）若当前结点是 “父结点的右孩子”：说明当前子树已访问完，需继续向上找祖先，直到找到一个 “当前节点作为其左子节点的祖先节点”—— 这个祖先就是下一个要访问的结点。
（例：it 指向 15，15 是 10 的右孩子且 15 右子树为空 → 10 子树已访问完 → 继续找，发现 10 是 18 的左孩子 → 下一个访问 18 ）

3. 图示

4. 解释

疑问1：为什么右子树存在时，后继是右子树的最左节点？根据中序遍历规则，访问完当前节点后，应访问其右子树而右子树中最先被访问的节点是其最左节点（最小值）

疑问2：为什么右子树不存在时，要找 “作为左子节点的祖先”？

当中序遍历访问完某个节点且其右子树为空时，意味着该节点及其子树已遍历完毕，需要回溯到最近的一个尚未完全遍历的父节点若当前节点是其父节点的右子节点，则说明父节点及其右子树已遍历完，需继续向上回溯直到找到一个 “作为左子节点” 的祖先，此时该祖先即为下一个要访问的节点

疑问3：如何处理 end()情况？当向上回溯到根节点仍未找到符合条件的祖先时，parent会变为nullptr此时将_node设为nullptr，表示迭代器已到达end()位置

二、前置–操作

1. 本质

红黑树的前置--操作对应中序遍历的前一个节点（前驱节点），其实现逻辑与前置++（后继节点）完全对称，但方向相反。中序遍历顺序为：左子树 → 根节点 → 右子树

对于红黑树中的任意节点，其前驱节点（即--操作的结果）遵循以下规则：若当前节点有左子树：前驱节点是左子树的最右节点（即：左子树中的最大值）若当前节点无左子树：前驱节点是第一个向上找到的父节点，且当前节点位于该父节点的右子树若找不到这样的父节点，则前驱为rend()（反向迭代器的末尾，通常对应树的最右节点）

2. 步骤

迭代器 -- 无需关注全局遍历情况，重点聚焦当前中序遍历的 “局部前一个结点” ，依据不同场景分两类处理：

情况 1：当前结点的左子树 “不为空”

这表明当前结点之前，还有可访问的结点，下一个要访问的是左子树的中序最后一个结点（即左子树的最右结点 ），直接定位到左子树的最右结点即可

情况 2：当前结点的左子树 “为空”

意味着当前结点及所在子树已回溯完毕，下一个结点需要沿着 “当前结点到根” 的祖先路径向上找若当前结点是 “父结点的右孩子”：按照中序逻辑（左 → 根 → 右 ），下一个要访问的结点就是父结点
（例：it 指向 50，50 是 40 的右孩子且 50 左子树为空 → 下一个访问 40）若当前结点是 “父结点的左孩子”：说明当前子树已回溯完，得继续向上找祖先，直至找到一个 “当前节点作为其右子节点的祖先节点”，这个祖先即为下一个要访问的结点。
（例：it 指向 35，35 是 40 的左孩子且 35 左子树为空 → 40 子树已回溯完 → 接着找，发现 40是 30 的右孩子 → 下一个访问 30 ）

3. 图示

4. 解释

疑问1：为什么左子树存在时，前驱是左子树的最右节点？根据中序遍历规则，访问当前节点前，应先访问其左子树而左子树中最后被访问的节点是其最右节点（最大值）

疑问2：为什么左子树不存在时，要找 “作为右子节点的祖先”？

当中序遍历访问完某个节点且其左子树为空时，意味着需要回溯到最近的一个尚未完全遍历的父节点。若当前节点是其父节点的左子节点，则说明父节点及其左子树已遍历完，需继续向上回溯直到找到一个 “作为右子节点” 的祖先，此时该祖先即为前一个要访问的节点

疑问3：如何处理 rend()情况？前置–应返回树的最右节点（即中序遍历的最后一个节点）此时需特殊处理：从根节点开始，一路向右找到最右节点情况 2：若树为空--end() 仍返回end()（即：_node为nullptr）

情况 1：当迭代器指向end()（即_node为nullptr）时

//情况1：当前节点为空 ---> 中序前一个节点是“整棵树最右边的节点（最后一个节点）”if(_node ==nullptr){/*------------准备------------*///1.定义指向整棵树最右边的节点 Node* last = _root;/*------------寻找------------*///2.使用while循环找到“整棵树最右变的节点”while(last && last->_right)//注意：这里的while循环条件要添加“last”{ last = last->_right;}/*------------赋值------------*///3.让当前节点指向整棵树的最右节点 _node = last;}

------------代码解释------------

片段一：仿函数的设计

由于红黑树（RBTree）采用泛型设计，无法直接判断模板参数 T 具体是单纯的键类型 K（如：set 的场景 ），还是键值对类型 pair<K, V>（如：map 的场景 ）这会导致一个问题：在 insert 逻辑里进行 “节点比较” 时，默认的比较规则无法满足需求因为 pair 的默认比较会同时涉及 key 和 value，但我们实际需要只比较 key

为解决这个问题，我们在 map 和 set 这两个容器层，分别实现了仿函数 MapKeyOfT 和 SetKeyOfT，并将它们传递给红黑树的 KeyOfT 模板参数

这样，红黑树内部就能通过 KeyOfT 仿函数：先从 T 类型对象中提取出 key再用这个 key 进行比较

从而实现 “仅按 key 排序 / 插入” 的逻辑。

/*--------------------------------RBTree.h--------------------------------*/// RBTree.h template<classK,classT,classKeyOfT>classRBTree{private: RBTreeNode<T>* _root =nullptr;//红黑树根节点的指针public://……};/*--------------------------------Myset.h--------------------------------*/// Myset.htemplate<classK>classset{private:/*--------------------------成员函数（私有）--------------------------*/structSetKeyOfT{const K&operator()(const K& key){return key;}};/*--------------------------成员变量--------------------------*/ RBTree<K,const K, SetKeyOfT> _t;public://……}； /*--------------------------------Mymap.h--------------------------------*/// Mymap.h template<classK,classV>classmap{private:/*--------------------------成员变量（私有）--------------------------*/structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};/*--------------------------成员变量--------------------------*/ RBTree<K, pair<const K, V>, MapKeyOfT> _t;public://……}； 

片段二：迭代器的设计

这里的 iterator 的实现思路与 list 的 iterator 框架一致：用一个类型封装 “结点指针”再通过重载运算符，让迭代器能像指针一样完成访问行为（如：*it、++it 等）

//任务4：定义红黑树迭代器的“结构体模板” ---> 支持双向遍历template<classT,classRef,classPtr>structRBTreeIterator{/*--------------------------类型别名--------------------------*///1.重命名红黑树节点的类型：RBTreeNode<T> ---> Nodetypedef RBTreeNode<T> Node;//2.重命名红黑树迭代器的类型：RBTreeIterator<T,Ref,Ptr> ---> Selftypedef RBTreeIterator<T, Ref, Ptr> Self;/*--------------------------成员变量--------------------------*///1.当前指向的节点 Node* _node;//2.红黑树的根节点 Node* _root;/*--------------------------成员函数--------------------------*///……};

1. begin()迭代器接口函数

在 map 和 set 的使用场景中，迭代器走的是中序遍历逻辑（左子树 → 根结点 → 右子树 ）

因此：begin() 返回中序遍历的第一个结点对应的 iterator（即：最左结点的迭代器 ）

2. end()迭代器接口函数

end() 表示 “遍历结束的位置”，返回nullptr指针

在红黑树迭代器中，end() 的表示需要结合中序遍历的边界条件处理，具体逻辑可通过以下场景理解：

1. 常规遍历到末尾的情况

假设迭代器 it 指向节点 50，执行 ++it 时：节点 50 是 40 的右子节点，40 是 30 的右子节点，30 是 18 的右子节点当回溯到 18 时，18 已无父节点（到达根节点），且找不到 “当前节点是父节点左子节点” 的祖先此时，将迭代器的结点指针置为 nullptr，用 nullptr 表示 end()（遍历结束位置）

2. STL 源码的 “哨兵节点” 方案

STL 源码中，红黑树额外设计了一个哨兵头结点作为 end()：哨兵节点与根节点 “互为父节点”，左指针指向树的最左结点，右指针指向树的最右结点。这种设计与我们用 nullptr 表示 end() 的思路功能等价，但实现细节不同。

3. --end() 的特殊处理

当对 end() 执行 --（即：--end() ）时：若 end() 由 nullptr 表示，需特殊处理：让迭代器直接指向树的最右结点（即：中序遍历的最后一个有效节点 ）这样可以保证反向遍历时，从 end() 回退能正确访问到最后一个元素

总结：

无论是用 nullptr 还是 STL 源码的 “哨兵节点”，核心目的都是标记遍历结束的位置。

我们实现时，通过 nullptr 即可模拟 end()，只需在 --end() 时额外处理，让迭代器指向最右结点即可。

3. 迭代器不可修改性的适配

set 和 map 迭代器的 “不可修改性” 适配：set 的 iterator：不支持修改 key因此将红黑树的第二个模板参数设为 const K即：RBTree<K, const K, SetKeyOfT> _t;map 的 iterator：不支持修改 key，但可修改 value因此将红黑树的第二个模板参数设为 pair<const K, V>即：RBTree<K, pair<const K, V>, MapKeyOfT> _t;（pair 的第一个参数 const K 保证 key 不可改 ）