【C++】map & set 底层刨析

慈云数据 2024-04-08 技术支持 44 0

文章目录

  • 1. 红黑树的迭代器
  • 2. 改造红黑树
  • 3. map 的模拟实现
  • 4. set 的模拟实现

    在这里插入图片描述

    在 C++ STL 库中,map 与 set 的底层为红黑树,那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。

    1. 红黑树的迭代器

    迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器,需要考虑以下问题:

    • begin() 与 end()

      STL 明确规定,begin() 与 end() 代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,可以得到一个有序的序列,因此:begin() 可以放在红黑树中最小节点(即最左侧节点)的位置,end() 放在最大节点(最右侧节点)的下一个位置。

      iterator begin()
      {
      	Node* subLeft = _root;
      	while (subLeft && subLeft->_left)
      	{
      		subLeft = subLeft->_left;
      	}
      	return iterator(subLeft);
      }
      const_iterator begin() const
      {
      	Node* subLeft = _root;
      	while (subLeft && subLeft->_left)
      	{
      		subLeft = subLeft->_left;
      	}
      	return const_iterator(subLeft);
      }
      iterator end()
      {
      	return iterator(nullptr);
      }
      const_iterator end() const
      {
      	return const_iterator(nullptr);
      }
      
    • operator++() 与 operator--()

      Self& operator++()
      {
      	if (_node->_right)
      	{
      		// 右子树的中序第一个(最左节点)
      		Node* subLeft = _node->_right;
      		while (subLeft->_left)
      		{
      			subLeft = subLeft->_left;
      		}
      		_node = subLeft;
      	}
      	else
      	{
      		// 祖先里面孩子是父亲左的那个
      		Node* cur = _node;
      		Node* parent = cur->_parent;
      		while (parent && cur == parent->_right)
      		{
      			cur = parent;
      			parent = cur->_parent;
      		}
      		_node = parent;
      	}
      	return *this;
      }
      Self& operator--()
      {
      	// 跟++逻辑相反
      	return *this;
      }
      

      2. 改造红黑树

      #pragma once
      enum Color
      {
      	RED,
      	BLACK
      };
      template
      struct RBTreeNode
      {
      	RBTreeNode* _left;
      	RBTreeNode* _right;
      	RBTreeNode* _parent;
      	Color _col;
      	T _data;
      	RBTreeNode(const T& data)
      		: _left(nullptr)
      		, _right(nullptr)
      		, _parent(nullptr)
      		, _data(data)
      		, _col(RED)
      	{}
      };
      template
      struct RBTreeIterator
      {
      	typedef RBTreeNode Node;
      	typedef RBTreeIterator Self;
      	Node* _node;
      	RBTreeIterator(Node* node)
      		: _node(node)
      	{}
      	T& operator*()
      	{
      		return _node->_data;
      	}
      	T* operator->()
      	{
      		return &_node->_data;
      	}
      	Self& operator++()
      	{
      		if (_node->_right)
      		{
      			// 右子树的中序第一个(最左节点)
      			Node* subLeft = _node->_right;
      			while (subLeft->_left)
      			{
      				subLeft = subLeft->_left;
      			}
      			_node = subLeft;
      		}
      		else
      		{
      			// 祖先里面孩子是父亲左的那个
      			Node* cur = _node;
      			Node* parent = cur->_parent;
      			while (parent && cur == parent->_right)
      			{
      				cur = parent;
      				parent = cur->_parent;
      			}
      			_node = parent;
      		}
      		return *this;
      	}
      	Self& operator--()
      	{
      		// 跟++逻辑相反
      		return *this;
      	}
      	bool operator!=(const Self& s)
      	{
      		return _node != s._node;
      	}
      	bool operator==(const Self& s)
      	{
      		return _node == s._node;
      	}
      };
      // set->RBTree
      // map->RBTree
      // 因为关联容器存储的是的键值对,因此
      // K为key的类型
      // T:如果是map,则为pair;如果是set,则为K
      // KeyOfT仿函数,取出T对象中的key
      template
      class RBTree
      {
      	typedef RBTreeNode Node;
      public:
      	typedef RBTreeIterator iterator;
      	typedef RBTreeIterator const_iterator;
      	iterator begin()
      	{
      		Node* subLeft = _root;
      		while (subLeft && subLeft->_left)
      		{
      			subLeft = subLeft->_left;
      		}
      		return iterator(subLeft);
      	}
      	const_iterator begin() const
      	{
      		Node* subLeft = _root;
      		while (subLeft && subLeft->_left)
      		{
      			subLeft = subLeft->_left;
      		}
      		return const_iterator(subLeft);
      	}
      	iterator end()
      	{
      		return iterator(nullptr);
      	}
      	const_iterator end() const
      	{
      		return const_iterator(nullptr);
      	}
      	iterator Find(const K& key)
      	{
      		KeyOfT kot;
      		Node* cur = _root;
      		while (cur)
      		{
      			if (kot(cur->_data) _right;
      			}
      			else if (kot(cur->_data) > key)
      			{
      				cur = cur->_left;
      			}
      			else
      			{
      				return iterator(cur);
      			}
      		}
      		return end();
      	}
      	pair 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)
      		{
      			if (kot(cur->_data) _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;
      		if (kot(parent->_data) _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)
      					{
      						//     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 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;
      			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;
      		parent->_left = subLR;
      		if (subLR)
      			subLR->_parent = parent;
      		subL->_right = parent;
      		Node* ppnode = parent->_parent;
      		parent->_parent = subL;
      		if (parent == _root)
      		{
      			_root = subL;
      			subL->_parent = nullptr;
      		}
      		else
      		{
      			if (ppnode->_left == parent)
      			{
      				ppnode->_left = subL;
      			}
      			else
      			{
      				ppnode->_right = subL;
      			}
      			subL->_parent = ppnode;
      		}
      	}
      private:
      	Node* _root = nullptr;
      };
      

      3. map 的模拟实现

      map 的底层结构就是红黑树,因此在 map 中直接封装一棵红黑树,然后将其接口包装下即可。

      #pragma once
      #include "RBTree.h"
      namespace tjq
      {
      	template
      	class map
      	{
      		struct MapKeyOfT
      		{
      			const K& operator()(const pair& kv)
      			{
      				return kv.first;
      			}
      		};
      	public:
      		typedef typename RBTree::iterator iterator;
      		typedef typename RBTree::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();
      		}
      		pair insert(const pair& kv)
      		{
      			return _t.Insert(kv);
      		}
      		iterator find(const K& key)
      		{
      			return _t.Find(key);
      		}
      		V& operator[](const K& key)
      		{
      			pair ret = insert(make_pair(key, V()));
      			return ret.first->second;
      		}
      	private:
      		RBTree _t;
      	};
      }
      

      4. set 的模拟实现

      set 的底层为红黑树,因此只需在 set 内部封装一棵红黑树,即可将该容器实现出来。

      #pragma once
      #include "RBTree.h"
      namespace tjq
      {
      	template
      	class set
      	{
      		struct SetKeyOfT
      		{
      			const K& operator()(const K& key)
      			{
      				return key;
      			}
      		};
      	public:
      		typedef typename RBTree::iterator iterator;
      		typedef typename RBTree::const_iterator const_iterator;
      		iterator begin()
      		{
      			return _t.begin();
      		}
      		iterator end()
      		{
      			return _t.end();
      		}
      		pair insert(const K& key)
      		{
      			return _t.Insert(key);
      		}
      		iterator find(const K& key)
      		{
      			return _t.Find(key);
      		}
      	private:
      		RBTree _t;
      	};
      }
      

      END
微信扫一扫加客服

微信扫一扫加客服

点击启动AI问答
Draggable Icon