C++【一棵红黑树封装 set 和 map】-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++【一棵红黑树封装 set 和 map】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✨个人主页： 北海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2019 版本 16.11.17

C++【一棵红黑树封装 set 和 map】

🌇前言

红黑树的基本情况我们已经在上一篇文章中学习过了，本文主要研究的是红黑树的实际应用：封装实现 set 和 map，看看如何通过一棵红黑树满足两个不同的数据结构；在正式封装之前，先要对之前的红黑树进行完善，增加必要功能

C++【一棵红黑树封装 set 和 map】

🏙️正文

1、红黑树的完善

1.1、修改默认成员函数

红黑树 中的每个节点都可能开辟独立的内存空间，因此在涉及拷贝、赋值等操作时，默认生成的成员函数已经无法满足需求了 --> 会导致两个指针指向同一块空间，然后造成重复析构问题

所以我们需要对其中的 默认成员函数 进行改造，手动添加符合要求的 默认成员函数

C++【一棵红黑树封装 set 和 map】

1.1.1、默认构造

写出默认构造函数是为了后面的 拷贝构造 做准备，因为祖师爷规定：只要我们写了构造函数（比如拷贝构造），就需要提供一个不需要传递参数的默认构造函数，否则编译会报错

假设只写了 拷贝构造 函数，编译时会报错：

C++【一棵红黑树封装 set 和 map】

所以需要提供一个 默认构造函数

//因为写了拷贝构造，所以需要有默认构造
RBTree()
	:_root(nullptr)
{}

注意：默认构造函数的要求是：不需要传递参数的构造函数，所以全缺省的拷贝构造函数也行，但最好还是额外提供一个无参版本

1.1.2、析构 —> 遍历释放

红黑树 中的节点可能涉及 动态内存申请，而编译器生成的 析构函数 无法满足 红黑树 的需求：释放其中的每个节点，所以我们需要编写 析构函数，释放其中的每个节点，确保不会出现 内存泄漏 问题

释放思路： 借助后序遍历 -> 左右根的思想，遍历到每一个不为空的节点，然后释放即可

因为需要 递归释放，所以推荐将释放流程封装为单独的函数，方便进行递归，析构函数 直接调用即可

	//析构
	~RBTree()
	{
		_destroy(_root);
	}
	
protected:
	void _destroy(Node*& root)
	{
		if (root == nullptr)
			return;

		//后序遍历
		_destroy(root->_left);
		_destroy(root->_right);

		//销毁节点
		free(root);
		root = nullptr;
	}

细节：_destroy 中参数使用引用，可以在不同栈帧中置空同一个指针变量

1.1.3、拷贝构造 —> 深拷贝

编译器生成的 拷贝构造 是 浅拷贝，当 红黑树 中的节点涉及动态内存申请时，程序运行必然会崩溃（多个指针指向同一块空间，导致重复析构）

比如下图中的场景，就是使用了 编译器生成的拷贝构造函数（浅拷贝）

void RBTreeTest1()
{
	RBTree<int, string> rb1;
	rb1.Insert(make_pair(1, "a"));

	RBTree<int, string> rb2(rb1);	//rb2 拷贝构造 rb1
}

C++【一棵红黑树封装 set 和 map】

此时就需要手动实现 拷贝构造（深拷贝） 了

深拷贝思路：照着被拷贝红黑树，逐个节点申请空间，并进行链接即可

类似于 根据中序、后序重构二叉树的思想

	//拷贝构造
	RBTree(const RBTree<K, V>& tree)
		:_root(nullptr)
	{
		//深拷贝 ---> 遍历构造每个节点
		_root = _copy(tree._root);
	}

protected:
	Node* _copy(const Node* root)
	{
		if (root == nullptr)
			return nullptr;

		//构造新节点
		Node* new_node = new Node(root);

		//递归链接左右子树
		new_node->_left = _copy(root->_left);
		new_node->_right = _copy(root->_right);

		//注意父亲链的链接
		if (new_node->_left != nullptr)
			new_node->_left->_parent = new_node;
		if (new_node->_right != nullptr)
			new_node->_right->_parent = new_node;

		return new_node;
	}

借助 后序遍历 的思想重构好每个节点后，返给父亲进行链接，当整棵树都重构完成后，返回 根节点

注意：

拷贝构造函数中的参数需要使用引用，避免无穷递归问题
因为是三叉链结构，需要注意父指针的链接，判断不为空后直接链接即可

