在这里插入图片描述

第十九章：封装红黑树实现mymap和myset

一、map/set封装的核心设计思想：红黑树的泛型复用

我们之前手动实现的红黑树是固定的KV键值对模型，而STL中：

  • set 是纯key模型，只存储键值，不存储关联值
  • map 是KV键值对模型，存储key和对应的value

最直观的实现思路是写两份红黑树代码，分别适配key模型和KV模型，但STL源码采用了更高级的泛型设计：用一颗通用泛型红黑树，同时支撑set和map的底层实现，通过模板参数控制红黑树的行为，最终由编译器实例化出对应类型的红黑树，实现极致的代码复用。

【核心结论】STL中红黑树的核心实现位于stl_tree.h头文件，set/multiset、map/multimap均是对这颗红黑树的上层封装，仅通过传递不同的模板参数，实现了key模型和KV模型的差异化适配。

二、红黑树的泛型改造：从固定KV到通用泛型设计

我们先从最基础的固定KV红黑树开始，按照课程步骤一步步完成泛型改造，每一步都明确修改原因和解决的问题。

2.1 改造前：固定KV模型的红黑树（初始版本）

这是我们最开始实现的红黑树，节点和逻辑完全写死为KV键值对，只能适配map场景，无法给set复用。

#pragma once
enum Colour
{
	RED,
	BLACK
};

// 固定KV模型的红黑树节点
template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv; // 写死存储pair键值对
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

// 固定KV模型的红黑树类
template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
    // 插入逻辑写死用kv.first比较
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first) // 直接访问kv.first，和KV模型强绑定
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
        // 后续插入、旋转、变色逻辑省略，和KV模型强绑定
        // ...
	}
private:
	Node* _root = nullptr;
};
2.2 第一步：改造红黑树节点，实现存储类型泛型化

核心问题：固定的pair<K,V>导致节点只能存储键值对，无法适配set的纯key存储需求。
解决方案：将节点的存储数据改为泛型参数T，节点存储的内容完全由T决定：

  • set实例化时，T = 键值类型K
  • map实例化时，T = 键值对pair<K,V>

改造后的节点代码：

template<class T> // 泛型参数T，决定节点存储的数据类型
struct RBTreeNode
{
	T _data; // 泛型数据，不再写死为pair
	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)
	{}
};

请添加图片描述

【补充说明】泛型的核心价值在这里体现：我们不用关心T到底是什么类型，只需要定义节点的通用结构，具体的存储类型由上层使用者实例化时决定，实现了节点结构和存储数据的解耦。

2.3 第二步：改造红黑树类的模板参数，明确三个核心参数的职责

核心问题：节点改为泛型T后，红黑树需要解决两个关键问题：

  1. 查找、删除接口必须固定接收key类型参数，不能随T变化
  2. 无论T是纯key还是pair，都必须能提取出用于比较的key

解决方案：红黑树类设计三个核心模板参数，各司其职：

// K: 键值类型，用于find/erase等接口，固定参数类型
// T: 节点存储的数据类型，set传K，map传pair<K,V>
// KeyOfT: 仿函数，从T类型的数据中提取出用于比较的key
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	// 后续实现...
};

三个模板参数的详细职责：

模板参数 核心职责 不可替代的原因
K 定义键值的类型，为find/erase等接口提供固定的参数类型 无论节点存的是纯key还是pair，查找/删除都只能用key来操作，必须单独定义key的类型
T 定义红黑树节点实际存储的数据类型 实现set和map的复用，由上层决定节点存什么
KeyOfT 仿函数，从T类型的数据中提取出key 统一纯key和pair的key提取逻辑，让红黑树不用关心T的具体类型

【易错警告】很多同学会疑惑“第二个参数T已经能决定存储类型，为什么还要第一个参数K？”。核心原因是find/erase接口必须接收key类型的参数，比如map的find只能传key，不能传整个pair，所以必须单独定义K类型。

三、核心问题解决：KeyOfT仿函数的设计与作用

