【C++】set和map封装

2023-12-13 08:00:46

我们用上期写的红黑树来模拟一下C++中set和map的封装

一、STL中的set和map

二、底层红黑树的修改

三、set和map的封装

3.1 insert

3.2 增添仿函数来确定红黑树底层进行比较的数据类型

3.3?增添仿函数来确定红黑树底层进行比较的方式

3.4? map和set的迭代器实现

3.5 map的operate[]的实现

一、STL中的set和map

我们先来看看STL中set和map的实现源码：

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
  // typedefs:

  typedef Key key_type;
  typedef Key value_type;
  typedef Compare key_compare;
  typedef Compare value_compare;
private:
  typedef rb_tree<key_type, value_type, 
                  identity<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing set
  //·····
}

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:

// typedefs:

  typedef Key key_type;
  typedef T data_type;
  typedef T mapped_type;
  typedef pair<const Key, T> value_type;
  typedef Compare key_compare;
    
//·····

private:
  typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
  rep_type t;  // red-black tree representing map

//·····
}

咦？这实现的怎么和想象中的有些不一样，其底层都用到了一个rb_tree，我们来看看这个rb_tree的源码：

template <class Key, class Value, class KeyOfValue, class Compare,
          class Alloc = alloc>
class rb_tree {
protected:
  typedef void* void_pointer;
  typedef __rb_tree_node_base* base_ptr;
  typedef __rb_tree_node<Value> rb_tree_node;
  typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
  typedef __rb_tree_color_type color_type;
  
  //·····
}

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
  typedef __rb_tree_node<Value>* link_type;
  Value value_field;
};

struct __rb_tree_node_base
{
  typedef __rb_tree_color_type color_type;
  typedef __rb_tree_node_base* base_ptr;

  color_type color; 
  base_ptr parent;
  base_ptr left;
  base_ptr right;
//·····
}

哦~原来STL中的set和map使用的底层红黑树都是同一个结构（只存一个元素类型），set中红黑树存储的元素类型为T，map中存储类型为pair<const Key，T>

二、底层红黑树的修改

我们想要使用自己手搓的红黑树来封装set和map，就要对原来的实现结构做一些修改：

#include<iostream>

using namespace std;

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

template<class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root, * parent = nullptr;
		while (cur)//找到合适的位置
		{
			if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(data);
		//将插入的节点连接上二叉树
		if (data < parent->_data)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = 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)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
					{
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的右边,p在g的左边，构成一条折线
					{
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
					{
						//左单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的左边,p在g的右边，构成一条折线
					{
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
		}
		_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
		return true;
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			cout << "根节点颜色是红色" << endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		// 连续红色节点
		return _Check(_root, 0, benchmark);
	}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
	}

	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				cout << "某条路径黑色节点的数量不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			cout << "存在连续的红色节点" << endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
private:
	Node* _root = nullptr;
};

三、set和map的封装

3.1 insert

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

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

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

	private:
		RBTree<K, K> _t;
	};
}

insert函数的实现很简单，直接调用即可

3.2 增添仿函数来确定红黑树底层进行比较的数据类型

但是我们基于底层实现的红黑树，map的数据比较是按pair类型来进行的，这显然并不符合我们的需求，所以我们需要再向RBTree传入一个仿函数来提取pair中的first成员来进行比较：

namespace lhs
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool insert(const pair<const K, V>&data)
		{
			return _t.Insert(data);
		}

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

namespace lhs
{
	template<class K>
	class set
	{
		struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, K, SetKeyOfT> _t;
	};
}

#include<iostream>

using namespace std;

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

template<class K, class T, class KeyOft>//根据KeyOfT传入的仿函数来确定比较类型
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* cur = _root, * 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
			{
				cout << "插入的值重复" << endl;
				return false;
			}
		}
		cur = new Node(data);
		//将插入的节点连接上二叉树
		if (kot(data) < kot(parent->_data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		//开始调整
		//.......
	}

//......
private:
	Node* _root = nullptr;
};

3.3?增添仿函数来确定红黑树底层进行比较的方式

当然确定了map中的比较类型也不行，万一比较方式不符合用户的预期，我们需要通过模版传入仿函数来替换比较的方式：