1.1.4、赋值重载

编译器生成的 赋值重载 函数也是 浅拷贝，实现 赋值重载 就比较简单了，有以下两种办法：

像拷贝构造一样，递归创建每一个节点
现代写法：直接与临时变量交换根节点

现代写法很简单，也更安全（只要拷贝构造没问题，那么现代写法也没问题），下面就是现代写法：

//赋值重载
RBTree<K, V>& operator=(RBTree<K, V> tmp)
{
	//直接交换根节点即可
	std::swap(_root, tmp._root);
	return *this;
}

tmp 是 临时变量，传递参数时，会自动进行一次拷贝构造函数的调用，生成临时对象，并且此时是深拷贝

临时变量 的资源不利用就浪费了，所以可以直接把它的 根节点 偷过来，间接完成了 红黑树 的赋值，原 红黑树 中的节点在函数运行后、临时变量 销毁时进行逐一释放（自动调用 析构函数）

注意：现代写法中的参数不能使用引用，否则会导致被赋值的红黑树节点丢失

1.2、新增迭代器

红黑树 中也有 迭代器，因为是链式结构，所以在进行 迭代器 设计时，需要单独设计一个 迭代器类，就像 list 一样

C++【一棵红黑树封装 set 和 map】

1.2.1、整体设计

将 红黑树 的节点再一次封装，构建一个单独的 迭代器 类

因为此时节点的模板参数有 K 和 V，所以 迭代器类 中也需要这两个参数

至于 迭代器类 设计时的精髓：不同类型的迭代器传递不同的参数 这里就不再展开叙述，简单来说，额外增加 Ref 和 Ptr 的目的是为了让 普通迭代器 和 const 迭代器 能使用同一个 迭代器类

迭代器类中的多参数默认设计思想详见《C++ STL学习之【list的模拟实现】》

迭代器类 的大体框架如下：

//迭代器类
template<class K, class V, class Ref, class Ptr>
class __RBTreeIterator
{
	typedef RBTreeNode<K, V> Node;	//节点
	typedef __RBTreeIterator<K, V, Ref, Ptr> Self;	//迭代器
public:
	__RBTreeIterator()
		:_node(nullptr)
	{}

	//将节点构造为迭代器对象
	__RBTreeIterator(Node* root)
		:_node(root)
	{}
private:
	Node* _node;
};

其中的 Ref、Ptr 具体是什么类型，取决于调用方传递了什么

1.2.2、移动操作

迭代器 最重要的操作莫过于移动，红黑树 的迭代器是一个 双向迭代器，只支持 ++ 和 -- 操作

树形结构的容器在进行遍历时，默认按 中序遍历 的顺序进行迭代器移动，因为这样遍历 二叉搜索树 后，结果为有序

C++【一棵红黑树封装 set 和 map】

清楚遍历路径后，就可以设计具体操作了

正向移动 operator++() 与 operator++(int)

正向移动思路：

判断当前节点的右子树是否存在，如果存在，则移动至右子树中的最左节点
如果不存在，则移动至当前路径中孩子节点为左孩子的父亲节点
如果父亲为空，则下一个节点就是空

//前置++
Self operator++()
{
	//左根右
	//思路：如果右子树存在，访问右子树的最左节点；如果右子树不存在，访问父亲
	//注意：避免 _node 为空
	if (_node != nullptr && _node->_right != nullptr)
	{
		//访问右子树的最左节点
		Node* cur = _node->_right;
		while (cur->_left != nullptr)
			cur = cur->_left;

		_node = cur;
	}
	else if(_node != nullptr)
	{
		//访问父亲节点（cur 须位于父亲的左边）
		Node*  cur = _node;
		Node* parent = _node->_parent;
		while (parent && parent->_left != cur)
		{
			cur = parent;
			parent = cur->_parent;
		}

		_node = parent;
	}

	return *this;
}


//后置++
Self operator++(int)
{
	Self tmp = *this;
	++(*this);
	return tmp;
}

为什么右子树不为空时，要访问 右子树的最左节点？

因为此时是正向移动，路径为 左根右，如果右边路径存在，就要从它的最左节点开始访问

C++【一棵红黑树封装 set 和 map】

为什么右子树为空时，要访问当前路径中 孩子节点为左孩子的父亲节点？

因为孩子节点为右孩子的父亲节点已经被访问过了

C++【一棵红黑树封装 set 和 map】