3.1 泛型改造后遇到的核心矛盾

节点存储改为泛型T后，比较逻辑出现了致命问题：

  • 如果T是纯key（set场景），直接比较数据本身即可
  • 如果T是pair（map场景），我们只需要用pair的first（key）比较，但pair的默认比较运算符会同时比较first和second，完全不符合红黑树的排序规则

直接比较T会导致map的排序逻辑完全错误，我们需要一种方式，能统一从T中提取key，再用key进行比较。

3.2 解决方案：KeyOfT仿函数

仿函数的本质：重载了operator()的类，其对象可以像函数一样调用，是C++中用于封装通用逻辑的经典手段。
KeyOfT的核心作用：定义一套统一的规则，从T类型的数据中提取出用于比较的key，让红黑树的比较逻辑完全基于key，和T的具体类型解耦。

3.2.1 set对应的SetKeyOfT仿函数

set的T就是key本身，所以仿函数直接返回传入的key即可：

struct SetKeyOfT
{
    // 重载operator()，接收key，直接返回
	const K& operator()(const K& key)
	{
		return key;
	}
};
3.2.2 map对应的MapKeyOfT仿函数

map的T是pair<K,V>，所以仿函数需要提取pair的first（key）返回：

struct MapKeyOfT
{
    // 重载operator()，接收pair，返回其first（key）
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;
	}
};
3.3 红黑树中KeyOfT的使用

红黑树中所有需要比较key的位置，都必须先通过KeyOfT仿函数提取key，再进行比较。以Insert接口为例，改造后的核心逻辑：

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return {Iterator(_root, _root), true};
		}

		KeyOfT kot; // 实例化仿函数对象
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
            // 先通过仿函数提取key，再进行比较
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return {Iterator(cur, _root), false}; // key已存在，插入失败
			}
		}
		// 后续插入、旋转、变色逻辑，所有比较均通过kot提取key
        // ...
	}
private:
	Node* _root = nullptr;
};

【核心结论】通过KeyOfT仿函数，我们彻底解决了泛型带来的比较逻辑差异问题。红黑树再也不用关心T是纯key还是pair，只需要无脑调用仿函数提取key，就能完成所有排序、查找逻辑，实现了真正的通用化。

四、set和map的上层封装实现

完成红黑树的泛型改造后，set和map的上层封装就变得非常简单，本质上只是一个“壳”，负责给底层红黑树传递对应的模板参数，对外暴露符合STL规范的接口。

4.1 set的基础封装实现

set只有key类型，所以给红黑树传递的模板参数为：

  • K：键值类型
  • T：键值类型K（节点存纯key）
  • KeyOfT：SetKeyOfT仿函数
#pragma once
#include"RBTree.h"

namespace bit
{
	template<class K>
	class set
	{
		// 内部定义key提取仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
        // 后续会补充迭代器、find等接口
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
        // 底层封装泛型红黑树，传递对应模板参数
		RBTree<K, K, SetKeyOfT> _t;
	};
}
4.2 map的基础封装实现

map有key和value两个类型，给红黑树传递的模板参数为：

  • K：键值类型
  • T：pair<K,V>（节点存键值对）
  • KeyOfT：MapKeyOfT仿函数
#pragma once
#include"RBTree.h"

namespace bit
{
	template<class K, class V>
	class map
	{
		// 内部定义key提取仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
        // 后续会补充迭代器、find、operator[]等接口
		bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
        // 底层封装泛型红黑树，传递对应模板参数
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}

【补充说明】STL源码中，set和map的命名风格和我们略有差异，比如红黑树的模板参数命名为Key、Value，其中Value在set中是key，在map中是pair，这也是课程中提到的“源码命名风格混乱”的点，我们自己实现时做了规范，更易理解。

五、红黑树迭代器的设计与实现

迭代器是红黑树封装的核心难点，课程中用了大量篇幅讲解其实现逻辑。红黑树的迭代器是双向迭代器，支持++和--操作，遍历顺序为红黑树的中序遍历（左-根-右），保证遍历结果是有序的。

5.1 迭代器的设计思路

和链表迭代器的核心逻辑一致：用类封装节点的指针，通过重载运算符，控制指针的行为，让其符合迭代器的遍历规范。

