C++：set和map的底层封装模拟实现

发布于：2024-05-18 ⋅ 阅读:(126) ⋅ 点赞:(0)

目录

底层对比：

底层红黑树结构和set、map： 

底层模拟：

传值调用：

迭代器：

operator ++（）

 find函数

operator（） 、仿函数 

set和map的仿函数 ：

图解： 

insert函数：

构造函数，析构函数： 

 析构函数：

拷贝构造函数： 

赋值函数： 

map的封装：

set的封装： 

红黑树的修改： 


底层对比：

上图以kv模型为例 

通过底层可以看出：

  • set和map的底层调用都是调用了红黑树 rb_tree
  • set和map在底层最大的区别就是value的不同，set的value仍然是key类型的，但是map的value是pair<const key，T>类型的
  • 也因为类型的不同，二者使用的template 类模板也相差了一个class T ，而这个class T表示的其实就是map的value中的second的数值类型
  • 同时因为value的不同，所以导致了map和set在红黑树中存储的数据也并不相同

底层红黑树结构和set、map： 

底层模拟：

传值调用：

迭代器：

  • 不论是set还是map 的迭代器，关键得是看红黑树的迭代器
  • 树的内部迭代器其实就是和链表相差不多，需要进行一个内部的重载调用
  • 也就是说 operator-> operator * operator ++ operator --都是需要进行内部重载，然后进行封装的！
 RBTree.h

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;
	}

	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个，右树最左节点
			Node* leftMin = _node->_right;
			while (leftMin->_left)
			{
				leftMin = leftMin->_left;
			}

			_node = leftMin;
		}
		else
		{
			// 下一个，孩子等于父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};

operator ++（）

是实现迭代器的难点之一，因为红黑树的本质其实是二叉搜索树，所以遍历是使用中序遍历，所以++和--都是使用 中序遍历的节点，如下图所示，it所在位置的下一个节点是15 

 首先我们需要知道，中序遍历的过程是 左子树 根节点 右子树 所以可以通过下图右可以得出：

  • 当前it所在的位置是它父亲节点的左节点，那么下一个需要遍历的节点就是it的父亲节点
  • 当前节点的右子树是空的，那么表示这个节点的右子树结束遍历，下一个需要遍历和++递达的节点，应该往上进行查找祖先节点
  • 如果当前节点的右子树是空的，且当前节点是其父亲节点的右节点，那么表示要去父亲节点更往上的方向寻找下一个需要遍历的节点
  • 如果当前节点的右子树是空的/遍历完了，且当前节点是其父亲节点的左节点，那么表示当前节点结束，返回父亲节点且下一个访问的节点就是父亲节点，且同时访问完后需要取父亲节点的右子树中进行遍历和寻找下一个++位置的节点
  • 最后一个单独的处理，那就是走到最后一个节点的时候，走到最后一个节点的右子树是空的，就一直返回到根节点，这时候就需要给迭代器置空了！

 

  • ++的下一个节点是该节点右子树中的最左节点！
  • leftMin = node->right 表示进入右子树中寻找最左节点，当然现在的条件是右子树存在，如果右子树存在就是上面，如果不存在就需要往上边寻找，直到找到某个节点是它父亲节点的左节点为止，或者说找到的某个节点，他没有父亲节点它是根节点为止！

  • 要求当前的节点是他父亲节点的右节点，如果一直是这样就需要一直往上走，直到当前节点是它父亲节点的左节点时，返回父亲节点
  • 且需要注意如果当前节点是根节点，那么它的父亲就是空的，空的不能再继续往上寻找了，所以直接跳出循环，最后返回父亲节点！
RBTree.h
//红黑树中调动迭代器的函数方法
typedef __RBTreeIterator<T, T&, T*> Iterator;
typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;

Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return Iterator(leftMin);
	}

	Iterator End()
	{
		return Iterator(nullptr);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr);
	}

	ConstIterator Begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return ConstIterator(leftMin);
	}

 find函数

RBTree.h

Iterator Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur);
			}
		}

		return End();
	}

operator（） 、仿函数 

 使用仿函数的原因其实是在insert函数中需要使用operator()的原因，因为在insert函数中，需要使用比较大小之间的问题，而为了让红黑树同时适应set和map（主要是针对map的pair内部问题），需要对取值之间进行正确取值的操作。

如上图所示，在set中data可以直接对于set中的value，但是对于map来说，需要在pair中进行取值，所以map需要一个详细的对应关系，这就造成了仿函数Key0fT的诞生

RBTree.h