在这两种情况的组合之下，就可以完成 迭代器的正向移动

反向移动 operator--() 与 operator--(int)

反向移动很简单，就是与正向相反即可

反向移动思路：

判断当前节点的左子树是否存在，如果存在，则移动至左子树中的最右节点
如果不存在，则移动至当前路径中孩子节点为右孩子的父亲节点
如果父亲为空，则下一个节点就是空

//前置--
Self operator--()
{
	//右根左
	//思路：如果左子树存在，访问左子树的最右节点；如果左子树不存在，访问父亲
	//注意：避免 _node 为空
	if (_node != nullptr && _node->_left != nullptr)
	{
		//访问左子树的最右节点
		Node* cur = _node->_left;
		while (cur->_right != nullptr)
			cur = cur->_right;

		_node = cur;
	}
	else if(_node != nullptr)
	{
		//访问父亲节点（cur 必须置于父亲的右边）
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && parent->_right != cur)
		{
			cur = parent;
			parent = cur->_parent;
		}

		_node = parent;
	}

	return *this;
}

//后置--
Self operator--(int)
{
	Self tmp = *this;
	--(*this);
	return tmp;
}

至于为何要这两种不同的情况进行移动，上面的 正向移动 已经解释过了

以上就是红黑树中迭代器移动操作的相关实现

注意：在访问父亲节点前，需要先判断父亲是否为 nullptr，避免野指针

1.2.3、数据访问

数据访问 有两种方式：

直接解引用获取节点中的 _kv
获取节点中的 _kv 地址

具体实现如下：

//解引用
Ref operator*()
{
	return _node->_kv;
}

//成员访问
Ptr operator->()
{
	return &(operator*());	//复用
}

普通迭代器 创建对象时，传递的参数如下：

__RBTreeIterator<K, V, std::pair<K, V>&, std::pair<K, V>*>

此时的 Ref、Ptr 就是普通的类型，允许发生修改行为

而 const 迭代器 创建对象时，传递的参数如下：

__RBTreeIterator<K, V, const std::pair<K, V>&, const std::pair<K, V>*>

Ref、Ptr 是 const 对象，即不允许发生修改行为

C++【一棵红黑树封装 set 和 map】

这样一来，就能只通过一个 迭代器类，满足两个性质不同的 迭代器，这就是 泛型编程 思想的魅力

1.2.4、逻辑判断

在进行 迭代器 的 逻辑判断 时，可以直接两个 红黑树 节点是否为同一个

//判断相等
bool operator==(const Self& it) const
{
	return _node == it._node;
}

bool operator!=(const Self& it) const
{
	return !((*this) == it);	//复用
}

注意：是迭代器和迭代器比较，所以参数是 Self 即迭代器对象

1.2.5、迭代器测试

有了这些模块后，我们的 红黑树 类中就可以引入 迭代器 的相关操作了

//新增迭代器
typedef __RBTreeIterator<K, V, std::pair<K, V>&, std::pair<K, V>*> iterator;
typedef __RBTreeIterator<K, V, const std::pair<K, V>&, const std::pair<K, V>*> const_iterator;

iterator begin()
{
	//起始位置是最左节点
	Node* cur = _root;
	while (cur && cur->_left != nullptr)
		cur = cur->_left;

	return iterator(cur);
}

iterator end()
{
	return nullptr;
}

const_iterator begin() const
{
	//起始位置是最左节点
	Node* cur = _root;
	while (cur && cur->_left != nullptr)
		cur = cur->_left;

	return const_iterator(cur);
}

const_iterator end() const
{
	return nullptr;
}

先来简单玩玩这个 迭代器

void RBTreeTest2()
{
	vector<pair<int, string>> vp{ make_pair(1,"a"),make_pair(2,"b"),make_pair(3,"c"),make_pair(4,"d"),make_pair(5,"e") };
	RBTree<int, string> rb;
	for (auto& e : vp)
		rb.Insert(e);

	const RBTree<int, string> crb(rb);

	cout << "普通对象: " << endl;
	RBTree<int, string>::iterator it = rb.begin();
	while (it != rb.end())
	{
		//两种访问方式都行，但推荐第二种，更方便
		cout << (*it).first << " | " << it->second << endl;
		++it;
	}

	cout << "const 对象: " << endl;
	RBTree<int, string>::const_iterator cit = crb.begin();
	while (cit != crb.end())
	{
		cout << cit->first << " | " << (*cit).second << endl;
		cit++;	//后置++ 也可以用
	}
}