  • 链表的++是直接找下一个节点，而红黑树的++需要遵循中序遍历规则
  • 链表的--是直接找上一个节点，而红黑树的--需要遵循反向中序遍历规则
  • 迭代器不负责节点的释放，节点的生命周期由红黑树管理
5.2 迭代器类的模板参数与基础结构

为了用一套代码同时实现普通迭代器和const迭代器，我们设计三个模板参数，控制解引用和箭头运算符的返回值类型：

// T: 节点存储的数据类型
// Ref: 数据的引用类型（普通迭代器传T&，const迭代器传const T&）
// Ptr: 数据的指针类型（普通迭代器传T*，const迭代器传const T*）
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self; // 迭代器自身类型，简化代码

	// 成员变量：节点指针 + 根节点指针
	Node* _node;
	Node* _root; // 用于--end()的特殊处理

	// 构造函数：用节点指针和根节点初始化迭代器
	RBTreeIterator(Node* node, Node* root)
		:_node(node)
		,_root(root)
	{}

	// 1. 解引用运算符：返回节点数据的引用
	Ref operator*()
	{
		return _node->_data;
	}

	// 2. 箭头运算符：返回节点数据的指针
	Ptr operator->()
	{
		return &_node->_data;
	}

	// 3. 相等/不等比较：仅比较节点指针是否相同
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	// 4. 前置++运算符：核心遍历逻辑
	Self& operator++();
	// 5. 前置--运算符：反向遍历逻辑
	Self& operator--();
};

【补充说明】三个模板参数的设计是STL迭代器的经典技巧，避免了写两份几乎完全一样的普通迭代器和const迭代器代码，仅通过模板参数的差异，实现了const语义的控制。

5.3 核心难点：operator++的实现

迭代器++的核心设计思想：不看全局，只看局部，永远只考虑当前节点的中序下一个节点。
中序遍历规则是左-根-右，当前节点已经被访问，下一个节点分两种情况处理：

情况1：当前节点的右子树不为空

当前节点访问完成后，下一个要访问的是右子树的中序第一个节点，也就是右子树的最左节点。

【举例】节点10的右子树不为空，右子树的最左节点是15，所以++it后，迭代器指向15。

情况2：当前节点的右子树为空

说明当前节点所在的子树已经全部访问完成，需要沿着父节点向上找，找到第一个“当前节点所在子树是其左孩子”的祖先节点，这个祖先就是下一个节点。如果一直找到根节点都没有符合条件的祖先，说明整棵树遍历完成，将节点指针置为nullptr（即end()）。

【举例】节点15的右子树为空，向上找：15是父节点10的右孩子，继续往上；10是父节点18的左孩子，符合条件，所以++it后，迭代器指向18。

// 前置++运算符实现
template<class T, class Ref, class Ptr>
Self& RBTreeIterator<T, Ref, Ptr>::operator++()
{
	if (_node->_right)
	{
		// 情况1：右子树不为空，找右子树的最左节点
		Node* minLeft = _node->_right;
		while (minLeft->_left)
		{
			minLeft = minLeft->_left;
		}
		_node = minLeft;
	}
	else
	{
		// 情况2：右子树为空，向上找符合条件的祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
        //找到第一个“当前节点所在子树是其左孩子”的祖先节点
		// 循环条件：父节点不为空，且当前节点是父节点的右孩子
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;
		}
		// 找到符合条件的parent，或parent为nullptr（遍历结束）
		_node = parent;
	}
	return *this;
}
5.4 operator–的实现

--的逻辑和++完全相反，遵循反向中序遍历规则右-根-左，同样分三种情况处理：

特殊情况：当前节点是nullptr（即end()）

--end()需要指向整棵树的中序最后一个节点，也就是整棵树的最右节点，需要通过_root遍历找到最右节点。

