【C++、数据结构】封装map和set（用红黑树实现）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

📖 前言

在这之前我们学习了红黑树的模拟实现学习了如何使用map和set同时我们也了解到map和set底层都是用红黑树来实现的本文我们就要自己动手封装一下map和set这两大容器用我们之前学的红黑树来实现一下……🙋 🙋 🙋 🙋 🙋

前情回顾手撕红黑树 👉 传送门

前情回顾map和set 👉 传送门

1. 如何复用同一棵红黑树⚡

前提疑问

在我们这所有的之前我们知道map和set这两个容器都是用红黑树来实现的那么就有了接下来的问题。

  • map和set都是用的同一棵红黑树复用的吗
  • 或者这两个容器各自使用一棵红黑树吗

答案

很显然根据STL的设计理念是不可能是两个容器各自用一棵红黑树的这不符合泛型编程的理念实际上确实是用的同一棵树只是对我们之前的红黑树做了一些改动。

我们来看一下STL官方库的原码

在这里插入图片描述
通过翻看原码我们得知

  • map和set都是在复用同一棵红黑树
  • 它们实现的都是Key_value模型

这样设计的好处两个容器都可以复用同一棵红黑树体现了泛型编程的思想。

我们设T为红黑树的结点

  • 对于set而言T就是RBTree<K, K>
  • 对于map而言T就是RBTree<K, pair<K, V>>

这时我们就有了另一个疑问两个模板参数的第一个Key不能省略掉吗？？

  • 首先答案肯定是不能的
  • 那么原因又是什么呢？

因为map的这个类中无论怎么省略都会有一个查找函数…
在这里插入图片描述
如果将Key省略的话map中查找数据就不知道数据的类型了所以必须保留Key。

综上所述

  • map和set都是用了Key_value模型
  • set中的K是KV也是K
  • map中的K是KV是pair<KV>
  • 并且模板参数中第一个K都不能省

1.1 🌀 修改后结点的定义

enum Colour
{
	RED,
	BLACK,
};

//上层维度的一个泛型
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;	//数据

	Colour _col;

	RBTreeNode(const T& data)
		: _data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

2. 模拟实现中何实现数据比较大小🌟

  • 上述提到在模拟实现中map和set我们复用同一棵红黑树的时候都是用的是Kye_value的结构
  • 但是红黑树中的数据比较又是Key值的比较而现在我们用的则是pair的比较
  • 虽然编译上是可以通过但是真的就是我们所想要的吗？

pair比较大小

在这里插入图片描述
很显然这种比较规则不是我们所想要的并且map和set想要取到用来比较的数据是不同的。

为了取到我们想要的数据我们引入了仿函数

  • 根据map和set的需求不同
  • 我们在红黑树中新引入了一个模板参数

在这里插入图片描述
通过仿函数直接从红黑树的一个结点中取出想要的数据。

因为map和set中需要比较的数据取出方式不同所以分别在map和set类中实现不同的仿函数。

map中的仿函数
在这里插入图片描述
set中的仿函数

在这里插入图片描述
使用方法
在这里插入图片描述
此时仿函数的方便之处就体现出来了。

代码演示