C++【一棵红黑树封装 set 和 map】

此时基于迭代器的范围 for 也可以正常使用

C++【一棵红黑树封装 set 和 map】

注意：const 迭代器是为 const 对象提供的，所以可以选择重载 begin() 与 end()，也可以选择重新编写 cbegin() 和 cend()，二者除了函数名外，其他都是一样的

1.3、反向迭代器的设计

红黑树 的反向迭代器比较难搞，因为 反向迭代器类 中为了追求极致对称，rbegin() 是最后一个节点的下一个节点，即 红黑树中最右节点的下一个节点

由于 三叉链 结构的特殊性，我们实现的 红黑树 中没有指向 最右节点 的节点，既然没有，那就创造一个，这正是 SGI 版 STL 中 红黑树 的实现方法，它的根节点 _root 的父亲不是空，而是搞了一个 header 节点，让根节点指向它，它的左右指针分别指向 最左节点、最右节点

C++【一棵红黑树封装 set 和 map】

新增了这个节点后，之前的逻辑都要发生改变，比如 end() 不再是空，而是 header；涉及最左/最右节点的插入后，都要更新 header 的指向，这种方法在进行迭代器操作时比较友好，其他场景下就比较麻烦了，需要额外维护一个节点

如果按库中的 红黑树定义，rbegin() 就是 header 这个节点，因为它指向 最右节点

为了避免破坏前面的操作，我们可以额外新增一个成员：header 指向最右节点，在调用 rbegin() 时对其进行更新并返回即可，属于一个比较中庸的解决方案，默认构造、拷贝构造、赋值、析构记得对这个节点进行处理

C++【一棵红黑树封装 set 和 map】

额外新增一个节点，不会影响其他节点，也不会影响前面的逻辑

private:
	Node* _root = nullptr;
	Node* _header = nullptr;	//指向最右节点

涉及构造、初始化等操作时，需要带上 _header

反向迭代器的设计如下：

#include "reverse_iterator.hpp"

typedef __reverse_iterator<iterator, std::pair<K, V>&, std::pair<K, V>*> reverse_iterator;	//反向迭代器
typedef __reverse_iterator<const_iterator, const std::pair<K, V>&, const std::pair<K, V>*> const_reverse_iterator;

//反向迭代器
reverse_iterator rbegin()
{
	//返回指向最右节点的节点
	Node* cur = _root;
	while (cur && cur->_right != nullptr)
		cur = cur->_right;
	_header->_left = cur;
	return reverse_iterator(_header);
}

reverse_iterator rend()
{
	//返回最后一个节点的上一个节点，即最左节点
	Node* cur = _root;
	while (cur && cur->_left != nullptr)
		cur = cur->_left;
	return reverse_iterator(cur);
}

const_reverse_iterator rbegin() const
{
	//返回指向最右节点的节点
	Node* cur = _root;
	while (cur && cur->_right != nullptr)
		cur = cur->_right;
	_header->_left = cur;
	return const_reverse_iterator(_header);
}

const_reverse_iterator rend() const
{
	//返回最后一个节点的上一个节点，即最左节点
	Node* cur = _root;
	while (cur && cur->_left != nullptr)
		cur = cur->_left;
	return const_reverse_iterator(cur);
}

为什么一定要搞一个 辅助节点指向最右节点？

因为反向迭代器类比较奇怪 rbegin() 表示的是最后一个节点的下一个节点，所以为了与之适配，只能新增一个辅助节点

关于反向迭代器类的实现详见《C++ STL学习之【反向迭代器】》

其实库中解决方案是最优的，但这种方案会影响到前面的很多代码逻辑，于是我们选择了较为折中的方案

可以简单测试一下反向迭代器：

C++【一棵红黑树封装 set 和 map】

至此 红黑树 算是完善了，比较麻烦的是 迭代器 的实现，需要对 ++ 和 -- 进行分析，借助辅助节点 _header，最后也是成功利用 反向迭代器适配器 适配出了 红黑树的反向迭代器

注意：是 _header 的 _left 链接最右节点，因为反向迭代器中的 ++ 相当于 --，下一个节点是左子树的最右节点，就是整个红黑树中的最右节点

2、封装实现

下面可以正式步入本文的主题：用一棵红黑树封装实现 set 和 map