情况1：当前节点的左子树不为空

前一个节点是左子树的中序最后一个节点，也就是左子树的最右节点。

情况2：当前节点的左子树为空

沿着父节点向上找，找到第一个“当前节点所在子树是其右孩子”的祖先节点，这个祖先就是前一个节点。

// 前置--运算符实现
template<class T, class Ref, class Ptr>
Self& RBTreeIterator<T, Ref, Ptr>::operator--()
{
	if (_node == nullptr)
	{
		// 特殊情况：--end()，找整棵树的最右节点
		Node* maxRight = _root;
		while (maxRight && maxRight->_right)
		{
			maxRight = maxRight->_right;
		}
		_node = maxRight;
	}
	else if (_node->_left)
	{
		// 情况1：左子树不为空，找左子树的最右节点
		Node* rightMost = _node->_left;
		while (rightMost->_right)
		{
			rightMost = rightMost->_right;
		}
		_node = rightMost;
	}
	else
	{
		// 情况2：左子树为空，向上找符合条件的祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
        //找到第一个“当前节点所在子树是其右孩子”的祖先节点，这个祖先就是前一个节点。
		// 循环条件：父节点不为空，且当前节点是父节点的左孩子
		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}
5.5 红黑树中迭代器的配套接口

迭代器类实现完成后，需要在红黑树类中对外暴露迭代器类型，并实现begin()和end()接口：

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
    // 对外暴露普通迭代器和const迭代器类型
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

	// 普通版本begin()：返回中序第一个节点（最左节点）的迭代器
	Iterator Begin()
	{
		Node* minLeft = _root;
		while (minLeft && minLeft->_left)
		{
			minLeft = minLeft->_left;
		}
		return Iterator(minLeft, _root);
	}

	// 普通版本end()：返回nullptr构造的迭代器，代表遍历结束
	Iterator End()
	{
		return Iterator(nullptr, _root);
	}

	// const版本begin()：返回const迭代器
	ConstIterator Begin() const
	{
		Node* minLeft = _root;
		while (minLeft && minLeft->_left)
		{
			minLeft = minLeft->_left;
		}
		return ConstIterator(minLeft, _root);
	}

	// const版本end()：返回const迭代器
	ConstIterator End() const
	{
		return ConstIterator(nullptr, _root);
	}

	// 其他接口：Insert、Find、Rotate等...
private:
	Node* _root = nullptr;
};
5.6 与SGI STL哨兵位实现的对比

课程中提到，SGI STL的红黑树迭代器实现和我们的版本有一个核心差异：SGI用了一个header哨兵位节点，而我们用nullptr充当end()。

实现方案 优点 缺点
SGI哨兵位header 1. begin()直接取header->left，end()直接取header，无需遍历找最左节点；2. --end()直接取header->right，无需特殊处理 每次插入、删除、旋转后，都必须维护header的left、right、parent指针，代码复杂度大幅提升
我们的nullptr方案 代码实现简单，无需维护额外的哨兵位节点，逻辑更直观 --end()需要通过_root遍历找最右节点，做了特殊处理；遍历找最左/最右节点有轻微的性能损耗

【课程建议】我们的实现更适合学习和理解，核心逻辑和STL完全一致，避开了哨兵位的复杂维护，更易排查问题。

六、const迭代器的实现与适配

const迭代器的核心需求：迭代器本身可以修改（支持++/–），但绝对不能修改指向的节点数据，保证const对象的遍历安全。

6.1 const迭代器的复用实现

得益于我们迭代器类的三个模板参数设计，const迭代器无需重新写一套代码，只需要在红黑树中通过typedef定义即可：

// 普通迭代器：引用和指针都是非const
typedef RBTreeIterator<T, T&, T*> Iterator;
// const迭代器：引用和指针都是const，保证数据不可修改
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

当实例化const迭代器时：

  • operator*()返回const T&，无法修改数据
  • operator->()返回const T*，无法修改数据
  • 迭代器的_node成员没有const修饰，所以依然支持++/--操作
