map和set底层实现【C++】

文章目录

map和set模板参数
红黑树结点中的数据
模板参数中的仿函数
正向迭代器
- ++运算符重载
- --运算符重载
库里的写法
set
map
RBTree

map和set模板参数

set是K模型的容器，而map是KV模型的容器
如何用一棵KV模型的红黑树同时实现map和set

  template<class K ,class V>
	class map
	{
	// ...
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t; //map，MapKeyOfT是仿函数
	};

	class set
	{
	//...
	private:
		RBTree<K,K,SetKeyOfT> _t;
	};//set，SetKeyOfT是仿函数

红黑树结点中的数据

红黑树的节点是K还是T，对于set都是一样的 ,对于map,底层红黑树就只能存储T了。底层红黑树不知道上层容器是map还是set，因此红黑树的结点当中直接存储T就行了。

当上层容器是set，结点当中存储的是键值Key；当上层容器是map，结点当中存储的就是<Key, Value>键值对。

template<class T >
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{

	}
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;//颜色
};

模板参数中的仿函数

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

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

当上层容器是set，T就是键值Key，直接用T进行比较即可
当上层容器是map，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较
上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了

对于底层红黑树，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。

因此，set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。

当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较例如：

//查找函数
iterator Find(const K& key)
{
	KeyOfT kot;
	Node* cur = _root;
	while (cur)
	{
		if (key < kot(cur->_data)) //key值小于该结点的值
		{
			cur = cur->_left; //在该结点的左子树当中查找
		}
		else if (key > kot(cur->_data)) //key值大于该结点的值
		{
			cur = cur->_right; //在该结点的右子树当中查找
		}
		else //找到了目标结点
		{
			return iterator(cur); //返回该结点
		}
	}
	return end(); //查找失败
}

正向迭代器

struct  _TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef _TreeIterator<T,Ptr,Ref> Self;
	typedef _TreeIterator<T, T*, T&> iterator;
};
//构造函数
__TreeIterator(Node* node)
	:_node(node) //根据所给结点指针构造一个正向迭代器
{}

++运算符重载

1、右子树不为空，访问右树的最左节点（即为下一个节点）
2、如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。


	Self & operator++()//前置++，返回++之后的值
	{
		//右子树不为空，访问右树的最左节点
		//左子树不为空，如何解决？
		if (_node->_right != nullptr)
		{
			//右树的最左节点(右树的最小节点)
			Node* subLeft = _node->_right;
			while (subLeft->_left != nullptr)
			{
				subLeft = subLeft->_left;
			}
			_node = subLeft;
		 }
		else//_node->_left != nulltptr
		{
			// 下一个要访问的节点，找孩子是父亲左的那个祖先节点

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

			while (parent!=nullptr)
			{
				if (parent->_left != cur)
				{
					//往上更新
					cur = parent;
					parent = parent->_parent;
				}
				else//parent->_left == cur
				{
					break;
				}
			
			}
			_node = parent;
		}
		return *this;
	}

–运算符重载

1、左子树存在，找当前节点的左子树中最右边的节点，就是所需要的节点
2、如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

	Self& operator--()//前置-- 
		//右子树 、根 、左子树（中序反过来） 
	{
		 
		// 左子树存在 
		//将当前节点的左子树中最右边的节点，就是所需要的节点
		if (_node->_left != nullptr)
		{
			Node* subRight = _node->_left;
			while (subRight && subRight->_right)
			{
				subRight = subRight->_right;
			}
			_node = subRight;
		}
		//右子树存在
		//找孩子是父亲的右的那个节点
		else//_node->_right != nullptr
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent!=nullptr)
			{
				//向上调整 
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;		
		}
		return *this;
	}

库里的写法

上述所实现的迭代器是有缺陷的，因为理论上我们对end()位置的正向迭代器进行–操作后，应该得到最后一个结点的正向迭代器，但我们实现end()时，是直接返回由nullptr构造得到的正向迭代器的，因此上述实现的代码无法完成此操作

C++SLT库当中的实现逻辑：
在这里插入图片描述
在红黑树的根结点处增加了一个头结点，
该头结点的左指针指向红黑树当中的最左结点，
右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。

在该结构下，实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可，实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器），而实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行–操作后得到最后一个结点的正向迭代器。