红黑树的封装实现会涉及部分代码改动
为了进行区分，红黑树的完善代码名为 RBTree - 副本.hpp 存放在 Gitee 仓库中

2.1、解决 k 与 k/v 的参数冲突

在同时封装 set 和 map 时，面临第一个问题：两者参数不匹配

set 只需要 key
map 则需要 key 和 value

这就意味着一棵 红黑树 无法满足不同需求，难道真无法满足吗？

答案当然是 可以的

参考库中的解决方案：管你是 k 还是 k/v，我都看作 value_type，获取 key 值时再另想其他方法解决

C++【一棵红黑树封装 set 和 map】
注：re_tree 的参数3是获取 key 的方式（后续介绍），参数4是比较方式，参数5是空间配置器

能否省略 参数1 key_type ？

对于 set 来说，可以，因为冗余了
但对于 map 来说，不行，因为 map 中的函数参数类型为 key_type，省略后就无法确定参数类型了，比如 Find、Erase 中都需要 key_type 这个类型

这一波是 set 为 map 做出了牺牲，迁就了 map

红黑树 改造第一步：接口调整

注：库中的 value_type 太长了，这里改为 T，既能表示 k，也能表示 k/v；原红黑树节点中的 _kv 改成了 _data

红黑树 从之前的 K V 变成了现在的 K T，这样一来，凡是之前涉及 K V 的地方都要改，比如：节点类和迭代器

//红黑树的节点类
template<class T>
struct RBTreeNode
{
	RBTreeNode(T data = T())
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)	//默认新节点为红色，有几率被调整
	{}

	//拷贝构造
	RBTreeNode(const T*& node)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(node->_data)
		, _col(node->_col)	//默认新节点为红色，有几率被调整
	{
		//拷贝节点中的信息
	}

	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;

	Color _col;
};

//迭代器类
template<class T, class Ref, class Ptr>
class __RBTreeIterator
{
	typedef RBTreeNode<T> Node;	//节点
	typedef __RBTreeIterator<T, Ref, Ptr> Self;	//迭代器

	//……
};

//红黑树类
template<class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//……
	
	//新增迭代器
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
	typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;	//反向迭代器
	typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
	
	//……
};

除此之外仍有许多需要修改的地方，这里就不一一展示

红黑树 的接口经过这样一改之后，set 和 map 就可以传递各自的参数了

Set.hpp

#pragma once
#include <iostream>
#include "RBTree.hpp"

using Yohifo::RBTree;

namespace Yohifo
{
	template<class K>
	class set
	{
		typedef RBTree<K, K> Tree;
	private:
		Tree _t;	//这是一棵红黑树树
	};
}

Map.hpp

#pragma once
#include <iostream>
#include "RBTree.hpp"

using Yohifo::RBTree;

namespace Yohifo
{
	template<class K, class V>
	class map
	{
		typedef RBTree<K, std::pair<const K, V>> Tree;
	private:
		Tree _t;	//这也是一棵红黑树
	};
}

注意：map 中 pair 的第一个参数 K 需要使用 const 修饰，因为这是不可被修改的

接下来就很简单了，直接使用 红黑树 中的接口即可（此处给 红黑树 新增了一个 Find 函数，代码如下）

bool Find(const K& key) const
{
	if (_root == nullptr)
		return false;

	Node* cur = _root;
	while (cur)
	{
		if (cur->_data.first < key)
			cur = cur->_right;
		else if (cur->_data.second > key)
			cur = cur->_left;
		else
			return true;
	}

	return false;
}

可以看到，Find() 的参数类型为 K

此时面临着一个尴尬的问题：当 T 为 key 时，_data 不是 pair，自然没有 first 和 second，程序也就无法跑起来

Insert() 也是如此，凡是涉及获取 key 的地方都有这个问题，因为此时的 _data 是不确定的，对于这种不确定的类型，一般使用 仿函数 解决

2.2、解决不同类型的 key 获取问题

现在可以看看库中 rb_tree 的参数3了，它是一个 函数对象，可以传递 仿函数，主要是用来从不同的 T 中获取 key 值

C++【一棵红黑树封装 set 和 map】

set 中的 key 值就是 key，而 map 中的 key 值是 pair<K, V> 中的 first

所以 红黑树 的接口继续改进，新增 KeyOfT 这个模板参数
注：此时只需要在红黑树类中新增

//红黑树类
template<class K, class T, class KeyOfT>
class RBTree
{
	//……	
};

