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

在C++标准库中，set容器和map容器的底层都是红黑树，它们的各种接口都是基于红黑树来实现的，我们在这篇文章中已经模拟实现了红黑树 ->【C++】红黑树，接下来我们在此红黑树的基础上来看看如何封装set和map。

一、共用一颗红黑树

我们在这篇文章中 ->【C++】set容器和map容器的基本使用，清楚set是key搜索场景的结构，map是key/value搜索场景的结构。所以要用红黑树封装它们两个就需要2棵红黑树，这两颗红黑树整体逻辑差不多一样，只是结点中的元素数据类型不一样，一个是K类型，一个是pair<K,V>类型。两棵极为相似的树，只是一点不同，如果实现两个会显得冗余，那么我们就可以考虑使用模板来将结点中的数据类型泛型化，使set和map底层共用一个红黑树。

我在先前的文章中已经实现了红黑树，它是解决key/value搜索场景的，我将那篇文章的源代码裁剪了一些重要的部分，大家这里只需看懂这部分的功能：

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	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)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	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)
				parent = cur,cur = cur->_right;
			else if (cur->_kv.first > kv.first)
				parent = cur,cur = cur->_left;
			else
				return false;
		}

		cur = new Node(kv);
		cur->_col = RED; 
		if (parent->_kv.first < kv.first)
			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 true;
	}
private:
	Node* _root = nullptr; 
};

此时，结点中数据类型是pair，这样我们就把这个结点的数据类型写"死"了，set容器底层就不能用这个红黑树，我们要实现set和map共用一棵红黑树，所以就需要把结点的数据类型泛型化(根据传来的类型来确定具体的类型)：

template<class T>  //如果是set就传K，如果是map就传pair<K,V>
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)
	{}
};

那么，RBTree也要跟着改：

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

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

		cur = new Node(data);
		cur->_col = RED; 
		if (parent->_data.first < data.first)
			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 true;
	}
private:
	Node* _root = nullptr; 
};

封装set：

//MySet.h
#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K> _t;
	};
}

封装map：

//MyMap.h
#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
	public:
		bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<pair<K, V>> _t;
	};
}

这样我们就可以通过模板参数T来控制set和map共用一棵红黑树了！

二、 红黑树中Insert带来的问题

通过观察上面红黑中Insert中的代码，其实会有问题：

我们的data可能是K类型，也可能是pair<K,V>类型。如果是后者，那么这样比较当然没问题，那如果是前者，就不能这样比较，所以我们要对这个部分进行修改。

怎么修改呢？去掉.first吗？

我们如果去掉.first，那么不管是K还是pair<K,V>都可以进行比较，以pair<K,V>类型为例，两个pair类型进行比较时先比较K，如果K相同则比较V，这与我们的本意相违背，我们的要求是只比较K的值，不能让V的值参与比较！所以我们要解决问题，不能仅仅是去掉.first。

我们可以在set和map类中写一个仿函数，通过仿函数来获取K，具体做法如下：

#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K,KeyOfSet> _t;
	};
}

#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
		struct KeyOfMap
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<pair<K, V>,KeyOfMap> _t;
	};
}

 这时我们就需要在红黑树中加一个模板参数：

我们明确知道map是需要这个仿函数来获取K值的，但是在set中也写一个仿函数来获取K值，有人开始会觉得这是多余的，因为set中的元素类型本身就是K类型，但是不要忽略一点，set和map是共用同一份模板的，map需要这个仿函数，那么set也必须有这个仿函数，set这里的仿函数就是为了兼容map，这时，红黑树的第二个模板参数KeyOfT就出现了。

三、erase和find带的来问题

我们知道set容器和map容器都有erase和find接口，这两个接口都是根据K值来进行的，如果我们要在红黑树中实现这两个接口那么必须知道K的值，我们根据K的值来进行删除和查找。但是现在，我们自己实现的这个红黑树中并没有办法拿到K的值，也就是说在我们目前这棵红黑树中若要实现erase和find是做不到的！

