C++之模拟实现map和set-Toy模板网

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

红黑树源代码

#pragma once

enum color
{
	BLACK,
	RED
};
template<class K, class V>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	//存储的键值对
	pair<K, V> _kv;

	//结点的颜色
	color _col; //红/黑

	//构造函数
	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};


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* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			//如果插入key值小于根结点key值
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//如果插入key值大于根结点key值
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			//相等，返回false
			else
			{
				return false;
			}
		}

		//创建cur结点
		cur = new Node(kv);
		//颜色初始化为红色
		cur->_col = RED;

		//如果插入key值小于parent结点key值
		if (parent->_kv.first > kv.first)
		{
			//在左边插入
			parent->_left = cur;
		}
		//如果插入key值大于parent结点key值
		else
		{
			//在右边插入
			parent->_right = cur;
		}
		//跟父结点连接起来
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			//定义祖父节点
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);

			//如果父结点在祖父节点左边
			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);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					//插入结点在父结点左边
					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);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					//插入结点在父结点左边
					else
					{
						//右左双旋+颜色调整
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		//根结点变为黑色
		_root->_col = BLACK;
		return true;
	}
private:
	void RotateL(Node* parent)
	{
		//记录parent结点的父结点
		Node* ppNode = parent->_parent;

		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//建立parent与subRL之间的关系
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//建立parent与subR之间的关系
		subR->_left = parent;
		parent->_parent = subR;

		//判断根结点是否就是parent
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

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

		Node* ppNode = parent->_parent;

		//建立subLR与parent关系
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//建立subL与parent关系
		subL->_right = parent;
		parent->_parent = subL;

		//判断根结点是否就是parent
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
private:
	Node* _root = nullptr;
};

红黑树模板参数控制

我们可以知道，set属于K模型的容器，map属于KV模型的容器，那我们如何使用一棵红黑树来实现map和set呢？

我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template <class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	//....
private:
	Node* _root = nullptr;

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key：

namespace gtt
{
	template<class K>
	class set
	{
	public:
		//
	private:
		RBTree<K, K> _t;
	};
}

map它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对：

namespace gtt
{
	template<class K, class V>
	class map
	{
	public:
		//
	private:
		RBTree<K, pair<K, V>> _t;
	};
}

我们需要注意的是模板中第一个参数K是不可以省略掉的，对于set容器来说第一个参数K和第二个参数K都是一样的，并不会影响什么，对于map容器来说，进行find或者erase时，我们依然需要返回一个key类型的迭代器，所以第一个K不可以省略。

红黑树结点当中存储的数据

对于上层结构：

map：K代表键值Key，T代表由Key和Value构成的键值对。
set容器：K和T都代表键值Key。

对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了，这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。
C++之模拟实现map和set,c++,开发语言
代码如下：

template<class T>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储数据
	T _data;

	//结点的颜色
	color _col; //红/黑

	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_data(data)
		, _col(RED)
	{}
};

仿函数的增加

对于set容器，我们需要进行键值比较就是对key值进行比较，也就是直接比较T就可以了，但是对于map容器来说，我们需要比较的是键值对<key，value>中的key，我们需要先将key提取出来，在进行比较。

所以，我们需要在上层map和set中各提供一个仿函数，根据传入的T类型分开进行比较操作：

set仿函数：

namespace gtt
{
	template<class K>
	class set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

map仿函数：

namespace gtt
{
	template<class K, class V>
	class map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		//
	private:
		RBTree<K, pair<K, V>, MapKeyOfT> _t;
	};
}

我们提供了仿函数以后，在进行传参的过程，编译器就会识别我们是需要调用map进行比较还是调用set进行比较，不同的容器调用不同的比较方式：
C++之模拟实现map和set,c++,开发语言

正向迭代器的实现

红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

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

	Node* _node;

	//构造函数
	__TreeIterator(Node* node)
		:_node(node)
	{}
};

* 运算符重载

解引用操作，我们直接返回结点数据的引用即可：

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

->运算符重载

->也就是返回结点数据的地址：

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

!=和==运算符重载

!=和==就是判断两个迭代器所封装的结点是否是同一个

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

++运算符重载

红黑树的正向迭代器时，一个结点的正向迭代器进行++操作后，应该根据红黑树中序遍历的序列找到当前结点的下一个结点。

逻辑就是：

如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。

前置++代码如下：

Self& operator++()
{
	//右子树不为空，就去找右子树中最左节点
	if (_node->_right)
	{
		Node* left = _node->_right;

		while (left->_left)
		{
			left = left->_left;
		}
		//++后变为该结点
		_node = left;
	}
	//右子树为空，就去找孩子不在父亲右的祖先
	else
	{
		Node* parent = _node->_parent;
		Node* cur = _node;

		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = parent->_parent;
		}
		//++后变为该结点
		_node = parent;
	}

	return *this;
}

- -运算符重载