//红黑树的实现
//KeyOfT --> 支持取出T对象中key的仿函数
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*> const_iterator;

	//构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的

	//迭代器中序遍历要找最左结点
	iterator Begin()
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		//树的迭代器用结点的指针就可以构造
		return iterator(subLeft);
	}

	iterator End()
	{
		return iterator(nullptr);
	}

	const_iterator Begin() const
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		//树的迭代器用结点的指针就可以构造
		return const_iterator(subLeft);
	}

	const_iterator End() const
	{
		return const_iterator(nullptr);
	}

	pair<iterator, bool> Insert(const T& data)
	{
		//1、搜索树的规则插入
		//2、看是否违反平衡规则如果违反就需要处理旋转
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; //根节点是黑色
			return make_pair(iterator(_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 make_pair(iterator(cur), 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;
			assert(grandfather);

			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//情况一（叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					//祖父和叔叔变成黑色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//情况二（叔叔不存在 or 叔叔存在且为黑
				else
				{
					//单旋
					//	   g
					//	 p
					// c
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//双旋
					//    g
					//  p
					//    c
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
			//无论父亲和叔叔是左是右都是一样的
			//grandfather->_right == parent;
			else
			{
				Node* uncle = grandfather->_left;
				//情况一
				if (uncle && uncle->_col == RED)
				{
					//祖父和叔叔变成黑色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//单旋
					// g
					//   p
					//     c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//双旋
					//  g
					//    p
					//  c
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		//父亲为空就出循环将根节点设置成黑色
		_root->_col = BLACK;

		return make_pair(iterator(newnode), true);
	}
}

3. 红黑树迭代器的实现🔥

虽然map和set这种关联式容器的迭代器使用起来和序列式容器使用起来一样但是底层实现却不尽相同。

3.1 💥红黑树begin（和 end（的定义

在这里插入图片描述

  • 因为是二叉搜索树为了更有顺序所以我们采取的是中序遍历。
  • 那么中序遍历Begin（就应该是最左结点
  • 我们实现的版本中End（定义为空是（nullptr

而库中的红黑树则是设计了一个哨兵位的头结点
在这里插入图片描述
库中实现的end就和我们所实现的不同了我们实现的是简化版的。

先直接见代码

template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	Node* _node;

	typedef __RBTreeIterator<T, Ref, Ptr> Self;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

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

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

	Self& operator++()
	{
		if (_node->_right == nullptr)
		{
			//找祖先里面孩子是父亲左的那个
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}
		else
		{
			//右子树的最左结点
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}

			//左为空
			_node = subLeft;
		}
		return *this;
	}

	Self& operator--()
	{
		if (_node->_left == nullptr)
		{
			//找祖先里面孩子是父亲
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}
		else
		{
			//左子树的最右结点
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}

		return *this;
	}

	Self operator++(int)
	{
		Self tmp(*this);

		++(*this);

		return tmp;
	}

	Self operator--(int)
	{
		Self tmp(*this);
		
		--(*this);

		return tmp;
	}

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

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
};
  • T:数据
  • Ref引用
  • Ptr指针
  • Sefiterator本身

3.2 💥 operator* 和 operator->

在这里插入图片描述
就是正常的运用operator。

3.3 💥 operator++ 和 operator- -

这里迭代器的++和- - 需要分类一下分别是前置++- - 、后置++- -

前置++
因为我们是中序遍历我们访问完自己之后下一个该访问哪一个结点？

在这里插入图片描述
it走到哪说明哪个结点已经访问过了接下来我们的操作不是递归但是胜似递归。

我们大致的思路

  • 跟着中序遍历的方式it肯定是从5->6->7->8
  • 很显然这时我们只需要看当前位置右子树是否是空

分如下两种情况（重点

  1. 右子树为空找孩子是父亲的左的那个祖先节点否则继续往上走直到空（nullptr
  2. 右子树为非空找右子树的最左节点

为什么右子树为空时不能直接跳到该结点的父亲节点吗？

答案是不行的如图所示

在这里插入图片描述

如果按照问题中那样右子树为空直接跳到父亲的话5->66的右子树不为空6->7然后7的右子树为空7->6然后6的右子树不为空6->7然后7的右子树为空7->6……这样就反复横跳了……

所以我们找到一个办法那就是找孩子是祖先的左的那个祖先节点。

这样就实现了非递归这种非递归的前提是（一定是三叉链

在这里插入图片描述
前置- -

我们大致的思路

  • 很显然这时我们只需要看当前位置左子树是否是空

前置- -就是倒着走同样还是对当前位置分两种情况（重点

  1. 左子树为空找孩子是父亲的右的那个祖先节点否则继续往上走直到空（nullptr
  2. 左子树为非空找左子树的最右节点

在这里插入图片描述
只要前置++理解了那么前置- -完全就是前置++倒过来走一遍。

后置++、后置- -

和之前实现容器的得带器一样我们这里直接复用即可
在这里插入图片描述

3.4 💥 operator== 和 operator!=

直接见下图所示
在这里插入图片描述
红黑树中查找函数

iterator Find(const K& key)
{
	Node* cur = _root;
	KeyOfT kot;
	while (cur)
	{
		if (kot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (kot(cur->_data) > key)
		{
			cur - cur->_left;
		}
		else
		{
			return iterator(cur);
		}

		return End();
	}
}

4. 封装map和set⭕

有了上面的红黑树改装我们这里的对map和set的封装就显得很得心应手了。

map的封装

template<class K, class V>
class map
{
	//定义一个内部类
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)//operator() 可以像函数一样去使用
		{
			return kv.first;
		}
	};

public:
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
	typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;

	iterator begin()
	{
		return _t.Begin();
	}

	iterator end()
	{
		return _t.End();
	}

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

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));
		return ret.first->second;
	}
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

这里map中的operator[ ]我们知道其原理之后模拟实现就非常方便直接调用插入函数控制好参数和返回值即可。

对set的封装

template<class K>
class set    
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)//operator() 可以像函数一样去使用
		{
			return key;
		}
	};
public:

	//加上typename告诉编译器这是个类型类模板实例化了再去取
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

	iterator begin() const
	{
		return _t.Begin();
	}

	iterator end() const
	{
		return _t.End();
	}

	pair<iterator, bool> insert(const K& key)
	{
		//pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
		auto ret = _t.Insert(key);
		return pair<iterator, bool>(iterator(ret.first._node), ret.second);
	}

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

private:
	RBTree<K, K, SetKeyOfT> _t;
};
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：超声波测距LCD1602显示

下一篇：Git：查看提交信息

“【C++、数据结构】封装map和set（用红黑树实现）” 的相关文章

【C++11】—— 类的新功能1年前 (2023-02-02)
c++基础篇之C++ 模板1年前 (2023-02-02)
C++11 std::function 基础用法1年前 (2023-02-02)
如何在Linux上搭建C++开发环境1年前 (2023-02-02)
C++中＜bits/stdc++.h＞头文件介绍1年前 (2023-02-02)
第十一届蓝桥杯青少组C++选拔赛真题带参考1年前 (2023-02-02)
【C++】为什么C++会支持函数重载1年前 (2023-02-02)
【C++】AVL树1年前 (2023-02-02)
VScode快速配置C/C++环境1年前 (2023-02-02)
C++引用1年前 (2023-02-02)

阿里云国际版