分别针对这两种不同的情况设计仿函数：

Set.hpp

template<class K>
class set
{
	//仿函数：获取 key 值
	struct SetKeyOfT
	{
		const K& operator()(const K& key) const
		{
			return key;
		}
	};

	typedef RBTree<K, K, SetKeyOfT> Tree;
private:
	Tree _t;	//这是一棵红黑树树
};

Map.hpp

template<class K, class V>
class map
{
	//仿函数：获取 key 值
	struct MapKeyOfT
	{
		const K& operator()(const std::pair<K, V>& kv) const
		{
			return kv.first;
		}
	};

	typedef RBTree<K, std::pair<K, V>, MapKeyOfT> Tree;
private:
	Tree _t;	//这也是一棵红黑树
};

这一波依然是 set 为了 map 做出了牺牲~

至于 rb_tree 中参数3，也是一个仿函数，主要是用来规定 pair 中的比较方式的

当我们得到不同的 key 值获取方式后，就可以更改红黑树中相应的代码了

比如：查找、插入

bool Find(const K& key) const
{
	KeyOfT kot;	//创建一个对象，用来获取 key 值

	if (_root == nullptr)
		return false;

	Node* cur = _root;
	while (cur)
	{
		//operator()(data) 运算符重载，根据不同的对象，使用不同的获取方式
		if (kot(cur->_data) < key)
			cur = cur->_right;
		else if (kot(cur->_data) > key)
			cur = cur->_left;
		else
			return true;
	}

	return false;
}


bool Insert(const T& data)
{
	KeyOfT kot;

	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;	//根节点一定是黑色
		return true;
	}

	//寻找合适位置
	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 false;
		}
	}

	//插入节点
	cur = new Node(data);
	if (kot(parent->_data) < kot(data))
		parent->_right = cur;
	else
		parent->_left = cur;
	cur->_parent = parent;

	//判断是否需要 染色、旋转
	//……
}

现在代码可以跑起来了，先简单填充一下 set 和 map 中的基本操作

Set.hpp

public:
	bool Find(const K& key)
	{
		return _t.Find(key);
	}

	bool Insert(const K& key)
	{
		return _t.Insert(key);
	}

Map.hpp

public:
	bool Find(const K& key)
	{
		return _t.Find(key);
	}

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

测试自己封装的 set 和 map

void SetAndMapTest1()
{
	set<int> s;
	map<int, int> m;

	s.Insert(1);
	s.Insert(2);
	s.Insert(3);
	s.Insert(4);
	s.Insert(5);

	m.Insert(make_pair(1, 1));
	m.Insert(make_pair(2, 2));
	m.Insert(make_pair(3, 3));
	m.Insert(make_pair(4, 4));
	m.Insert(make_pair(5, 5));

	for (int i = 3; i < 8; i++)
	{
		cout << "set Find " << i << " -> " << s.Find(i) << endl;
		cout << "map Find " << i << " -> " << m.Find(i) << endl;
		cout << "=====================================" << endl;
	}
}

C++【一棵红黑树封装 set 和 map】

查找和插入没有问题（其实只要底层结构足够稳定，像这种表面封装是不太容易出问题的）

继续完善

set 新增迭代器、判空、求大小、计数
map 也是一样，新增 set 中新增的功能

注：关于默认成员函数，编译器生成的足够用了，因为此时的 _t 是一个自定义类型，涉及拷贝、赋值等问题时，会去调用红黑树中相应的函数，所以我们不需要实现

还是那句话：底层的数据结构足够强大，封装的时候就不需要操太多心

对于 set 和 map 都需要的函数，可以在 红黑树 中统一实现，两者分别调用即可

RBTree.hpp

bool Empty() const
{
	return _root == nullptr;
}

size_t Size() const
{
	//将底层容器遍历一遍即可
	size_t cnt = 0;
	for (auto& e : *this)
		cnt++;
	return cnt;
}

size_t Count(const K& key) const
{
	KeyOfT kot;
	//统计 key 的数量
	size_t cnt = 0;
	for (auto& e : *this)
	{
		//此时的 e 就是 key
		if (kot(e) == key)
			cnt++;
	}
	return cnt;
}

Set.hpp

注：typename 的作用是告诉编译器这是一个类型

//迭代器
typedef typename Tree::iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_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(); }

reverse_iterator rbegin() { return _t.rbegin(); }
reverse_iterator rend() { return _t.rend(); }