红黑树的正向迭代器时，一个结点的正向迭代器进行–操作后，应该根据红黑树中序遍历的序列找到当前结点的前一个结点：

逻辑如下：

如果当前结点的左子树不为空，则–操作后应该找到其左子树当中的最右结点。
如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

代码如下：文章来源地址https://www.toymoban.com/news/detail-707346.html

Self& operator--()
{
	//左子树不为空，就去找左子树中最右节点
	if (_node->_left)
	{
		Node* right = _node->_left;

		while (right->_right)
		{
			right = right->_right;
		}
		//--后变为该结点
		_node = right;
	}
	//左子树为空，就去找孩子不在父亲左的祖先
	else
	{
		Node* parent = _node->_parent;
		Node* cur = _node;

		while (parent && cur == parent->_left)
		{
			cur = parent;
			parent = parent->_parent;
		}
		//--变为该结点
		_node = parent;
	}
}

begin()与end()实现

begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;//正向迭代器
	
	iterator begin()
	{
		Node* left = _root;
		
		//寻找最左结点
		while (left && left->_left)
		{
			left = left->_left;
		}

		//返回最左结点的正向迭代器
		return iterator(left);
	}

	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器
		return iterator(nullptr);
	}
private:
	Node* _root = nullptr;

set的模拟实现

namespace gtt
{
	template<class K>
	class set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		//begin()
		iterator begin()
		{
			//调用红黑树的begin()
			return _t.begin();
		}
		//end()
		iterator end()
		{
			//调用红黑树的end()
			return _t.end();
		}
		//插入函数
		pair<iterator, bool> Insert(const K& key)
		{
			//调用红黑树的Insert
			return _t.Insert(key);
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

map的模拟实现

namespace gtt
{
	template<class K, class V>
	class map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		//begin()
		iterator begin()
		{
			return _t.begin();
		}
		//end()
		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;
	};

封装后红黑树代码

#pragma once

enum color
{
	BLACK,
	RED
};
template<class T>
struct RBTreeNode
{
	//三叉链
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	//存储数据
	T _data;

	//结点的颜色
	color _col; //红/黑

	//构造函数
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		,_data(data)
		, _col(RED)
	{}
};

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

	Node* _node;

	//构造函数
	__TreeIterator(Node* node)
		:_node(node)
	{}

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

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

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

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

	Self& operator++()
	{
		//右子树不为空，就去找右子树中最左节点
		if (_node->_right)
		{
			Node* left = _node->_right;

			while (left->_left)
			{
				left = left->_left;
			}
			//++后变为该结点
			_node = left;
		}
		//右子树为空，就去找孩子不在父亲右的祖先
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;

			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//++后变为该结点
			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		//左子树不为空，就去找左子树中最右节点
		if (_node->_left)
		{
			Node* right = _node->_left;

			while (right->_right)
			{
				right = right->_right;
			}
			//--后变为该结点
			_node = right;
		}
		//左子树为空，就去找孩子不在父亲左的祖先
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;

			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//--变为该结点
			_node = parent;
		}
	}
};

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;//正向迭代器
	iterator begin()
	{
		Node* left = _root;
		
		//寻找最左结点
		while (left && left->_left)
		{
			left = left->_left;
		}

		//返回最左结点的正向迭代器
		return iterator(left);
	}

	iterator end()
	{
		//返回由nullptr构造得到的正向迭代器
		return iterator(nullptr);
	}
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//根结点为空
		if (_root == nullptr)
		{
			//创建根结点
			_root = new Node(data);
			//颜色变为黑
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}

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

		while (cur)
		{
			//如果插入key值小于根结点key值
			if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			//如果插入key值大于根结点key值
			else if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			//相等，返回false
			else
			{
				return make_pair(iterator(cur), false);
			}
		}

		//创建cur结点
		cur = new Node(data);
		Node* newnode = cur;
		//颜色初始化为红色
		cur->_col = RED;

		//如果插入key值小于parent结点key值
		if (kot(parent->_data) > kot(data))
		{
			//在左边插入
			parent->_left = cur;
		}
		//如果插入key值大于parent结点key值
		else
		{
			//在右边插入
			parent->_right = cur;
		}
		//跟父结点连接起来
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			//定义祖父节点
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);

			//如果父结点在祖父节点左边
			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);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					//插入结点在父结点左边
					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);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					//插入结点在父结点左边
					else
					{
						//右左双旋+颜色调整
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		//根结点变为黑色
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}
	void RotateL(Node* parent)
	{
		//记录parent结点的父结点
		Node* ppNode = parent->_parent;

		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		//建立parent与subRL之间的关系
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//建立parent与subR之间的关系
		subR->_left = parent;
		parent->_parent = subR;

		//判断根结点是否就是parent
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

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

		Node* ppNode = parent->_parent;

		//建立subLR与parent关系
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		//建立subL与parent关系
		subL->_right = parent;
		parent->_parent = subL;

		//判断根结点是否就是parent
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
private:
	Node* _root = nullptr;
};