【map、set的封装】

2023-09-20 14:48:21

前言

本文的代码是基于前一篇文章的红黑树的代码来封装map、set。

一、map、set的框架搭建

在这里插入图片描述
代码:
map:

namespace Ting
{
	template<class K,class V>
	class map
	{
	public:
		struct KeyOfT
		{
			K& operator()(const pair<K,V>& p)
			{
				return p.first;
			}
		};
	private:
		RBTree<K, pair<K,V>, KeyOfT> _t;
	};
}

set:

namespace Ting
{
	template<class K>
	class set
	{
	public:
		struct KeyOfT
		{
			K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		RBTree<K, K,KeyOfT> _t;
	};
}

二、map、set的迭代器的封装

2.1、map、set的迭代器的初步封装

首先先对树的迭代器进行代码编写

template<class T>
class __TreeIterator
{
	typedef __TreeIterator<T> self;
public:
	typedef RBTreeNode<T> Node;

	__TreeIterator(Node* node)
		:_node(node)
	{}


	self& operator++()
	{
		if (_node->_right)
		{
			//找node右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent)
			{
				if (cur == parent->_left)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
		}
		return *this;
	}

	T* operator->()
	{
		return &_node->_date;
	}

	T& operator*()
	{
		return _node->_date;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
private:
	Node* _node;
};
template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef  __TreeIterator<T> iterator;

	RBTree()
		:_root(nullptr)
	{}

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

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

map

#pragma once
#include"RBTree.h"
namespace Ting
{
	template<class K,class V>
	class map
	{
	public:
		struct KeyOfT
		{
			K operator()(const pair<K,V>& p)
			{
				return p.first;
			}
		};

		typedef typename RBTree<K, pair<K, V>, KeyOfT>::iterator iterator;

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

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

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

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

set

#pragma once
#include"RBTree.h"
namespace Ting
{
	template<class K>
	class set
	{

	public:
		struct KeyOfT
		{
			K operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree<K, K, KeyOfT>::iterator iterator;


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

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

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

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

2.2、map、set的const迭代器的封装

2.2.1、set的const迭代器的封装

目标:set的key不能被修改
第一步:先利用模板参数设计出树的const的迭代器

template<class T,class Ptr,class Ref>
class __TreeIterator
{
	typedef __TreeIterator<T,Ptr,Ref> self;
public:
	typedef RBTreeNode<T> Node;

	__TreeIterator(Node* node)
		:_node(node)
	{}


	self& operator++()
	{
		if (_node->_right)
		{
			//找node右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent)
			{
				if (cur == parent->_left)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
		}
		return *this;
	}

	Ptr operator->()
	{
		return &_node->_date;
	}

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

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
private:
	Node* _node;
};

在这里插入图片描述
第二步: begin()、end()

	typedef  __TreeIterator<T, T*, T&> iterator;
	typedef  __TreeIterator<T, const T*, const T&> const_iterator;


	RBTree()
		:_root(nullptr)
	{}

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

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

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

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

第三步: 很关键也很巧妙
在这里插入图片描述

2.2.2、map的const迭代器的封装

#pragma once
#include"RBTree.h"
namespace Ting
{
	template<class K,class V>
	class map
	{
	public:
		struct KeyOfT
		{
			K operator()(const pair<K,V>& p)
			{
				return p.first;
			}
		};

		typedef typename RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, KeyOfT>::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();
		}

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

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

在这里插入图片描述

三、operator[ ]

**第一步:**对RBTree中插入的返回值类型进行修改

pair<iterator,bool> insert(const T& date)
	{
		if (_root == nullptr)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			return make_pair(_root,true);
		}
		KeyOfT kt;

		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if (kt(cur->_date)> kt(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if ((kt(cur->_date) < kt(date)))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		cur = new Node(date);
		Node* newnode = cur;
		if (kt(parent->_date) > kt(date))
		{
			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)
				{
					//变色加向上调整
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或者叔叔是黑色
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);

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

					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);

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

		}
		_root->_col = BLACK;
		return make_pair(newnode,true);

	}

然后该完后会发现编译报错。如图:
在这里插入图片描述
原因是:
在这里插入图片描述
**解决办法:**给迭代器写个构造函数让迭代器支持普通迭代器构造const迭代器
在这里插入图片描述

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

四、代码实现

MySet.h

#pragma once
#include"RBTree.h"
namespace Ting
{
	template<class K>
	class set
	{

	public:
		struct KeyOfT
		{
			K operator()(const K& key)
			{
				return key;
			}
		};
		typedef typename RBTree<K, K, KeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, KeyOfT>::const_iterator const_iterator;

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

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

		pair<iterator,bool> insert(const K& key)
		{
			pair<typename RBTree<K, K, KeyOfT>::iterator, bool> ret = _t.insert(key);
			return make_pair(ret.first, ret.second);
		}

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

MyMap.h

#pragma once
#include"RBTree.h"
namespace Ting
{
	template<class K,class V>
	class map
	{
	public:
		struct KeyOfT
		{
			K operator()(const pair<K,V>& p)
			{
				return p.first;
			}
		};

		typedef typename RBTree<K, pair<const K, V>, KeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, KeyOfT>::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<iterator,bool> insert(const pair<K, V>& p)
		{
			return _t.insert(p);
		}

		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>, KeyOfT> _t;
	};
}

RBTree.h

#pragma once
#include<iostream>
using namespace std;

enum Colour
{
	RED,
	BLACK
};
template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _date;
	Colour _col;

	RBTreeNode(const T& date)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _date(date)
		, _col(RED)
	{}

};

template<class T,class Ptr,class Ref>
struct __TreeIterator
{
	typedef __TreeIterator<T, Ptr, Ref> self;
	typedef __TreeIterator<T, T*, T&> Iterator;
	typedef RBTreeNode<T> Node;

	__TreeIterator(const Iterator& it)
		:_node(it._node)
	{}

	__TreeIterator(Node* node)
		:_node(node)
	{}


	self& operator++()
	{
		if (_node->_right)
		{
			//找node右子树的最左结点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent)
			{
				if (cur == parent->_left)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
		}
		return *this;
	}

	Ptr operator->()
	{
		return &_node->_date;
	}

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

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}

	Node* _node;
};

template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef  __TreeIterator<T, T*, T&> iterator;
	typedef  __TreeIterator<T, const T*, const T&> const_iterator;

	
	RBTree()
		:_root(nullptr)
	{}

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

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

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

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	pair<iterator,bool> insert(const T& date)
	{
		if (_root == nullptr)
		{
			_root = new Node(date);
			_root->_col = BLACK;
			return make_pair(_root,true);
		}
		KeyOfT kt;

		Node* parent = _root;
		Node* cur = _root;
		while (cur)
		{
			if (kt(cur->_date)> kt(date))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if ((kt(cur->_date) < kt(date)))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		cur = new Node(date);
		Node* newnode = cur;
		if (kt(parent->_date) > kt(date))
		{
			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)
				{
					//变色加向上调整
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或者叔叔是黑色
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					else
					{
						RotateL(parent);
						RotateR(grandfather);

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

					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);

						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);

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

		}
		_root->_col = BLACK;
		return make_pair(newnode,true);

	}

	bool isBalance()
	{
		return isBalance(_root);
	}

	bool checkcolour(Node* root, int basevalue,int blacknum)
	{
		if (root == nullptr)
		{
			if (basevalue != blacknum)
			{
				return false;
			}
			return true;
		}
		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			return false;
		}
		if (root->_col == BLACK)
		{
			blacknum++;
		}
		return checkcolour(root->_left, basevalue, blacknum) &&
			   checkcolour(root->_right, basevalue, blacknum);
	}

	bool isBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		if (root->_col != BLACK)
		{
			return false;
		}
		//计算最左路基中黑色结点数量
		int basevalue = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				basevalue++;
			}
			cur = cur->_left;
		}

		return checkcolour(root, basevalue,0);
	}

	void inorder()
	{
		inorder(_root);
	}

	void inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		inorder(root->_left);
		cout << root->_p.first << endl;
		inorder(root->_right);
	}


private:
	Node* _root;
	void RotateL(Node* parent)
	{
	//右边高  左旋
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	Node* ppnode = parent->_parent;

	parent->_right = curleft;
	if (curleft)
	{
		curleft->_parent = parent;
	}
	cur->_left = parent;
	parent->_parent = cur;

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

	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curRight = cur->_right;
		Node* ppnode = parent->_parent;

		parent->_left = curRight;
		if (curRight)
		{
			curRight->_parent = parent;
		}

		cur->_right = parent;
		parent->_parent = cur;

		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
	}
};
更多推荐

【GPU编程】Visual Studio创建基于GPU编程的项目

vs创建基于GPU编程的项目🍊前言🐸方法一-CUDARuntime生成😝debug设置🍅方法二-空项目配置🍉🍉🍉代码验证🍊前言cuda以及cudnn的安装以及系统环境变量的配置默认已经做完。如果没有安装好配置好的,可以参考其他的博客。本博客只为记录在完成以上配置后,如何在vs端创建GPU编程的项目。🐸

多线程中的Semaphore信号量

在Java多线程编程中,Semaphore是一种用于控制资源访问的机制。Semaphore允许您限制同时访问某个资源的线程数量。这在需要限制并发访问的情况下非常有用,例如数据库连接池或有限数量的线程池。创建Semaphore要使用Semaphore,首先需要创建一个Semaphore对象并指定许可证数量。许可证数量表示

提升群辉AudioStation音乐体验,实现公网音乐播放

文章目录本教程解决的问题是:按照本教程方法操作后,达到的效果是本教程使用环境:1群晖系统安装audiostation套件2下载移动端app3内网穿透,映射至公网很多老铁想在上班路上听点喜欢的歌或者相声解解闷儿,于是打开手机上的某雅软件和某音乐软件点进去一看:奈何目前移动端的娱乐软件广告很烦人,不知不觉就会点进去而且不好

vue基础知识十一:Vue组件之间的通信方式都有哪些?

一、组件间通信的概念开始之前,我们把组件间通信这个词进行拆分组件通信都知道组件是vue最强大的功能之一,vue中每一个.vue我们都可以视之为一个组件通信指的是发送者通过某种媒体以某种格式来传递信息到收信者以达到某个目的。广义上,任何信息的交通都是通信组件间通信即指组件(.vue)通过某种方式来传递信息以达到某个目的举

动漫ip受著作权法保护吗?

受保护的,不过你得申请版权保护,不然,你难以说明这个作品的所有者是你啊,你可以了解一下可信时间戳,他能起到版权保护的作用。版权保护的重点是证明:什么人在什么时间拥有什么作品,只要原创作者能提供这样的证据就能保护自己的版权。现在每个地级城市基本上都有版权局,你可以通过版权局对你的作品进行版权登记证书的申请来保护自己的版权

【实训项目】智联校友会小程序

1.项目背景作为某某省唯一一所中医药高等院校,××大学已经走过了30个春秋,截止到现在,我校已有近十万名校友遍布全国各地,校友在社会各界享有良好声誉,校友与学校相互成为密不可分的无形资源。然而,在广大在校学生中,还有很多校友意识薄弱,对和自己息息相关的校友工作并不了解。校友会管理系统是代表学校联系和服务校友的职能系统,

半导体产品使用高温老化测试技术

主要功能:为了达到满意的合格率,几乎所有产品在出厂前都必须经过老化处理。制造商如何在不缩短老化时间的情况下提高效率?本文介绍了一种在老化过程中进行功能测试的新方法,以减少和缩短与老化过程相关的成本和时间问题。在半导体行业,关于器件老化存在着各种争论。与其他产品一样,半导体随时可能因各种原因而失效。老化是通过使半导体超载

spring ioc

1.什么是SpringSpring框架是一个分层的、面向切面的Java应用程序的一站式轻量级解决方案,它是Spring技术栈的核心和基础,是为了解决企业级应用开发的复杂性而创建的。>简单来说,Spring是一个轻量级的控制反转(IoC)和面向切面(AOP)的容器框架。介于SpringMVC与Mybatis之间的中间层框

【java】【SpringBoot】【四】原理篇 bean、starter、核心原理

目录一、自动配置1、bean加载方式(复习)1.1加载方式-xml方式生命bean1.2加载方式-xml+注解方式声明bean1.3注解方式声明配置类1.4FactoryBean1.5proxyBeanMethod属性1.6使用@Import注解导入1.7使用上下文对象在容器初始化完毕后注入bean1.8导入实现了Im

Django Web开发入门基础

官方有很详细的文档,但是看过几遍之后如果要翻找还是有点麻烦,本文算作是学习笔记,提取一些关键点记录下来,另附上官方教程WritingyourfirstDjangoapp注:文中的指令使用py,是在Windows上,macOS要使用python31.安装DjangoDjango是一个基于Python的Web开发框架,安装

git使用说明

配置hosts配置C:\Windows\System32\drivers\etc\hosts192.168.**.**git.wl.com本地git账号配置(xxx在gitlab个人profile中)打开gitbashgitconfig--globaluser.namexxxxgitconfig--globaluser

热文推荐