为了获取K的值，我们可以在RBTree中再添加一个模板参数K，专门用来获取K的值：

在set中：

在map中：

其实，这里的set中传了两个K，第一个K就是兼容map的。因为map需要这个K，那么在TRBTree中就必须增加一个模板参数，所以set就必须传一个K。

那么在RBTree中erase和find接口就可以这样写：

bool find(const K& key)
{
	//...
}

bool erase(const K& key)
{
	//...
}

 四、迭代器

红黑树的迭代器和我们在模拟实现list时思路是一样的，因为红黑树的底层空间是不连续的，所以我们不能直接"typedef Node* iterator"，我们要单独用一个类型封装结点的指针，再通过重载运算
符实现，让迭代器具有像指针一样访问的行为：

//Ref和Ptr是为了兼容普通迭代器和const迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node; //当前结点指针
	RBTreeIterator(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)
	{
		return _node != s._node;
	}
};

因为set和map都是双向迭代器，所以它们的迭代器应该要支持++和--操作，由于它们的迭代器是复用红黑树的，所以红黑树中的迭代器也要实现++和--操作，list迭代器的++或--操作实现起来非常简单，只需利用next指针就好；反观红黑树，它的++/--操作要求必须满足中序遍历规则，红黑树的中序遍历是有序的，假设某棵红黑树的中序遍历是"1   3    5    6    7   9" ，如果迭代器在3这个位置，那么++后就必须到5，--后就必须到1。迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

那么如何实现++操作呢？(分为以下几种情况)

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的右子树存在

++后，只需找到右子树的最左结点即可。

2、cur的右子树为空

(1)cur是parent的左孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的右孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。最坏情况下，cur = _root，parent=nullptr，这时直接返回parent即可，我们这里让结束位置为nullptr。

代码实现：

Self& operator++()
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_right)  //右子树不为空，找右子树的最左结点
		{
			cur = cur->_right;
			while (cur->_left)
				cur = cur->_left;
			_node = cur;
		}
		else
		{
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
            //直到cur是parent的左，那么parent就是我们的目标   
            //极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent)
			_node = parent;
		}
		return  *this;

	}

那么如何实现--操作呢？(分为以下几种情况) 

迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为它访问顺序是右子树->根结点->
左子树。

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的左子树存在

--后，只需找到左子树的最右结点即可。

2、cur的左子树为空

(1)cur是parent的右孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的左孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。

代码实现：

Self& operator--()
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

完成这一步，我们迭代器的封装任务差不多已经完成了，接下来我们需要在红黑树中实现Begin和End：

public:
    typedef RBTreeIterator<T, T&, T*> Iterator;  //普通迭代器
    typedef RBTreeIterator<T, const T&,const T*> ConstIterator; //const迭代器

    Iterator Begin()
    {
	    Node* cur = _root;
	    while (cur->_left)
	    	cur = cur->_left;
    	return Iterator(cur);
    }
    Iterator End()
    {
    	return Iterator(nullptr);  //我们这里让nullptr当最终结点
    }

    ConstIterator Begin() const
    {
	    Node* cur = _root;
	    while (cur->_left)
		    cur = cur->_left;
	    return ConstIterator(cur);
    }
    ConstIterator End() const
    {
	    return ConstIterator(nullptr);
    }

在set中：

public:
	typedef typename RBTree<K, K, KeyOfSet>::Iterator iterator;
	typedef typename RBTree<K, K, KeyOfSet>::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();
	}

在map中：

public:
	typedef typename RBTree<K, pair<K, V>, KeyOfMap>::Iterator iterator;
	typedef typename RBTree<K, pair<K, V>, KeyOfMap>::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();
	}

 我们大致的任务已经完成了，接下来我们来写一段代码验证一下(看看是否会出现错误)：

//Test.cpp
#include "MyMap.h"
#include "MySet.h"

void TestSet()
{
	blue::set<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(6);

	blue::set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;
}

