C++：用红黑树封装map与set-2

时间：2024-11-29 16:13:57

在这里插入图片描述

文章目录

  • 前言
  • 一、红黑树封装map与set中const迭代器
    • 1. 框架的搭建
    • 2. set实现const迭代器
    • 3. map实现const迭代器
  • 二、operator[ ]
    • 1. operator[ ]要达成的样子
    • 2. insert的改变
  • 三. 解决insert里set中的问题
  • 四. 解决map中的operator[ ]
  • 总结用红黑树封装map与set代码

前言

前面我们map与set封装的已经差不多了，接下来还有一些细节需要处理，本片博客主要解决const迭代器以及引发的一些其他问题~????????

总后的总结完整的源码封装的源码附上~????????

想看前面的封装是怎么实现的戳这里哦宝宝~❤️❤️

一、红黑树封装map与set中const迭代器

1. 框架的搭建

首先，和以前一样，要写出const迭代器，和以前一样通过控制三个模板参数，从而控制operator*以及operator->的返回值，从而控制普通迭代器与const迭代器。

在这里插入图片描述

改变模板参数，控制返回值：
在这里插入图片描述

2. set实现const迭代器

set的data中储存的是key，而且set是key的模型，我们说key是不可以被改变的，无论你是普通迭代器还是const迭代器，key都不可以被改变。

因此，这里set普通迭代器与set const迭代器都是RBTree::const迭代器，就达到了这样的效果：
在这里插入图片描述

tips：注意这里要加typename，模板类内的东西要在外部使用要告诉编译器哦

因此，我们在封装的时候要这样写：
在这里插入图片描述
这里的iterator是什么呢？是普通的迭代器吗？

答：不是的，这里我们typedef了，这里其实是红黑树中的const_iterator。

3. map实现const迭代器

map与set不同，对于set来说，data中存储的是key，因此直接让它的普通迭代器与const迭代器都是const迭代器。

但是！对于map来说就不一样了，map的data中存储的是
pair<key, calue>，对于pair.first是不可以修改的，对于pair.second是需要修改的，如果直接将普通迭代器与const迭代器都是const迭代器，那么pair.first与pair.second都不能修改了。

因此我们需要想出其他的方法！

这里的解决方法是，将map的pair<key, calue>变为pair<const key, calue>，从一开始就限制key是不能够修改的，因此迭代器正常走就可以了~

在这里插入图片描述

二、operator[ ]

1. operator[ ]要达成的样子

对于map来说，因为map是key-value，因此我们要存在operator[ ]，

  1. 通过[ ]进行插入
  2. 通过[ ]通过key改变value

因此我们实现operator[ ]是一定要借助insert的。
这里我们前面详细分析过，具体的分析过程戳这里哦宝

○( ＾皿＾)っHiahiahia…

2. insert的改变

通过前面的分析我们知道了，为了实现上述的目的，insert的返回值需要变成一个pair，

在这里插入图片描述

因此：
在这里插入图片描述
当然，RBTree.h中的insert改了，对应的map与set也要相应的更改：

以下是我们的测试代码：

jyf::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));

//bit::map<int, int>::iterator mit = m.begin();
auto mit = m.begin();
while (mit != m.end())
{
	// 不能修改key，可以修改value
	//mit->first = 1;
	mit->second = 2;

	cout << mit->first << ":" << mit->second << endl;
	++mit;
}
cout << endl;

//func(m);

for (const auto& kv : m)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

jyf::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);
jyf::set<int>::iterator it = s.begin();
while (it != s.end())
{
	// 不应该允许修改key
/*	if (*it % 2 == 0)
	{
		*it += 10;
	}*/

	cout << *it << " ";
	++it;
}
cout << endl;

但是，但是中的但是，就算我们改完了之后还是编译不通过：
在这里插入图片描述

我们看到这里，map好像没问题了，唯一出问题的就是set，因此我们要解决这个问题。

三. 解决insert里set中的问题

那么set为什么会出问题呢？
问题出在set中普通迭代器与const迭代器都是const迭代器！

如下图：
在这里插入图片描述

那这里怎么解决呢？

首先我们来套一层：

用pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret来接收Insert的返回值，因此在ret中，pair的iterator是普通的iterator。

然后又用ret.first 与 ret.second来构造pair返回，也就是说pair是不能直接构造的时候这里first用const迭代器来构造，因此需要套一层，最后用普通迭代器构造cosnt迭代器。

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

但是只是这样还是编译不通过，还是老问题~

这是因为我们没有提供用普通迭代器构造const迭代器的构造函数：
解决方案如下：

在这里插入图片描述
这样我们的编译就可以通过了：
在这里插入图片描述