namespace lhs
{
	template<class K, class Compare = less<K>>
	class set
	{
		struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, K, SetKeyOfT, Compare> _t;
	};
}

namespace lhs
{
	template<class K, class V, class Compare = less<K>>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool insert(const pair<const K, V>&data)
		{
			return _t.Insert(data);
		}

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

#include<iostream>

using namespace std;

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型，根据Compare传入的方式来确定比较方式
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}
		Node* cur = _root, * parent = nullptr;
		KeyOft kot;//创建仿函数对象
		Compare cmp;
		while (cur)//找到合适的位置
		{
			if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) == kot(cur->_data))
			{
				cout << "插入的值重复" << endl;
				return false;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		cur = new Node(data);
		//将插入的节点连接上二叉树
		if (cmp(kot(data), kot(parent->_data)))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		//开始调整
        //.......
	}

private:
	Node* _root = nullptr;
};

3.4? map和set的迭代器实现

红黑树迭代器的实现和我们讲解list迭代器的实现基本一致，这里不再一步步赘述，不熟悉的同学可以看到这里：【C++】深入剖析list

在红黑树对于迭代器的++操作会有不同的方式来进行处理：

#include<iostream>

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

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& n)
	{
		return _node != n._node;
	}

	Self& operator++()//++就是走中序遍历的顺序
	{
		if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		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* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;

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

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

	const_iterator cbegin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

	const_iterator cend()
	{
		return const_iterator(nullptr);
	}

private:
	Node* _root = nullptr;
};

namespace lhs
{
	template<class K, class V, class Compare = std::less<K>>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;

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

	private:
		RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
	};
}

namespace lhs
{
	template<class K, class Compare = std::less<K>>
	class set
	{
		struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, K, SetKeyOfT, Compare>::iterator iterator;

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

	private:
		RBTree<K, K, SetKeyOfT, Compare> _t;
	};
}

3.5 map的operate[]的实现

map的operate[]的实现底层调用的是insert函数，所以我们需要在之前实现的insert函数上做一些修改：

#include<iostream>

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

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& n)
	{
		return _node != n._node;
	}

	Self& operator++()//++就是走中序遍历的顺序
	{
		if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		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* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;

	std::pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return std::make_pair(iterator(_root), true);
		}
		Node* cur = _root, * parent = nullptr;
		KeyOft kot;//创建仿函数对象
		Compare cmp;
		while (cur)//找到合适的位置
		{
			if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) == kot(cur->_data))
			{
				std::cout << "插入的值重复" << std::endl;
			    return std::make_pair(iterator(cur), false);
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		cur = new Node(data);
		//将插入的节点连接上二叉树
		if (cmp(kot(data), kot(parent->_data)))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		Node* newnode = cur;//记录新增节点位置，方便构造返回迭代器，防止调整后cur位置发生改变
		//开始调整
		while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
					{
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的右边,p在g的左边，构成一条折线
					{
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
					{
						//左单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的左边,p在g的右边，构成一条折线
					{
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
		}
		_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
		return std::make_pair(iterator(newnode), true);;
	}
private:
	Node* _root = nullptr;
};

namespace lhs
{
	template<class K, class V, class Compare = std::less<K>>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;

		V& operator[](const K& key)//调用Insert来实现
		{
			std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
			return ret.first->second;
		}

	private:
		RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
	};
}

四、set和map封装的完整代码

RBTree.h:

#pragma once
#include<iostream>

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)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(RED)//默认构造时,优先将节点的颜色置为红色
	{}
};

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& n)
	{
		return _node != n._node;
	}

	Self& operator++()//++就是走中序遍历的顺序
	{
		if (_node->_right)//如果右子树不为空，就找到右子树的最左节点
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		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* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else//左子树为空,向上找到孩子节点是父亲右孩子的那个节点
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

template<class K, class T, class KeyOft, class Compare>//根据KeyOfT传入的仿函数来确定比较类型,根据Compare传入的方式来确定比较方式
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	~RBTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;

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

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

	const_iterator cbegin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}

	const_iterator cend()
	{
		return const_iterator(nullptr);
	}

	std::pair<iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return std::make_pair(iterator(_root), true);
		}
		Node* cur = _root, * parent = nullptr;
		KeyOft kot;//创建仿函数对象
		Compare cmp;
		while (cur)//找到合适的位置
		{
			if (cmp(kot(data), kot(cur->_data)))//通过仿函数调出我们想要比较的成员,再按我们预期的方式进行比较
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) == kot(cur->_data))
			{
				std::cout << "插入的值重复" << std::endl;
				return std::make_pair(iterator(cur), false);
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		cur = new Node(data);
		//将插入的节点连接上二叉树
		if (cmp(kot(data), kot(parent->_data)))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		Node* newnode = cur;//记录新增节点位置，方便构造返回迭代器，防止调整后cur位置发生改变
		//开始调整
		while (parent && parent->_col == RED)//红黑树的结构出现两个连续的红色节点
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_left)//cur在p的左边,p也在g的左边，构成一条直线
					{
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的右边,p在g的左边，构成一条折线
					{
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)//cur为红，p为红，g为黑，u存在且为红
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续向上更新
					cur = grandfather;
					parent = cur->_parent;
				}
				elsecur为红，p为红，g为黑，u不存在/u存在且为黑
				{
					if (cur == parent->_right)//cur在p的右边,p也在g的右边，构成一条直线
					{
						//左单旋
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur在p的左边,p在g的右边，构成一条折线
					{
						//右左双旋
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;//调整完跳出
				}
			}
		}
		_root->_col = BLACK;//确保即便进行过调整后根节点颜色为黑
		return std::make_pair(iterator(newnode), true);;
	}

	bool IsBalance()
	{
		if (_root && _root->_col == RED)
		{
			std::cout << "根节点颜色是红色" << std::endl;
			return false;
		}

		int benchmark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++benchmark;
			cur = cur->_left;
		}

		// 连续红色节点
		return _Check(_root, 0, benchmark);
	}