void TestMap()
{
	blue::map<string, string> dict;
	dict.insert({ "sort", "排序" });
	dict.insert({ "left", "左边" });
	dict.insert({ "right", "右边" });

	blue::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

int main()
{
	TestSet();
	cout << "-----------------------" << endl;
	TestMap();
	return 0;
}

运行结果：

运行结果暂时没有什么问题。

这里有一个bug，看下面测试代码：

void Print(const blue::set<int>& s)
{
	bit::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}

我们上面将end()指向nullptr，那么如果逆向遍历，--it就会出现错误，所以我们在--it时先判断一下，如果指向空，那么就修改_node为红黑树的最后一个结点，那么，问题又来了，怎么获得最后一个结点呢？所以我们需要知道红黑树的头结点，所以，我们在RBTreeIterator这个类中还需要一个成员变量来记录根节点：

修改operator--如下：

Self& operator--() 
	{
		if (_node == nullptr)
		{
			Node* cur = _root;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
			return *this;
		}

		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

解决完上述问题，还有一个问题，set和map中的K的值是不允许修改的，因为若修改就可能会破坏红黑树的结构，但我们写的代码中通过普通迭代器是能够修改的，如果要解决可以这样修改：

在set中：

在map中：

五、[]

好了，好了，到这里我们将上面的坑都踩完了，接下来最后最后一个功能，也是比较重要的，就是处理map中[]的实现逻辑：

map中的[]的逻辑其实就是利用了insert接口。

我们在红黑树中实现Insert的返回值是bool，接下来我们将它改为pair<Iterator,bool>类型：

pair<Iterator,bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		//return true;
		return { Iterator(_root, _root),true };
	}
	Node* parent = nullptr;
	Node* cur = _root;
	KeyOfT kot;
	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;
			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 true;
	return { Iterator(newnode, _root),true };
}

完成对Insert的调整后，在set和map的insert也要跟着调：

在set中：

在map中：

接下来，我们就着手实现[]，在map中：

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

是不是非常简单！ 

六、其他问题

1、构造函数

RBTree() = default;

2、拷贝构造

RBTree(const RBTree<K, T, KeyOfT>& t)
{
	_root = Copy(t._root);
}

Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;
	Node* newnode = new Node(root->_data);
	newnode->_left = Copy(root->_left);
	newnode->_right = Copy(root->_right);

	return newnode;
}

3、赋值重载

RBTree& operator=(RBTree tmp)
{
	swap(tmp._root);
	return *this;
}

4、析构函数

~RBTree()
{
	Destroy(_root);
	_root = nullptr;
}

void Destroy(Node* root)
{
	if (root == nullptr)
		return;

	Destroy(root->_left);
	Destroy(root->_right);
	delete root;
}

七、源码 

(1)RBTree.h

#pragma once
#include <iostream>
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)
	{}
};


//Ref和Ptr是为了兼容普通迭代器和const迭代器
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)
	{}

	Self& operator++() 
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_right)   //右子树不为空，找右子树的最左结点
		{
			cur = cur->_right;
			while (cur->_left)
				cur = cur->_left;
			_node = cur;
		}
		else
		{
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的左，那么parent就是我们的目标   
			//极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent) 
			_node = parent;
		}
		return  *this;
	}

	Self& operator--() 
	{
		if (_node == nullptr)
		{
			Node* cur = _root;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
			return *this;
		}

		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

	Ref operator*() const
	{
		return _node->_data;
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}
};



template<class K,class T,class KeyOfT>
class RBTree
{
public:
	RBTree() = default;
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}
	RBTree& operator=(RBTree tmp)
	{
		swap(tmp._root);
		return *this;
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&,const T*> ConstIterator;

	Iterator Begin()
	{
		Node* cur = _root;
		while (cur->_left)
			cur = cur->_left;
		return Iterator(cur,_root);
	}
	Iterator End()
	{
		return Iterator(nullptr,_root);
	}

	ConstIterator Begin() const
	{
		Node* cur = _root;
		while (cur->_left)
			cur = cur->_left;
		return ConstIterator(cur,_root);
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr,_root);
	}