6.2 上层set/map的迭代器适配

需要在set和map中，把底层红黑树的迭代器对外暴露，同时实现const版本的begin()和end()。

【易错警告】取类模板的内嵌类型时，必须加typename关键字，告诉编译器这是一个类型，否则编译器无法区分这是类型还是静态成员变量，会直接报错。

set的迭代器完整适配
template<class K>
class set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	RBTree<K, const K, SetKeyOfT> _t;
public:
    // 用typename声明这是内嵌类型
	typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
	typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

	// 普通版本begin/end
	iterator begin()
	{
		return _t.Begin();
	}
	iterator end()
	{
		return _t.End();
	}

	// const版本begin/end
	const_iterator begin() const
	{
		return _t.Begin();
	}
	const_iterator end() const
	{
		return _t.End();
	}

	// 其他接口...
};
map的迭代器完整适配
template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
public:
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

	// 普通版本begin/end
	iterator begin()
	{
		return _t.Begin();
	}
	iterator end()
	{
		return _t.End();
	}

	// const版本begin/end
	const_iterator begin() const
	{
		return _t.Begin();
	}
	const_iterator end() const
	{
		return _t.End();
	}

	// 其他接口...
};

七、key不可修改的约束实现

红黑树是严格的有序搜索树，所有的插入、查找、删除逻辑都依赖key的有序性。如果修改了节点中的key，会直接破坏红黑树的有序结构，导致后续所有操作逻辑失效，所以必须从语法层面约束key不可修改。

7.1 set的key不可修改实现

set的节点中存储的就是key本身，所以只需要给底层红黑树的第二个模板参数T加上const修饰，让节点存储的是const K，迭代器解引用后也是const类型，无法修改。

// set底层红黑树封装，T改为const K
private:
	RBTree<K, const K, SetKeyOfT> _t;

【补充说明】SGI STL的实现方式是把set的普通迭代器直接typedef成红黑树的const迭代器，这种方式会带来额外的类型转换问题，我们直接给T加const的方式更简单直观，不易出错。

7.2 map的key不可修改实现

map的节点中存储的是pair<K,V>，我们只需要让pair的first（key）是const类型，second（value）保持可修改即可。所以给底层红黑树的第二个模板参数T改为pair<const K, V>。

// map底层红黑树封装，T改为pair<const K, V>
private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;

这样修改后：

  • 迭代器解引用得到的pair<const K, V>中，first是const，无法修改
  • second是普通的V类型，可以正常修改，完全符合map的使用特性

【易错警告】修改了底层红黑树的T类型后，对应的MapKeyOfT仿函数的参数也要同步改为const pair<const K, V>&，否则会出现类型不匹配的编译错误。

八、Insert接口的完善与operator[]重载实现

8.1 Insert接口返回值的完善

map的operator[]底层完全依赖insert接口，所以我们需要先把红黑树的Insert接口返回值从bool改为pair<Iterator, bool>，和STL规范保持一致。

返回值的含义：

  • first：迭代器，无论插入成功还是失败，都指向key对应的节点
  • second：bool值，插入成功（key不存在）返回true，插入失败（key已存在）返回false

Insert接口的修改要点：

  1. 新插入节点后，用临时变量newNode保存新节点的指针，避免旋转变色修改cur后，返回的迭代器指向错误
  2. 插入成功/失败时，返回对应的pair对象
