【STL】set和map的模拟实现-创新互联

前言

创新互联-专业网站定制、快速模板网站建设、高性价比大悟网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式大悟网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖大悟地区。费用合理售后完善，10余年实体公司更值得信赖。

map和set容器的底层使用的红黑树, set只存储值, map存储键值对

为了体现复用思想, 红黑树存储类型统一为K/T模型, 如果是set实现T则传K, map实现T则传pair

再通过仿函数KeyOfT来取到T中的K类型对象key

注: 以下只是模拟实现的迭代器/插入功能

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once

enum Color
{
	RED,
	BLACK
};

templatestruct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Color _col;
	T _val;
	//构造
	RBTreeNode(const T& val)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)//默认添加的新节点为红色
		, _val(val)
	{}
};

templatestruct Iterator
{
	typedef RBTreeNodeNode;
	typedef IteratorSelf;
	Iterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_val;
	}

	Ptr operator->()
	{
		//return &(_node->_val);
		return &(*Iterator(_node));
	}

	bool operator==(const Self& val)const
	{
		return _node == val._node;
	}

	bool operator!=(const Self& val)const
	{
		return _node != val._node;
	}

	//前置++
	Self& operator++()
	{
		if (_node->_right != nullptr)
		{
			//找右节点为根节点的最左节点
			Node* left = _node->_right;
			while (left->_left != nullptr)
			{
				left = left->_left;
			}
			_node = left;
		}
		else
		{
			Node* parent = _node->_parent;
			Node* cur = _node;
			//如果当前是父的左,说明还没走过,下一步要走到父;
			//如果当前是父的右,说明已经走过了,下一步循环判断父是爷的左还是右,重复这个过程
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//出循环说明1.parent为nullptr说明到了end()2.当前是父的左
			//结论:下一步都要走到parent
			_node = parent;
		}
		return *this;
	}

	//前置--
	//与前置++逻辑逆置
	Self& operator--()
	{
		if (_node->_left != nullptr)
		{
			Node* right = _node->_left;
			while (right->_right != nullptr)
			{
				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;
		}
		return *this;
	}

	Node* _node;
};