public:
	pair<Iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			//return true;
			return { Iterator(_root,_root),true };
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		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;
				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 true;
		return { Iterator(newnode,_root),true };
	}


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

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

			Node* pParent = parent->_parent;

			subL->_right = parent;
			parent->_parent = subL;

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

				subL->_parent = pParent;
			}
		}
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

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

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->_data);
			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			return newnode;
		}

		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}
private:
	Node* _root = nullptr; 
};

(2)MySet.h 

#pragma once
#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, KeyOfSet>::Iterator iterator;
		typedef typename RBTree<K, const K, KeyOfSet>::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();
		}

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

(3)MyMap.h 

#pragma once
#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
		struct KeyOfMap
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::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();
		}

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

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

	private:
		RBTree<K, pair<const K, V>, KeyOfMap> _t;
	};
}

(4)Test.cpp 

#define _CRT_SECURE_NO_WARNINGS 1

#include "MyMap.h"
#include "MySet.h"

void Print(const blue::set<int>& s)
{
	blue::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}

void TestSet()
{
	blue::set<int> s;
	s.insert(5);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(6);

	blue::set<int>::iterator sit = s.begin();
	//*sit += 10;
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;


	Print(s);

}

void TestMap()
{
	blue::map<string, string> dict;
	dict.insert({ "sort", "排序" });
	dict.insert({ "left", "左边" });
	dict.insert({ "right", "右边" });

	dict["left"] = "左边，剩余";
	dict["insert"] = "插入";
	dict["string"];

	blue::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		// 不能修改first，可以修改second
		//it->first += 'x';
		it->second += 'x';

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

int main()
{
	TestSet();
	cout << "-----------------------" << endl;
	TestMap();
	return 0;
}

八、总结

本篇内容到这里就结束啦，主要讲了如何用红黑树来封装set和map容器，希望对大家有帮助，祝生活愉快！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/914950.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Leetcode3345. 最小可整除数位乘积 I

Leetcode3345. 最小可整除数位乘积 I

Every day a Leetcode 题目来源&#xff1a;3345. 最小可整除数位乘积 I 解法1&#xff1a;枚举 至多循环 10 次&#xff0c;一定会遇到个位数为 0 的数字&#xff0c;数位乘积是 0&#xff0c;一定是 t 的倍数。 所以暴力枚举即可。 代码&#xff1a; /** lc appleetcod…
阅读更多...
通过scrapy和Django登录、爬取和持久化数据

通过scrapy和Django登录、爬取和持久化数据

使用 Scrapy 和 Django 实现登录、爬取和持久化数据的完整流程&#xff0c;可以通过以下步骤完成&#xff1a; 创建 Django 项目和数据库模型&#xff1a;定义一个存储爬取数据的数据库模型。创建 Scrapy 项目&#xff1a;实现登录并抓取目标页面的数据。整合 Scrapy 和 Djang…
阅读更多...
SpringMVC全面复习

SpringMVC全面复习

Javaweb SpringMVC Spring MVC是Spring框架的一个模块&#xff0c;专门用于构建Web应用程序的模型-视图-控制器&#xff08;MVC&#xff09;架构。它通过清晰的分离关注点&#xff0c;简化了Web应用各部分的开发。Spring MVC提供了强大的绑定机制&#xff0c;能够将请求参数绑定…
阅读更多...
【再谈设计模式】抽象工厂模式~对象创建的统筹者

【再谈设计模式】抽象工厂模式~对象创建的统筹者

一、引言 在软件开发的世界里&#xff0c;高效、灵活且易于维护的代码结构是每个开发者追求的目标。设计模式就像是建筑蓝图中的经典方案&#xff0c;为我们提供了应对各种常见问题的有效策略。其中&#xff0c;抽象工厂模式在对象创建方面扮演着重要的角色&#xff0c;它如同一…
阅读更多...
【Linux】ELF可执行程序和动态库加载

【Linux】ELF可执行程序和动态库加载

&#x1f525; 个人主页&#xff1a;大耳朵土土垚 &#x1f525; 所属专栏&#xff1a;Linux系统编程 这里将会不定期更新有关Linux的内容&#xff0c;欢迎大家点赞&#xff0c;收藏&#xff0c;评论&#x1f973;&#x1f973;&#x1f389;&#x1f389;&#x1f389; 文章目…
阅读更多...
SpringBootCloud 服务注册中心Nacos对服务进行管理

SpringBootCloud 服务注册中心Nacos对服务进行管理

介绍 Nacos&#xff08;Naming and Configuration Service&#xff09;是一个开源的、动态的服务发现、配置管理和服务管理平台&#xff0c;特别适用于云原生应用和微服务架构。它可以作为服务注册中心&#xff0c;用于微服务的注册、发现、配置管理等。在微服务架构中&#x…
阅读更多...
八款局域网监控软件优选|2024最新排行榜(企业老板收藏篇)

八款局域网监控软件优选|2024最新排行榜(企业老板收藏篇)

在当今数字化办公的时代&#xff0c;企业和组织对于局域网电脑监控的需求日益增长。无论是为了保障信息安全、提高员工工作效率&#xff0c;还是为了规范网络行为&#xff0c;一款优秀的局域网电脑监控软件都能发挥重要作用。市面上的监控软件种类繁多&#xff0c;功能各异&…
阅读更多...
限价订单簿中的高频交易

限价订单簿中的高频交易

数量技术宅团队在CSDN学院推出了量化投资系列课程 欢迎有兴趣系统学习量化投资的同学&#xff0c;点击下方链接报名&#xff1a; 量化投资速成营&#xff08;入门课程&#xff09; Python股票量化投资 Python期货量化投资 Python数字货币量化投资 C语言CTP期货交易系统开…
阅读更多...
丹摩征文活动｜CogVideoX-2b：从0到1，轻松完成安装与部署！

丹摩征文活动｜CogVideoX-2b：从0到1，轻松完成安装与部署！

丹摩征文活动 | CogVideoX-2b&#xff1a;从0到1&#xff0c;轻松完成安装与部署&#xff01; CogVideoX 介绍 CogVideoX的问世&#xff0c;标志着视频制作技术迈入了一个全新的时代。它不仅打破了传统视频制作在效率与质量之间的平衡难题&#xff0c;还通过其先进的3D变分自…
阅读更多...
Creo 9.0 中文版软件下载安装教程

Creo 9.0 中文版软件下载安装教程

[软件名称]&#xff1a;Creo 9.0 [软件语言]&#xff1a;简体中文 [软件大小]&#xff1a;5.2G [安装环境]&#xff1a;Win11/Win10/ [硬件要求]&#xff1a;内存8G及以上 下载方法&#xff1a;电脑打开浏览器&#xff0c;复制下载链接&#xff0c;粘贴至浏览器网址栏&…
阅读更多...
RT-DETR融合CVPR[2024]无膨胀多尺度卷积PKI模块及相关改进思路

RT-DETR融合CVPR[2024]无膨胀多尺度卷积PKI模块及相关改进思路

RT-DETR使用教程&#xff1a; RT-DETR使用教程 RT-DETR改进汇总贴&#xff1a;RT-DETR更新汇总贴 《Poly Kernel Inception Network for Remote Sensing Detection》 一、 模块介绍 论文链接&#xff1a;https://arxiv.org/abs/2403.06258 代码链接&#xff1a;https://github…
阅读更多...
ubuntu-desktop-24.04上手指南(更新阿里源、安装ssh、安装chrome、设置固定IP、安装搜狗输入法)

ubuntu-desktop-24.04上手指南(更新阿里源、安装ssh、安装chrome、设置固定IP、安装搜狗输入法)

ubuntu-desktop-24.04上手指南(更新阿里源、安装ssh、安装chrome、设置固定IP、安装搜狗输入法) 一、更新并安装基础软件 #切换root用户 sudo su -#更新 apt update #升级 apt upgrade#install vim apt install vim#install net-tools apt install net-tools二、安装ssh并设置…
阅读更多...
[CKS] K8S ServiceAccount Set Up

[CKS] K8S ServiceAccount Set Up

最近准备花一周的时间准备CKS考试&#xff0c;在准备考试中发现有一个题目关于Rolebinding的题目。 ​ 专栏其他文章: [CKS] Create/Read/Mount a Secret in K8S-CSDN博客[CKS] Audit Log Policy-CSDN博客 -[CKS] 利用falco进行容器日志捕捉和安全监控-CSDN博客[CKS] K8S Netwo…
阅读更多...
介绍和安装及数据类型

介绍和安装及数据类型

1、介绍和安装 1.1、简介 ClickHouse是俄罗斯的Yandex于2016年开源的列式存储数据库&#xff08;DBMS&#xff09;&#xff0c;使用C语言编写&#xff0c;主要用于在线分析处理查询&#xff08;OLAP&#xff09;&#xff0c;能够使用SQL查询实时生成分析数据报告。 OLAP&…
阅读更多...
算法魅力-二分查找实战

算法魅力-二分查找实战

目录 前言 算法定义 朴素二分模版 二分查找 二分的边界查找 在排序数组中查找元素的第一个和最后一个位置&#xff08;medium&#xff09; 暴力算法 二分查找 边界查找分析 山峰数组的峰顶 暴力枚举 二分查找 搜索旋转排序数组中的最小值&#xff08;medium&#xf…
阅读更多...
Linux第四讲：Git gdb

Linux第四讲：Git gdb

Linux第四讲&#xff1a;Git && gdb 1.版本控制器Git1.1理解版本控制1.2理解协作开发1.3Git的历史1.4Git的操作1.4.1仓库创建解释、仓库克隆操作1.4.2本地文件操作三板斧1.4.3文件推送详细问题 2.调试器 -- gdb/cgdb使用2.1调试的本质是什么2.2watch命令2.3set var命令…
阅读更多...
海底捞点单

海底捞点单

单点锅底推荐&#xff1a; 番茄锅底通31 牛油麻辣通44 清汤麻辣备44 菌汤锅底通31 小吃&主食&#xff1a; 捞派捞面一黄金小馒头一茴香小油条 红糖枇杷一小酥肉 DIY锅底推荐&#xff1a; 1.寿喜锅&#xff1a;海鲜味酱4勺陈醋1勺蚝油2勺盐适量白糖7勺 芹菜1勺 2.麻辣锅底…
阅读更多...
PNG图片批量压缩exe工具+功能纯净+不改变原始尺寸

PNG图片批量压缩exe工具+功能纯净+不改变原始尺寸

小编最近有一篇png图片要批量压缩&#xff0c;大小都在5MB之上&#xff0c;在网上找了半天要么就是有广告&#xff0c;要么就是有毒&#xff0c;要么就是功能复杂&#xff0c;整的我心烦意乱。 于是我自己用python写了一个纯净工具&#xff0c;只能压缩png图片&#xff0c;没任…
阅读更多...
达梦8数据库适配ORACLE的8个参数

达梦8数据库适配ORACLE的8个参数

目录 1、概述 1.1 概述 1.2 实验环境 2、参数简介 3、实验部分 3.1 参数BLANK_PAD_MODE 3.2 参数COMPATIBLE_MODE 3.3 参数ORDER_BY_NULLS_FLAG 3.4 参数DATETIME_FMT_MODE 3.5 参数PL_SQLCODE_COMPATIBLE 3.6 参数CALC_AS_DECIMAL 3.7 参数ENABLE_PL_SYNONYM 3.8…
阅读更多...
如何低成本、零代码开发、5分钟内打造一个企业AI智能客服？

如何低成本、零代码开发、5分钟内打造一个企业AI智能客服？

传统客服因员工效率低、时段需求波动大、数据管理费时费力等管理难题&#xff0c;导致难以满足用户需求&#xff0c;无法深入挖掘客服数据价值&#xff0c;造成客源流失。而智能体搭建的“智能客服”能借助大模型和知识库知识&#xff0c;助力实现数字化运营&#xff0c;破解企…
阅读更多...
最新文章

Copyright @ 2022~2023