// 完善后的Insert接口，返回pair<Iterator, bool>
template<class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::Iterator, bool> 
RBTree<K, T, KeyOfT>::Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return {Iterator(_root, _root), true};
	}

	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return {Iterator(cur, _root), false}; // key已存在，插入失败
		}
	}

	// 新插入红色节点，用newNode保存新节点指针
	cur = new Node(data);
	Node* newNode = cur;
	cur->_col = RED;
	// 链接父节点
	if (kot(parent->_data) < kot(data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	cur->_parent = parent;

	// 旋转变色平衡逻辑（省略，和之前一致）
	// ...

	_root->_col = BLACK;
	return { Iterator(newNode, _root), true }; // 插入成功，返回新节点迭代器
}

上层set和map的insert接口也要同步修改，返回值和底层保持一致。

8.2 map的operator[]运算符重载

operator[]是map最常用的特性，它同时支持插入、查找、修改三种功能，是map的核心语法糖。

operator[]的核心功能
  1. 插入：如果key不存在，自动插入一个pair(key, V())，其中V()是value类型的默认构造值
  2. 查找：如果key已存在，直接找到对应的节点
  3. 修改：返回key对应value的引用，可直接修改value的值
  4. 插入+修改：支持m[key] = value的写法，key不存在则插入，存在则修改
operator[]的实现原理

底层完全复用Insert接口，利用Insert返回值的特性，一行代码即可实现：

// map的operator[]重载
V& operator[](const K& key)
{
    // 1. 调用Insert，key不存在则插入默认值，存在则直接返回对应迭代器
	pair<iterator, bool> ret = _t.Insert({ key, V() });
    // 2. 取出迭代器
	iterator it = ret.first;
    // 3. 返回value的引用
	return it->second;
}
典型使用场景：统计字符串出现次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
	countMap[str]++; // 一行代码完成统计，无需手动判断key是否存在
}

【易错警告】operator[]会自动插入默认值，即使你只是想查找key是否存在。如果仅需判断key是否存在，应该用find接口，避免不必要的插入操作，影响性能。

九、课程易错点与实现建议

课程中老师反复强调了多个实现过程中的高频踩坑点，这里做完整汇总：

  1. 分步实现，拒绝一步到位

    【课程强提醒】不要一上来就把迭代器、const迭代器、operator[]所有功能一起实现，模板代码的报错信息不直观，叠加太多功能会导致报错无法排查。
    正确步骤：泛型红黑树改造 → KeyOfT仿函数 → set/map基础insert → 普通迭代器 → const迭代器 → key不可修改约束 → Insert返回值完善 → operator[]重载，跑通一步再走下一步。

  2. KeyOfT仿函数的使用遗漏
    红黑树中所有需要比较key的位置，都必须通过仿函数提取key，不能直接比较_data，否则map的pair.second会参与比较，导致排序逻辑完全错误。

  3. typename关键字的遗漏
    取类模板的内嵌类型时（比如RBTree<...>::Iterator），必须加typename关键字，否则编译器会报错，这是模板编程的高频易错点。

  4. 迭代器++/–的循环条件写反
    右为空时，++的循环条件是cur == parent->_right；左为空时，--的循环条件是cur == parent->_left，条件写反会导致死循环或遍历顺序错误。

  5. Insert接口中新节点指针的保存
    插入新节点后，旋转变色的逻辑会修改cur的指向，必须用newNode临时变量保存新插入的节点，否则返回的迭代器会指向错误的节点。

  6. key的const修饰遗漏
    必须给set的T加const K，给map的T加pair<const K, V>，否则key可以被修改，直接破坏红黑树的有序结构。

  7. end()的特殊处理
    我们用nullptr充当end()，--end()需要单独做特殊处理，找到整棵树的最右节点，否则会出现空指针解引用的崩溃。

十、完整代码实现汇总

1. RBTree.h（最终完整版本）
#pragma once
#include <iostream>
#include <utility>
using namespace std;

enum Colour
{
	RED,
	BLACK
};

// 红黑树节点结构
template<class T>
struct RBTreeNode
{
	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)
	{}
};