private:
	void RotateL(Node* parent)//左单旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;
		parent->_right = subRL;//更新parent的右节点
		if (subRL)//防止该节点为空
		{
			subRL->_parent = parent;//更新subRL的父节点
		}
		parent->_parent = subR;//更新parent的父节点
		subR->_left = parent;//subR的左子树置为parent
		subR->_parent = pparent;//更新subR的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subR;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subR;
			}
			else
			{
				pparent->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)//右单旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;
		parent->_left = subLR;//更新parent的左节点
		if (subLR)//防止该节点为空
		{
			subLR->_parent = parent;//更新subLR的父节点
		}
		parent->_parent = subL;//更新parent的父节点
		subL->_right = parent;//subL的右子树置为parent
		subL->_parent = pparent;//更新subL的父节点
		if (pparent == nullptr)//旋转的是整棵树
		{
			_root = subL;//更新根节点
		}
		else//将旋转后的子树链接上整个二叉树
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}
	}

	bool _Check(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)
		{
			if (benchmark != blackNum)
			{
				std::cout << "某条路径黑色节点的数量不相等" << std::endl;
				return false;
			}

			return true;
		}

		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED
			&& root->_parent
			&& root->_parent->_col == RED)
		{
			std::cout << "存在连续的红色节点" << std::endl;
			return false;
		}

		return _Check(root->_left, blackNum, benchmark)
			&& _Check(root->_right, blackNum, benchmark);
	}

	void _Destroy(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
private:
	Node* _root = nullptr;
};

Map.h:

#pragma once
#include"RBTree.h"
namespace lhs
{
	template<class K, class V, class Compare = std::less<K>>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const std::pair<const K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT,Compare>::iterator iterator;

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

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

		V& operator[](const K& key)//调用Insert来实现
		{
			std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
			return ret.first->second;
		}

	private:
		RBTree<K, std::pair<const K, V>, MapKeyOfT, Compare> _t;
	};
}

Set.h：

#pragma once
#include"RBTree.h"
namespace lhs
{
	template<class K, class Compare = std::less<K>>
	class set
	{
		struct SetKeyOfT//set中仿函数没有什么实际作用,只是为了和map配套
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, K, SetKeyOfT, Compare>::iterator iterator;

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

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

	private:
		RBTree<K, K, SetKeyOfT, Compare> _t;
	};
}

文章来源:https://blog.csdn.net/m0_70811813/article/details/134951789
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！