templateclass RBTree
{
public:
	typedef RBTreeNodeNode;
	typedef Iteratoriterator;
	
	iterator begin()
	{
		Node* cur = root;
		while (cur && cur->_left != nullptr)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}

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

	pairinsert(const T& val)
	{
		KeyOfT key;
		if (root == nullptr)
		{
			//如果此时为空树
			root = new Node(val);
			//将根节点修正为黑色
			root->_col = BLACK;
			return make_pair(iterator(root), true);
		}
		Node* cur = root;
		Node* parent = nullptr;//cur的父节点
		while (cur)
		{
			if (key(cur->_val) >key(val))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (key(cur->_val)< key(val))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				//如果插入的节点是重复值, 则插入失败
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(val);
		if (key(parent->_val) >key(cur->_val))
		{
			parent->_left = cur;
		}
		else if (key(parent->_val)< key(cur->_val))
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		//以上为插入节点
		//-------------------------------------------------------
		//以下为调整为红黑树
		//因为默认插入的节点为红色,所以如果出现了两个连续为红的节点就需要处理
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			Node* uncle = nullptr;
			//确定叔叔节点的位置
			if (grandfather->_left == parent)
			{
				uncle = grandfather->_right;
			}
			else//grandfather->_right == parent
			{
				uncle = grandfather->_left;
			}
			//将分为三种情况
			//1.父节点为红,叔叔节点存在且为红(变色 + 向上迭代)
			//2/3.父节点为红,叔叔节点不存在或者存在且为黑(旋转 + 变色)
			if (uncle && uncle->_col == RED)//情况一
			{
				//父变黑,叔叔变黑,祖父变红->向上迭代
				parent->_col = BLACK;
				uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else//情况二/三
			{
				//情况二
				//     g
				//   p   u
				// c
				if (uncle == grandfather->_right && cur == parent->_left)
				{
					//右单旋
					RotateR(grandfather);
					//
					parent->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
				//     g
				//   u   p
				//         c 
				else if (uncle == grandfather->_left && cur == parent->_right)
				{
					//左单旋
					RotateL(grandfather);
					//
					parent->_col = BLACK;
					grandfather->_col = RED;
					break;

				}
				//情况三
				//     g
				//   u   p
				//     c
				else if (uncle == grandfather->_left && cur == parent->_left)
				{
					//左双旋
					RotateRL(grandfather);
					//
					grandfather->_col = RED;
					cur->_col = BLACK;
					break;

				}
				//     g
				//   p   u
				//     c
				else if (uncle == grandfather->_right && cur == parent->_right)
				{
					//右双旋
					RotateLR(grandfather);
					//
					grandfather->_col = RED;
					cur->_col = BLACK;
					break;

				}
				else
				{
					cout<< "不存在这种情况"<< endl;
					exit(-1);
				}
			}
		}
		root->_col = BLACK;
		return make_pair(iterator(cur), true);
	}

	void inorder()
	{
		_inorder(root);
	}

	bool isRBTree()
	{
		if (root->_col == RED)
		{
			cout<< "出错: 根节点为红"<< endl;
			return false;
		}
		//判断是否有连续红节点,且每条路径的黑节点是否相等
		int benchmark = 0;//算出最左路径的黑节点个数
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++benchmark;
			}
			cur = cur->_left;
		}
		return _isRBTree(root, 0, benchmark);
	}

private:
	//四种旋转
	void RotateL(Node* prev)
	{
		Node* subR = prev->_right;
		Node* subRL = subR->_left;
		Node* ppNode = prev->_parent;

		prev->_right = subRL;
		if (subRL)
		{
			subRL->_parent = prev;
		}

		subR->_left = prev;
		prev->_parent = subR;

		if (root == prev)
		{
			root = subR;
		}
		else
		{
			if (ppNode->_left == prev)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
		}
		subR->_parent = ppNode;
	}

	void RotateR(Node* prev)
	{
		Node* subL = prev->_left;
		Node* subLR = subL->_right;
		Node* ppNode = prev->_parent;

		subL->_right = prev;
		prev->_parent = subL;

		prev->_left = subLR;
		if (subLR)
		{
			subLR->_parent = prev;
		}

		if (root == prev)
		{
			root = subL;
		}
		else
		{
			if (ppNode->_left == prev)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
		}
		subL->_parent = ppNode;
	}

	void RotateRL(Node* prev)
	{
		//先右旋, 再左旋
		RotateR(prev->_right);
		RotateL(prev);
	}

	void RotateLR(Node* prev)
	{
		//先左旋, 再右旋
		RotateL(prev->_left);
		RotateR(prev);
	}

	void _inorder(Node* root)
	{
		if (root)
		{
			_inorder(root->_left);
			cout<< root->_kv.first<< "--"<< root->_kv.second<< endl;
			_inorder(root->_right);
		}
	}

	bool _isRBTree(Node* root, int blackNum, int benchmark)
	{
		if (root == nullptr)//走到空节点
		{
			if (benchmark == blackNum)
			{
				//for debug
				//cout<< blackNum<< endl;
				return true;
			}
			else
			{
				//for debug
				//cout<< blackNum<< endl;
				cout<< "不是所有路径的黑色节点个数都相同"<< endl;
				return false;
			}
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}
		//判断是否有连续的红节点
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout<< "出现了连续的红色节点"<< endl;
			return false;
		}
		return _isRBTree(root->_left, blackNum, benchmark)
			&& _isRBTree(root->_right, blackNum, benchmark);
	}

	Node* root = nullptr;
};

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"


templateclass Set
{
public:
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	
	typedef typename RBTree::iterator iterator;

	pairinsert(const K& key)
	{
		return _t.insert(key);
	}

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

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

private:
	RBTree_t;
};

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"

templateclass Map
{
public:
	struct MapKeyOfT
	{
		const K& operator()(const pair& kv)
		{
			return kv.first;
		}
	};

	typedef typename RBTree, MapKeyOfT>::iterator iterator;

	pairinsert(const pair& kv)
	{
		return _t.insert(kv);
	}

	V& operator[](const K& key)
	{
		pairret = insert(make_pair(key, V()));
		return ret.first->second;
	}

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

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

private:
	RBTree, MapKeyOfT>_t;
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