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

发布于：2025-09-11 ⋅ 阅读:(15) ⋅ 点赞:(0)

【set/map 模拟实现】目录

在这里插入图片描述

往期《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 <class Key, class Compare = less<Key>, class Alloc = alloc>
class set 
{
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 <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map 
{
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 <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree 
{
protected:
    typedef void* 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 <class Value>
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

#pragma once

//任务1：包含需要使用的头文件
#include <iostream>

#include<vector>
#include<time.h>

using namespace std;


//任务2：定义节点颜色的“枚举”
enum Colour
{
	RED,   // 红色节点
	BLACK  // 黑色节点
};

//任务3：定义红黑树的节点的“结构体模板”
template<class T>
struct RBTreeNode
{
	/*--------------------------成员变量--------------------------*/
	//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<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	/*--------------------------类型别名--------------------------*/

	//1.重命名红黑树节点的类型：RBTreeNode<T> ---> Node
	typedef RBTreeNode<T> Node;

	//2.重命名红黑树迭代器的类型：RBTreeIterator<T,Ref,Ptr> ---> Self
	typedef 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.实现：“==运算符的重载”
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
	/* 注意事项：
	*		1. 函数的形式参数：常量的迭代器
	*		2. 函数的函数体：直接判断“当前指针”和“传入的迭代器的指针”是否相等即可
	*/

	//5.实现：“!=运算符的重载”
	bool operator!=(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：当前节点的左子树“不为空”---> 中序前一个节点是“左子树的最右节点（左子树最大值）”
		else if (_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<class K, class T, class KeyOfT>
class RBTree
{
private:
	/*--------------------------成员变量--------------------------*/

	RBTreeNode<T>* _root = nullptr;  //红黑树根节点的指针

	/*--------------------------类型别名--------------------------*/

	//1.重命名红黑树节点的类型：RBTreeNode<T> ---> Node
	typedef RBTreeNode<T> Node;

	/*--------------------------成员函数（私有）--------------------------*/

	//1.实现：“获取树的高度”
	int _Height(Node* root)
	{
		/*------------处理“特殊情况 + 递归出口”------------*/
		if (root == nullptr)
		{
			return 0;
		}

		/*------------处理“正常情况”------------*/
		//1.递归计算出左子树的高度
		int leftHeight = _Height(root->_left);
		//2.递归计算出右子树的高度
		int rightHeight = _Height(root->_right);

		//3.树的高度 = 左子树/右子树中的最大高度 + 1
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}


	//2.实现：“获取节点的数量”
	int Size(Node* root)
	{
		/*------------处理“特殊情况 + 递归出口”------------*/
		if (root == nullptr)
		{
			return 0;
		}

		/*------------处理“正常情况”------------*/

		//树中节点的数量 = 左子树节点的数量 + 右子树节点的数量 + 1
		return _Size(root->_left) + _Size(root->_right) + 1;
	}
public:
	/*--------------------------类型别名--------------------------*/
	//2.重命名红黑树“普通迭代器”的类型：RBTreeIterator<T, T&, T*> --->  Iterator
	typedef RBTreeIterator<T, T&, T*> Iterator;

	//3.重命名红黑树“常量迭代器”的类型：RBTreeIterator<T, const T&, const T*> ---> ConstIterator
	typedef 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.返回最左节点的迭代器
		return Iterator(current, _root);
	}

	//2.实现：“获取树的普通终止迭代器” ---> 指向假想的尾后节点
	Iterator End()
	{
		return Iterator(nullptr, _root);
	}


	//3.实现：“获取树的常量起始迭代器”
	ConstIterator Begin()const
	{
		//1.
		Node* current = _root;
		//2.
		while (current && current->_left)
		{
			current = current->_left;
		}
		//3.
		return ConstIterator(current, _root);
	}

	//4.实现：“获取树的常量终止迭代器”
	ConstIterator End()const
	{
		return ConstIterator(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)
			else if (kot(curr->_data) > key)
			{
				curr = curr->_left;
			}
			//情况3：当前遍历到的节点的键 = 要查找的键 ---> “找到了要查找的键”
			else
			{
				return curr;
			}
		}

		//3.跳出了循环，说明没有找到的键为key的节点
		return nullptr;
	}





	//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 = new Node(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)
			else if (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 = new Node(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.实现：“右单旋操作”
	void RotateR(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.实现：“左单旋操作”
	void RotateL(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.实现：“获取树的高度”
	int Height()
	{
		return _Height(_root);
	}

	//10.实现：“获取节点的个数”
	int Size()
	{
		return _Size(_root);
	}
};

Myset.h

#pragma once

#include "RBTree.h"

namespace mySpace
{
	//任务：定义set容器的类模板
	template<class K>
	class set
	{
	private:
		/*--------------------------成员函数（私有）--------------------------*/

		//1.实现：仿函数“从元素中提起键” （注意：set中容器中元素本来就是键）
		struct SetKeyOfT
		{
			//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 ---> iterator
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

		//2.重新定义红黑树的“常量迭代器”：ConstIterator ---> const_iterartor
		typedef typename RBTree<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

#pragma once

#include "RBTree.h"

namespace mySpace
{
	//任务：定义map容器的类模板
	template<class K, class V>
	class map
	{
	private:
		/*--------------------------成员变量（私有）--------------------------*/
		//1.实现：仿函数“从元素中提取键”
		struct MapKeyOfT
		{
			//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 ---> iterator
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;

		//2.重新定义红黑树的“常量迭代器”：ConstIterator ---> const_iterartor
		typedef typename RBTree<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_WARNINGS 1

#include"Myset.h"
#include"Mymap.h"


//1.实现：“反向打印set容器中的元素的函数”（演示逆向迭代器的使用）
void Print(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;
}




int main()
{
    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;

    return 0;
}

运行结果

在这里插入图片描述

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

一、前置++操作

1. 本质

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

  • 中序遍历顺序为：左子树 → 根节点 → 右子树

对于红黑树中的任意节点，其后继节点（即 ++操作的结果）遵循以下规则：

  1. 若当前节点有右子树：后继节点是右子树的最左节点（即：右子树中的最小值）
  2. 若当前节点无右子树：
    • 后继节点是第一个向上找到的父节点，且当前节点位于该父节点的左子树
    • 若找不到这样的父节点，则后继为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. 本质

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

  • 中序遍历顺序为：左子树 → 根节点 → 右子树

对于红黑树中的任意节点，其前驱节点（即--操作的结果）遵循以下规则：

  1. 若当前节点有左子树：前驱节点是左子树的最右节点（即：左子树中的最大值）
  2. 若当前节点无左子树：
    • 前驱节点是第一个向上找到的父节点，且当前节点位于该父节点的右子树
    • 若找不到这样的父节点，则前驱为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()情况？

  • 情况 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;
}

  • 情况 2：若树为空

    • --end() 仍返回end()（即：_node为nullptr）

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

片段一：仿函数的设计

由于红黑树（RBTree）采用泛型设计，无法直接判断模板参数 T 具体是单纯的键类型 K（如：set 的场景 ），还是键值对类型 pair<K, V>（如：map 的场景 ）

  • 这会导致一个问题：在 insert 逻辑里进行 “节点比较” 时，默认的比较规则无法满足需求

  • 因为 pair 的默认比较会同时涉及 key 和 value，但我们实际需要只比较 key

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

这样，红黑树内部就能通过 KeyOfT 仿函数：

  1. 先从 T 类型对象中提取出 key

  2. 再用这个 key 进行比较

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

/*--------------------------------RBTree.h--------------------------------*/
    
// RBTree.h 
template<class K, class T, class KeyOfT>
class RBTree
{
private:
    RBTreeNode<T>* _root = nullptr;  //红黑树根节点的指针
    
public:
    //……
};


/*--------------------------------Myset.h--------------------------------*/

// Myset.h
template<class K>
class set
{
private:
	/*--------------------------成员函数（私有）--------------------------*/
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

	/*--------------------------成员变量--------------------------*/
	RBTree<K, const K, SetKeyOfT> _t;
    
public:
	//……
}；

    
/*--------------------------------Mymap.h--------------------------------*/

// Mymap.h    
template<class K, class V>
class map
{
private:
	/*--------------------------成员变量（私有）--------------------------*/
	struct MapKeyOfT
	{
		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<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	/*--------------------------类型别名--------------------------*/

	//1.重命名红黑树节点的类型：RBTreeNode<T> ---> Node
	typedef RBTreeNode<T> Node;

	//2.重命名红黑树迭代器的类型：RBTreeIterator<T,Ref,Ptr> ---> Self
	typedef 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 不可改 ）

在这里插入图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布