// 红黑树迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	Node* _root;

	RBTreeIterator(Node* node, Node* root)
		:_node(node)
		,_root(root)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* minLeft = _node->_right;
			while (minLeft->_left)
			{
				minLeft = minLeft->_left;
			}
			_node = minLeft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node == nullptr)
		{
			Node* maxRight = _root;
			while (maxRight && maxRight->_right)
			{
				maxRight = maxRight->_right;
			}
			_node = maxRight;
		}
		else if (_node->_left)
		{
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

// 泛型红黑树主类
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

	Iterator Begin()
	{
		Node* minLeft = _root;
		while (minLeft && minLeft->_left)
		{
			minLeft = minLeft->_left;
		}
		return Iterator(minLeft, _root);
	}

	Iterator End()
	{
		return Iterator(nullptr, _root);
	}

	ConstIterator Begin() const
	{
		Node* minLeft = _root;
		while (minLeft && minLeft->_left)
		{
			minLeft = minLeft->_left;
		}
		return ConstIterator(minLeft, _root);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr, _root);
	}

	// 插入接口
	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return {Iterator(_root, _root), true};
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return {Iterator(cur, _root), false};
			}
		}

		cur = new Node(data);
		Node* newNode = cur;
		cur->_col = RED;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return { Iterator(newNode, _root), true };
	}

	// 查找接口
	Iterator Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur, _root);
			}
		}
		return End();
	}

private:
	// 右旋转
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		Node* ppnode = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}

	// 左旋转
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		Node* ppnode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}

private:
	Node* _root = nullptr;
};
2. myset.h（最终完整版本）
#pragma once
#include"RBTree.h"

namespace bit
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();
		}

		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

	private:
		RBTree<K, const K, SetKeyOfT> _t;
	};
}
3. mymap.h（最终完整版本）
#pragma once
#include"RBTree.h"

namespace bit
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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();
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

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

	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}
4. Test.cpp（测试代码）
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
using namespace std;
#include"mymap.h"
#include"myset.h"

// 测试set
void test_set()
{
	bit::set<int> s;
	s.insert(4);
	s.insert(14);
	s.insert(2);
	s.insert(12);
	s.insert(222);

	// 正向遍历
	bit::set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 反向遍历
	bit::set<int>::iterator it2 = s.end();
	while (it2 != s.begin())
	{
		--it2;
		cout << *it2 << " ";
	}
	cout << endl;
}

// 测试map
void test_map()
{
	bit::map<string, string> m;
	m.insert({ "sort", "排序"});
	m.insert({ "left", "左边" });
	m.insert({ "right", "右边" });

	// operator[]插入+修改
	m["insert"] = "插入";
	m["string"] = "字符串";

	// 遍历
	for (auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	// 统计次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	bit::map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

int main()
{
	test_set();
	cout << "-------------------------" << endl;
	test_map();
	return 0;
}
# 开发语言 # c语言 # c++ # visual studio # 算法
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

DeepSeek vs Claude vs GPT-4o：我拿同一个需求让三个AI写代码，结果出乎意料

同一需求让 DeepSeek、Claude、GPT-4o 分别写代码，三轮实测下来结果出乎意料。谁写出来直接能用？谁的代码看似完美实则埋坑？

avatar AtomGit开源社区

AI Agent Harness Engineering 的“常识”问题：我们离真正的理解还有多远

AI Agent Harness（Agent管控框架）是介于大模型和上层应用之间的中间层，核心职能是将大模型的生成能力转化为可落地、可信赖的执行能力。任务解析器：将自然语言描述的用户目标拆解为可执行的子任务序列状态机：管理Agent执行过程中的全局状态、上下文信息工具编排器：负责工具的调用、参数校验、结果返回常识校验层：专门负责检测生成的动作是否违反常识记忆管理器：管理短期对话记忆、长期用户记忆、

avatar AtomGit开源社区

AI写复杂业务比你强？别慌，这才是工程师的核心竞争力

摘要： AI编程工具（如VibeCoding）的普及引发开发者对自身价值的思考。单纯依赖“AI无法处理复杂业务”的回答已无说服力，因AI能力持续进化。工程师的核心优势在于：1）定义模糊需求并拆解为可执行任务；2）判断AI输出的合理性与风险；3）结合业务上下文做出工程决策。复杂业务的难点并非代码实现，而是规则梳理、历史兼容及责任兜底。未来，工程师的角色将转向问题定义、AI协同与质量把控，而非单纯编码

avatar AtomGit开源社区