//树的最终的基础结构
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
    typedef __RBTreeIterator<T, T&, T*> Iterator;
    typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;
private:
	Node* _root = nullptr;
};

set和map的仿函数 ：

        //Myset.h
        struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
       
        //Mymap.h
        struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

图解： 

insert函数：

pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(Iterator(_root), true);
		}

		KeyOfT kot;//调用了仿函数，方便之后的比较
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// K
			// pair<K, V>
			// kot对象，是用来取T类型的data对象中的key
			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 make_pair(Iterator(cur), 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;

		// 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)
					{
						//     g  
						//   p   u
						// c 
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g  
						//   p     u
						//      c 
						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 // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//		g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

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

构造函数，析构函数： 

 析构函数：

~RBTree()
	{
		Destroy(_root);

		_root = nullptr;
	}

private:

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

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

拷贝构造函数： 

 拷贝构造函数使用的是前序遍历，且内部需要三条链接的拷贝和构造，也就是左子树、右子树、和父亲节点，同时也需要进行节点颜色的拷贝操作，所以拷贝构造的内部其实是一个前序遍历+颜色的拷贝+左右子树的拷贝和链接+递归遍历

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

Node* Copy(Node* root)
	{//因为要有父亲节点的链接，所以需要一个反向链接
     //其次也需要进行颜色的拷贝！因为是红黑树！
		if (root == nullptr)
			return nullptr;

		Node* newroot = new Node(root->_data);
		newroot->_col = root->_col;

		newroot->_left = Copy(root->_left);
		if (newroot->_left)
			newroot->_left->_parent = newroot;

		newroot->_right = Copy(root->_right);
		if (newroot->_right)
			newroot->_right->_parent = newroot;

		return newroot;
	}

赋值函数： 

//RBTree.h
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

map的封装：

namespace bit
{
	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, const K, MapKeyOfT>::ConstIterator const_iterator;

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end() const
		{
			return _t.End();
		}

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

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

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

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

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

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

set的封装： 

namespace bit
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end() const
		{
			return _t.End();
		}

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

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

		iterator find(const K& key)
		{
			return _t.Find(key);
		}

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

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

	void PrintSet(const set<int>& s)
	{
		for (auto e : s)
		{
			cout << e << endl;
		}
	}

红黑树的修改： 

 

#pragma once
#include<vector>

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

	Self& operator++()
	{
		if (_node->_right)
		{
			// 下一个，右树最左节点
			Node* leftMin = _node->_right;
			while (leftMin->_left)
			{
				leftMin = leftMin->_left;
			}

			_node = leftMin;
		}
		else
		{
			// 下一个，孩子等于父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}
};

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

public:
	typedef __RBTreeIterator<T, T&, T*> Iterator;
	typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;

	RBTree() = default;

	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}
	
	// t2 = t1
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}

	~RBTree()
	{
		Destroy(_root);

		_root = nullptr;
	}

	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return Iterator(leftMin);
	}

	Iterator End()
	{
		return Iterator(nullptr);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr);
	}

	ConstIterator Begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return ConstIterator(leftMin);
	}

	Iterator Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur);
			}
		}

		return End();
	}
	// 20:10
	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(Iterator(_root), true);
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// K
			// pair<K, V>
			// kot对象，是用来取T类型的data对象中的key
			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 make_pair(Iterator(cur), 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;

		// 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)
					{
						//     g  
						//   p   u
						// c 
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g  
						//   p     u
						//      c 
						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 // 叔叔不存在，或者存在且为黑
				{
					// 情况二：叔叔不存在或者存在且为黑
					// 旋转+变色
					//      g
					//   u     p
					//            c
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//		g
						//   u     p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;
				}
			}
		}

		_root->_col = BLACK;

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

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

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

		subL->_right = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subL;

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

			subL->_parent = ppNode;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

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

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		if (_root->_col == RED)
		{
			return false;
		}

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

			cur = cur->_left;
		}

		return Check(_root, 0, refNum);
	}

private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* newroot = new Node(root->_data);
		newroot->_col = root->_col;

		newroot->_left = Copy(root->_left);
		if (newroot->_left)
			newroot->_left->_parent = newroot;

		newroot->_right = Copy(root->_right);
		if (newroot->_right)
			newroot->_right->_parent = newroot;

		return newroot;
	}

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

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

	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (refNum != blackNum)
			{
				cout << "存在黑色节点的数量不相等的路径" << endl;
				return false;
			}

			return true;
		}

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

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

		return Check(root->_left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}

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

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

private:
	Node* _root = nullptr;
	//size_t _size = 0;
};

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布