C++【一棵红黑树封装 set 和 map-每日运维

🌇前言

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

🏙️正文

1、红黑树的完善

1.1、修改默认成员函数

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

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

1.1.1、默认构造

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

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

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

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

1234

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

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;
	}

1234567891011121314151617181920

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

1.1.3、拷贝构造 —> 深拷贝

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

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

void RBTreeTest1()
{
	RBTree rb1;
	rb1.Insert(make_pair(1, "a"));

	RBTree rb2(rb1);	//rb2 拷贝构造 rb1
}

1234567

重复释放问题

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

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

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

	//拷贝构造
	RBTree(const RBTree& 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;
	}

1234567891011121314151617181920212223242526272829

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

注意：

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

1.1.4、赋值重载

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

像拷贝构造一样，递归创建每一个节点

现代写法：直接与临时变量交换根节点

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

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

1234567

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

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

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

1.2、新增迭代器

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

1.2.1、整体设计

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

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

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

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

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

//迭代器类
template
class __RBTreeIterator
{
	typedef RBTreeNode Node;	//节点
	typedef __RBTreeIterator Self;	//迭代器
public:
	__RBTreeIterator()
		:_node(nullptr)
	{}

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

123456789101112131415161718

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

1.2.2、移动操作

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

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

遍历图示

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

正向移动 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;
}

12345678910111213141516171819202122232425262728293031323334353637383940

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

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

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

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

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

反向移动 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;
}

123456789101112131415161718192021222324252627282930313233343536373839

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

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

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

1.2.3、数据访问

数据访问有两种方式：

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

获取节点中的 _kv 地址

具体实现如下：

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

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

1234567891011

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

__RBTreeIterator

1

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

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

__RBTreeIterator

1

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

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

1.2.4、逻辑判断

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

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

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

12345678910

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

1.2.5、迭代器测试

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

//新增迭代器
typedef __RBTreeIterator iterator;
typedef __RBTreeIterator 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;
}

123456789101112131415161718192021222324252627282930313233

先来简单玩玩这个迭代器

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

	const RBTree crb(rb);

	cout _left;
	return const_reverse_iterator(cur);
}

12345678910111213141516171819202122232425262728293031323334353637383940414243

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

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

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

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

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

至此红黑树算是完善了，比较麻烦的是迭代器的实现，需要对 ++ 和 -- 进行分析，借助辅助节点 _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 值时再另想其他方法解决

库中的解决方案
注：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
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* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;

	Color _col;
};

//迭代器类
template
class __RBTreeIterator
{
	typedef RBTreeNode Node;	//节点
	typedef __RBTreeIterator Self;	//迭代器

	//……
};

//红黑树类
template
class RBTree
{
	typedef RBTreeNode Node;
public:
	//……
	
	//新增迭代器
	typedef __RBTreeIterator iterator;
	typedef __RBTreeIterator const_iterator;
	typedef __reverse_iterator reverse_iterator;	//反向迭代器
	typedef __reverse_iterator const_reverse_iterator;
	
	//……
};

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657

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

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

Set.hpp

#pragma once
#include 
#include "RBTree.hpp"

using Yohifo::RBTree;

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

12345678910111213141516

Map.hpp

#pragma once
#include 
#include "RBTree.hpp"

using Yohifo::RBTree;

namespace Yohifo
{
	template
	class map
	{
		typedef RBTree Tree;
	private:
		Tree _t;	//这也是一棵红黑树
	};
}

12345678910111213141516

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

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

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

	return false;
}

123456789101112131415161718

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

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

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

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

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

set 中的 key 值就是 key，而 map 中的 key 值是 pair 中的 first

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

//红黑树类
template
class RBTree
{
	//……	
};

123456

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

Set.hpp

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

	typedef RBTree Tree;
private:
	Tree _t;	//这是一棵红黑树树
};

12345678910111213141516

Map.hpp

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

	typedef RBTree Tree;
private:
	Tree _t;	//这也是一棵红黑树
};

12345678910111213141516

这一波依然是 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) _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) _right;
		}
		else if (kot(cur->_data) > kot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			//插入失败
			return false;
		}
	}

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

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

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667

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

Set.hpp

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

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

12345678910

Map.hpp

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

	bool Insert(const std::pair& kv)
	{
		return _t.Insert(kv);
	}

12345678910

测试自己封装的 set 和 map

void SetAndMapTest1()

{

	set s;

	map 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

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

1、红黑树的完善

1.1、修改默认成员函数

1.1.1、默认构造

1.1.2、析构 —> 遍历释放

1.1.3、拷贝构造 —> 深拷贝

1.1.4、赋值重载

1.2、新增迭代器

1.2.1、整体设计

1.2.2、移动操作

1.2.3、数据访问

1.2.4、逻辑判断

1.2.5、迭代器测试

2、封装实现

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

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

相关文章

发布评论取消回复

共饮一杯

Oracle回收DBA权限注意事项

MongoDB 入门教学贴从术语到操作（约束怎么建立内部培训贴）

RisingWave 1.10 发布！新增用户自定义聚合函数

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

1、红黑树的完善

1.1、修改默认成员函数

1.1.1、默认构造

1.1.2、析构 —> 遍历释放

1.1.3、拷贝构造 —> 深拷贝

1.1.4、赋值重载

1.2、新增迭代器

1.2.1、整体设计

1.2.2、移动操作

1.2.3、数据访问

1.2.4、逻辑判断

1.2.5、迭代器测试

2、封装实现

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

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

相关文章

发布评论 取消回复

共饮一杯

Oracle回收DBA权限注意事项

MongoDB 入门教学贴 从术语到操作 （约束怎么建立 内部培训贴）

RisingWave 1.10 发布！新增用户自定义聚合函数

发布评论取消回复

MongoDB 入门教学贴从术语到操作（约束怎么建立内部培训贴）