const_reverse_iterator rbegin() const { return _t.rbegin(); }
const_reverse_iterator rend() const { return _t.rend(); }

bool Empty() const
{
	return _t.Empty();
}

size_t Size() const
{
	return _t.Size();
}

size_t Count(const K& key) const
{
	return _t.Count(key);
}

Map.hpp

//迭代器
typedef typename Tree::iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_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(); }

reverse_iterator rbegin() { return _t.rbegin(); }
reverse_iterator rend() { return _t.rend(); }

const_reverse_iterator rbegin() const { return _t.rbegin(); }
const_reverse_iterator rend() const { return _t.rend(); }

bool Empty() const
{
	return _t.Empty();
}

size_t Size() const
{
	return _t.Size();
}

size_t Count(const K& key) const
{
	return _t.Count(key);
}

可以简单测试一波

C++【一棵红黑树封装 set 和 map】

注意：在红黑树中，凡是涉及 key 获取的地方，都要通过 KeyOfT 的方式进行获取，因为 _data 的类型不确定

2.3、解决 set 迭代器的非法操作

此时的代码仍然存在问题：set 中只有 key，key 是不能修改的，但此时 set 中的 key 可以被修改！

void SetAndMapTest3()
{
	vector<int> arr = { 8,6,3,2,1 };
	set<int> s;
	for (auto e : arr)
		s.Insert(e);

	cout << "修改前: ";
	for (auto& e : s)
	{
		cout << e << " ";
		e = 1;
	}
	cout << endl;

	cout << "修改后: ";
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}

C++【一棵红黑树封装 set 和 map】

此时居然能将 set 中的 key 进行修改！？ 这是非常不合理的

库中给出的解决方案：对于 set 来说，无论是否为 const 迭代器，都使用红黑树中的 const 迭代器进行适配

也就是说，锁死了 set 中迭代器的修改权限，此时自然无法修改 key 值

此时迭代器类中的 Ref 和 Ptr 都是 const 版本

Set.hpp

//迭代器
typedef typename Tree::const_iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::const_reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_iterator;

修改完成，VS 启动，代码，运行

C++【一棵红黑树封装 set 和 map】

结果：出现了一个编译错误

注意：先要把修改相关的代码屏蔽，否则会导致这个错误无法出现

出现错误的原因

在 set 中，普通对象调用 begin() 或 end() 时，返回的是普通迭代器，但此时的 iterator 是 const 迭代器，这就涉及一个类型转换问题了，其中的 Ref、Ptr 类型不匹配！

解决方案：在红黑树迭代器类中新增一个特殊的构造函数

当类模板实例化为普通迭代器时，就是一个普通的拷贝构造函数
当类模板实例化为 const 迭代器时，则是一个特殊的构造函数 -> 将普通的迭代器对象 -> 构造为 const 迭代器

typedef __RBTreeIterator<T, T&, T*> iterator;	//普通迭代器

//特殊的构造函数
__RBTreeIterator(const iterator& it)
	:_node(it._node)	//构造 或 拷贝构造
{}

如何做到的？

当创建 set（普通对象）中的普通迭代器时，因为此时是普通对象，所以红黑树底层会返回一个普通迭代器，但对于 set 来说，无论是否为 const 对象，它要返回的都是 const 迭代器，于是它会把红黑树返回的普通迭代器 -> 借助特殊的构造函数 -> 构造为 const 迭代器
如果 set 是 const 对象，那么红黑树返回的就是 const 迭代器，都不用进行类型转换了

这种写法对于 map 是否有影响？

没有影响，对于 map 来说，普通对象对应的就是普通迭代器，不存在普通迭代器转为 const 迭代器这种情况

新增这个特殊的构造函数后，能正常编译，将 e = 1 这条赋值语句取消注释，再编译，可以发现出现了预料中的报错信息：不能给常量对象赋值

C++【一棵红黑树封装 set 和 map】

注意：set 中的普通对象对应的也是 const 迭代器，但底层红黑树仍然是普通对象，返回的普通迭代器无法转换为 set 中的 const 迭代器，需要通过特殊构造函数解决；不能单纯的通过 const 修饰迭代器暴力解决问题，因为这样会出现 const const 的问题

2.4、调整函数返回值

set 和 map 中部分函数的返回值比较特殊，不是单纯的 bool

比如 Find() 返回的是 迭代器，查找成功返回所在位置的迭代器，失败返回最后一个位置的迭代器