四. 解决map中的operator[ ]

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

以下是测试代码：

jyf::map<string, string> dict;
dict.insert(make_pair("sort", "xxx"));
dict["left"]; // 插入

for (const auto& kv : dict)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

dict["left"] = "左边"; // 修改
dict["sort"] = "排序"; // 修改
dict["right"] = "右边"; // 插入+修改

for (const auto& kv : dict)
{
	cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

运行结果为：
在这里插入图片描述

总结用红黑树封装map与set代码

RBTree.h

#pragma once

#include<iostream>

using namespace std;



enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	Colour _col;
	T _data;

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

template<class T, class Ptr, class Ref>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ptr, Ref> Self;

	// 解决insert中set的问题
	typedef __TreeIterator<T, T*, T&> iterator;

	__TreeIterator(const iterator& it)
		: _node(it._node)
	{};

	Node* _node;

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

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

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

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

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

	Self& operator++ ()
	{
		if (_node->_right != nullptr)
		{
			Node* curleft = _node->_right;
			while (curleft->_left)
			{
				curleft = curleft->_left;
			}
			_node = curleft;
		}
		else
		{
			// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
			Node* cur = _node;
			Node* parent = _node->_parent;

			while (parent)
			{
				if (parent->_left == cur)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}

			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* subRight = _node->_left;
			while (subRight->_right)
			{
				subRight = subRight->_right;
			}

			_node = subRight;
		}
		else
		{
			// 孩子是父亲的右的那个节点
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}
		return *this;
	}

};

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	// 同一个类模板，传的不同的参数实例化出的不同类型
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T, const T*, const T&> const_iterator;

	iterator begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return iterator(leftMin);
	}

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

	const_iterator begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return const_iterator(leftMin);
	}

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

	Node* 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 cur;
			}
		}

		return nullptr;
	}


	pair<iterator, bool> Insert(const T& data)
	{
		// 树为空，直接插入然后返回
		if (_root == nullptr)
		{
			_root = new Node(data);
			// 根节点必须是黑色
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

		Node* cur = _root;
		Node* parent = nullptr;

		KeyOfT kot;

		while (cur)
		{
			// 小于往左走
			if (kot(data) < kot(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) > kot(cur->_data))   // 大于往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		cur = new Node(data);
		// 其他结点初始颜色为红色
		cur->_col = RED;

		// 记录cur用于改变颜色后还能找到cur来返回
		Node* newnode = cur;

		// 链接
		if (kot(cur->_data) < kot(parent->_data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		// 如果我们parent是黑色，不用处理，就结束了

		// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定
		// 用while循环是因为我们要不断的向上调整
		while (parent && parent->_col == RED)
		{
			// 首先我们要找到grandfather
			Node* grandfather = parent->_parent;

			// 接下来通过grandfather找到uncle

			//如果parent是grandfather->_left
			if (parent == grandfather->_left)
			{
				// 说明uncle在右边
				Node* uncle = grandfather->_right;

				// uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 满足上述情况，开始调整颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上调整
					cur = grandfather;
					parent = cur->_parent;

					// 但是走到这里有一个问题，如果当前parent就是根，
					// 并且parent是红色，我们要把它变为黑色，
					// 处理方式是：出循环后，暴力将_root->_col变为黑色
				}
				else    // uncle不存在 或 uncle存在且为黑色
				{
					// 判断要怎样旋转

					// 右单旋
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						RotateR(grandfather);
						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 左右双旋
					{
						//     g
						//   p
						//		c
						RotateL(parent);
						RotateR(grandfather);
						// 调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出
					break;
				}
			}
			else //(parent == grandfather->_right)  // 如果parent是grandfather->_right
			{
				// 说明uncle在左边
				Node* uncle = grandfather->_left;

				// uncle存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 满足上述情况，开始调整颜色
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else    // uncle不存在 或 uncle存在且为黑色
				{
					// 判断要怎样旋转

					// 左单旋
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						RotateL(grandfather);
						// 调整颜色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else // 右左双旋
					{
						// g
						//	  p
						// c
						RotateR(parent);
						RotateL(grandfather);
						// 调整颜色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}

		// 这里保证根为黑色
		_root->_col = BLACK;

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

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		// 重新链接
		parent->_right = curleft;
		if (curleft) // 如果curleft存在
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = cur;

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

			cur->_parent = ppnode;
		}
	}

	// 右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		parent->_left = curright;

		if (curright)
		{
			curright->_parent = parent;
		}

		cur->_right = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = cur;
		if (ppnode == nullptr)
		{
			cur->_parent = nullptr;
			_root = cur;
		}
		else
		{
			if (ppnode->

相关文章