set

#pragma once 

#include "RBTree.h"
namespace cxq
{
	template<class K>//set只有一个模板参数
	class set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K & operator()( const K &key)
			{
				return key;
			}
		};
	public:
		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)
		{
			
			//return _t.insert(kv); //这样写return的是pair<RBTree::iterator , bool>,所以不能这样写

			//库里面的写法
			pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); //这个iterator是普通迭代器
			return pair<iterator, bool>(ret.first, ret.second);//这个iterator是const_iterator
		}
	private:
		RBTree<K,K,SetKeyOfT> _t;
	};
}

map

#pragma once 
#include"RBTree.h"
namespace cxq
{
  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< const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair< const K, V>, MapKeyOfT>::const_iterator  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();
		}

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

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

	};
}

RBTree

#pragma once 
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
enum Colour
{
	RED,
	BLACK
};

template<class T >
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{

	}
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;//颜色


};

template <class T,class Ptr,class Ref>
struct  _TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef _TreeIterator<T,Ptr,Ref> Self;
	typedef _TreeIterator<T, T*, T&> iterator;

	//？？
	_TreeIterator(const iterator & it)
		:_node(it._node)
	{

	}


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

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

	 Ptr operator->()// T * operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self & s)
	{
		return _node != s._node;
	}
	Self& operator--()//前置-- 
		//右子树 、根 、左子树（中序反过来） 
	{
		 
		// 左子树存在 
		//将当前节点的左子树中最右边的节点，就是所需要的节点
		if (_node->_left != nullptr)
		{
			Node* subRight = _node->_left;
			while (subRight && subRight->_right)
			{
				subRight = subRight->_right;
			}
			_node = subRight;
		}
		//右子树存在
		//找孩子是父亲的右的那个节点
		else//_node->_right != nullptr
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent!=nullptr)
			{
				//向上调整 
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;		
		}
		return *this;
	}
	Self & operator++()//前置++，返回++之后的值
	{
		//右子树不为空，访问右树的最左节点
		//左子树不为空，如何解决？
		if (_node->_right != nullptr)
		{
			//右树的最左节点(右树的最小节点)
			Node* subLeft = _node->_right;
			while (subLeft->_left != nullptr)
			{
				subLeft = subLeft->_left;
			}
			_node = subLeft;
		 }
		else//_node->_left != nulltptr
		{
			// 下一个要访问的节点，找孩子是父亲左的那个祖先节点

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

			while (parent!=nullptr && cur == parent->_right)
			{
				//	往上更新
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Node* _node;

};


template <class K, class T,class KeyOfT >
struct RBTree
{
	typedef RBTreeNode<T> Node;

public:
	//同一个类模板，传的不同参数，实例化不同的类型
	typedef _TreeIterator<T,T* ,T&> iterator;
	typedef _TreeIterator<T, const T* , const T &> const_iterator;//const的位置如何选择 
public:
	iterator begin()
	{
		//最左边即最小值节点
		Node* leftMin = _root;
		while (leftMin!=nullptr && leftMin->_left!=nullptr)
		{
			leftMin = leftMin->_left;

		}
		return iterator(leftMin);//支持单参数构造支持隐式类型转换

	}
	iterator end() 
	{
		return iterator(nullptr);//支持单参数构造支持隐式类型转换
	}


	const_iterator begin()const
	{
		//最左边即最小值节点
		Node* leftMin = _root;
		while (leftMin != nullptr && leftMin->_left != nullptr)
		{
			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!= nullptr)
		{	
			if (kot(cur->_data) < key)
			{
				cur = cur->_left;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_right;
			}
			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 != nullptr)
		{
			//用仿函数比较 
			if (kot(cur->_data	) > kot(data ))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_data)  < kot(data) )
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(  iterator(cur) ,false);
			}
		}


		cur = new Node(data);
		cur->_col = RED;
		Node* newnode = cur;
		//将插入节点插入到树中 
		if (kot(parent->_data) > kot(data) ) //用仿函数 
		{
			parent->_left = cur;
		}
		else//kot(parent->_data) < kot(data)
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//如果插入节点的父节点是红色，分三种情况进行调整 
		while (parent!=nullptr &&parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			assert(grandfather);
			assert(grandfather->_col == BLACK);


			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//插入结点的叔叔存在，且颜色是红色
				if (uncle != nullptr && uncle->_col == RED)
				{


					//parent 、uncle  变黑
					//grandfather变红
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上处理 
					cur = grandfather;
					parent = cur->_parent;
				}
				//插入结点的叔叔存在，且颜色是黑色
				//插入节点的叔叔不存在
				//这两种情况统一处理
				else  if (uncle != nullptr && uncle->_col == BLACK || uncle == nullptr)
				{
					//先旋转再变色

					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_right 
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}

			}
			else//parent == grandfather->_right
			{
				Node* uncle = grandfather->_left;
				//插入结点的叔叔存在，且颜色是红色
				if (uncle != nullptr && uncle->_col == RED)
				{


					//parent 、uncle  变黑
					//grandfather变红
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					//向上处理 
					cur = grandfather;
					parent = cur->_parent;
				}
				//插入结点的叔叔存在，且颜色是黑色
				//插入节点的叔叔不存在
				//这两种情况统一处理
				else  if (uncle != nullptr && uncle->_col == BLACK || uncle == nullptr)
				{
					//先旋转再变色

					if (cur == parent->_left)
					{
						//双旋	
						
						RotateR(parent);
						RotateL(grandfather); 


						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					else//cur == parent->_right 
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}

			}
		}



		_root->_col = BLACK;
		return make_pair(iterator(newnode),true);
	}
	void RotateL(Node* parent)
	{
		_rotateCount++;
		Node* cur = parent->_right;

		Node* curleft = cur->_left;

		//parent和curleft链接
		parent->_right = curleft;
		if (curleft != nullptr)
		{
			
			curleft->_parent = parent;
		}
		//cur和parent链接
		cur->_left = parent;

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

		//parent 是根节点
		if (parent == _root)
		{
			cur->_parent = nullptr;
			_root = cur;
		}
		else//parent 是一个子树 
		{
			//parent是一个左子树
			

		
			if (ppnode->_left == parent)
			{
				//3和ppnode链接
				ppnode->_left = cur;
				cur->_parent = ppnode;
			}
			//parent是一个右子树
			else
			{
				//3和ppnode链接
				ppnode->_right = cur;
				cur->_parent = ppnode;
			}
		}

	}
	void RotateR(Node* parent)
	{
		_rotateCount++;
		Node* cur = parent->_left;
		Node* curright = cur->_right;

		//cur和parent 链接 

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

		//curright和parent链接 
		parent->_left = curright;
		if (curright != nullptr)
		{
			curright->_parent = parent;
		}



		
		if (parent == _root)//parent是根节点
		{
			cur->_parent = nullptr;
			_root = cur;//更新根节点
		}
		else//parent一个子树 
		{
			//parent是左子树 
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
				cur->_parent = ppnode;
			}
			else//(ppnode->_right == parent)
				//parent是右子树 
			{
				ppnode->_right = cur;
				cur->_parent = ppnode;
			}
		}


	}

	bool CheckColour(Node* root, int blacknum, int benchMark)
	{
		if (root == nullptr)
		{
			//blacknum是一条路径上的黑色节点总数 
			if (blacknum != benchMark)
			{
				return  false;
			}
			return false;
		}
		else if (root->_col == BLACK)
		{
			blacknum++;

		}
		else if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << "连续的红节点：" << root->_kv.first << endl;
			return false;
		}

		return   CheckColour(root->_left, blacknum, benchMark)
			&& CheckColour(root->_right, blacknum, benchMark);
	}
	bool IsBalance()
	{
	  return 	_IsBalance(_root);
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return  true;
		}
		//根节点必须是黑色
		if (root->_col != BLACK)
		{
			return false;
		}
		//基准值
		//求最左路径的黑色节点
		int benchMark = 0;
		Node* cur = _root;
		while (cur != nullptr)
		{
			if (cur->_col == BLACK)
			{
				benchMark++;
			}
			cur = cur->_left;
		}
		return CheckColour(root, 0, benchMark);
	}
	int Height()
	{
		return _Height(_root);
	}
    int _Height(Node *root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return  leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
private:
	Node* _root = nullptr;
public:
	int _rotateCount = 0;
};