Insert 插入时，成功返回《新节点所在位置迭代器与 true》构成的 pair，失败则返回《冗余节点所在位置的迭代器与 false》构成的 pair

将 红黑树 中的对应函数进行改造

RBTree.hpp

iterator Find(const K& key) const
{
	KeyOfT kot;	//创建一个对象，用来获取 key 值

	if (_root == nullptr)
		return iterator(nullptr);

	Node* cur = _root;
	while (cur)
	{
		//operator()(data) 运算符重载，根据不同的对象，使用不同的获取方式
		if (kot(cur->_data) < key)
			cur = cur->_right;
		else if (kot(cur->_data) > key)
			cur = cur->_left;
		else
			return iterator(cur);
	}

	return iterator(nullptr);
}

std::pair<iterator, bool> Insert(const T& data)
{
	KeyOfT kot;

	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;	//根节点一定是黑色
		return std::make_pair(iterator(_root), true);
	}

	//寻找合适位置
	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 std::make_pair(iterator(cur), true);
		}
	}

	//插入节点
	//……
	
	//判断是否需要 染色、旋转
	//……

	return std::make_pair(iterator(new_node), true);
}

set 与 map 中做出相应调整即可

Set.hpp

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

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

Map.hpp

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

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

可以通过代码测试一下

C++【一棵红黑树封装 set 和 map】

清楚了 Insert 的返回值之后，就可以轻而易举的理解下图了

C++【一棵红黑树封装 set 和 map】

2.5、map 新增 operator[]

map 比 set 多一个 operator[] ，主要作用是用来 访问 value

并且 operator[] 还是一个多功能函数，兼顾 插入、修改、插入+修改、查找

具体实现如下：

Map.hpp

V& operator[](const K& key)
{
	//首先插入
	auto ret = Insert(std::make_pair(key, V()));

	//插入成功：获取新迭代器
	//插入失败：返回已存在节点迭代器
	auto it = ret.first;	//获取迭代器

	return it->second;	//返回 value
}

可以测试一下：

C++【一棵红黑树封装 set 和 map】

至此，用一颗 红黑树 完成 set 和 map 的封装就算完成了

3、性能测试

将自己封装的 set 与库中的 set 进行一波性能对比（Release 模式下）

#include <set>

void SetAndMapTest6()
{
	Yohifo::set<int> mySet;
	std::set<int> stdSet;

	srand((size_t)time(NULL));

	int mySetTime = 0;
	int stdSetTime = 0;

	clock_t begin, end;

	int sum = 0;
	int n = 5000000;
	for (int i = 0; i < n; i++)
	{
		int val = rand() % n + i;

		begin = end = 0;
		begin = clock();
		auto ret1 = mySet.Insert(val);
		end = clock();
		mySetTime += (end - begin);

		begin = end = 0;
		begin = clock();
		auto ret2 = stdSet.insert(val);
		end = clock();
		stdSetTime += (end - begin);

		if (ret1.second && ret2.second)
			sum++;	//成功插入的数据量
	}

	cout << "成功插入 " << sum << " 个数据" << endl;
	cout << "mySet 耗时: " << mySetTime << " ms" << endl;
	cout << "stdSet 耗时: " << stdSetTime << " ms" << endl;
}

C++【一棵红黑树封装 set 和 map】
成功插入 300w+ 数据，结果与库中的 set 性能差不多，证明我们这棵红黑树还是很强的

4、完整源码

关于本次完善的红黑树、封装实现 set 和 map 的相关代码在下面这个 Gitee 仓库中

《封装set和map博客》

C++【一棵红黑树封装 set 和 map】

🌆总结

以上就是本次关于 C++【一棵红黑树封装 set 和 map】的全部内容了，在本文中，我们首先将红黑树进行了完善，解决了一些深拷贝问题，新增了迭代器，同时还用反向迭代器适配器适配出了反向迭代器，当红黑树完善后，我们用同一棵红黑树同时封装实现了 set 和 map，其中涉及大量泛型编程思想，值得仔细推敲

C++【一棵红黑树封装 set 和 map】

文章来源地址https://www.toymoban.com/news/detail-500394.html
相关文章推荐
C++ 进阶知识
C++【红黑树】
C++【AVL树】
C++【set 和 map 学习及使用】
C++【二叉搜索树】
C++【多态】
C++【继承】
STL 之泛型思想
C++【模板进阶】
C++【模板初阶】