当前位置：网站首页 > 程序开发学习 > 正文

【C++】map与set的封装

作者：小教学发布时间：2023-09-27分类：程序开发学习浏览：71

导读：文章目录前言正文1.类型的泛化2.仿函数3.迭代器3.1正向迭代器3.1.1++3.1.2--3.1.3*3.1.4->3.1.5!=完整版代码...

文章目录

前言
正文
- 1. 类型的泛化
- 2.仿函数
- 3.迭代器
- - 3.1正向迭代器
  - - 3.1.1 ++
    - 3.1.2 - -
    - 3.1.3 *
    - 3.1.4 ->
    - 3.1.5 !=
    - 完整版代码
- 4.[]（map）
框架
- 1.红黑树
- 2.set
- 3.map
总结

前言

在学习了红黑树之后，我们便可以尝试初步的在红黑树的基础上封装出map与set，好了，话不多说，进入今天的学习吧！

所需知识：

模板,主要为typename的特殊用法，模板参数，类模板。
迭代器与const迭代器
仿函数、反向迭代器
红黑树

正文

1. 类型的泛化

我们先分析map与set以及红黑树的模板参数。

map 存的是key——val，键值对。
set 存的是key。
红黑树存的是 key——val。

因此，为了适配set，红黑树里面存的是key，为了适配map红黑树存的是key——val, 如何实现呢？

那不如，设红黑树的存放的val是T类型，可以是key，也可以是key——val。

既然这样，我们就将原先的结点改为T类型的。

template<class T>
struct RBTreeNode
{

	typedef RBTreeNode<T> Node;
	RBTreeNode(const T& data)
		:_data(data)
		,_right(nullptr)
		,_left(nullptr)
		,_parent(nullptr)
		,_col(RED)
	{}

	Node* _right;
	Node* _left;
	Node* _parent;
	T _data;
	Color _col;
};

那既然这样，又会引出两个问题：

模板参数的Key还有用吗？
插入的数据类型也要变为T，如何进行比较？

先来解决第一个问题，Key有用吗？首先要明白Key是一个类型，在定义变量或者作为函数参数时要使用，很显然红黑树的查找的函数的参数类型是Key，因此有用，且不能舍弃。

2.仿函数

接着解决第二个问题，插入时既然T可以是key，也可以是pair<key,val> ,我们在找结点的位置的过程中，是通过key值进行查找的,因此又面临两种情况：

T是key时，结点中存的是key可以直接进行比较。
T是pair<key,val>,结点中存的是pair<key,val>直接比较，是无法得出正确结果的，我们看库里的实现即可清楚。

库里的实现涉及到第二参数，因此无法准确的得出正确结果，因此需要我们自己写一个仿函数，那因为map需要写，set也要适配红黑树，因此也需要写一个仿函数，返回key即可。

set实现：

template<class K>
struct SetOfT
{
	K operator()(const K& val)
	{
		return val;
	}
};

map实现:

template<class K, class V>
struct MapOfT
{
	const K operator()(const  pair<const K, V>& val)
	{
		return val.first;
	}
};

3.迭代器

3.1正向迭代器

根据之前的内容的学习，我们是封装出来一个通用的正向迭代器，通过模板参数控制其为const还是非const迭代器。

基本框架：

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

		__TreeIterator(Node* val)
			:_node(val)
		{}
		//此构造用于将非const迭代器转换为const迭代器，从而实现类型转换的功能。
		__TreeIterator(const iterator& val)
			:_node(val._node)
		{}
		//前置++
		self& operator++();
		//后置++
		self operator++(int);
		//后置--
		self operator--(int);
		//解引用
		Ref operator*();
		//箭头
		Ptr operator->();
		//不等于
		bool operator!=(const __TreeIterator& it);

		Node* _node;
	};

3.1.1 ++

由于三叉链的结构，父节点是很容易找到的，因此可以直接用循环写一个。

原理：中序遍历

开始节点树的最小节点。
根据中序遍历的过程遍历整棵树。

图解：
在这里插入图片描述

		self& operator++()
		{
			Node* cur = _node;
			assert(cur);
			if (cur->_right)
			{
				//如果右子树不为空，访问其右子树的最左结点。
				Node* MostLeft = cur->_right;
				while (MostLeft && MostLeft->_left)
				{
					MostLeft = MostLeft->_left;
				}
				_node = MostLeft;
			}
			else
			{
				//右子树为空，访问其祖先

				Node* parent = cur->_parent;

				//结点为其父节点的左边，访问父节点即可
				if (parent && parent->_left == cur)
				{
					_node = parent;
				}
				//结点为其父节点的右边，访问父亲的父亲
				else
				{
					while (parent && parent->_right == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}
			return *this;
		}

3.1.2 - -

与 ++同思路。

图解：
在这里插入图片描述
注意：当为空时，–我在这实现的是不可以的，但是库里面的是可以的，因为库里的结构是这样的。

在这里插入图片描述
库里的判断条件是这样的：当node为header时，node就转换其右边结点，也就是右树的最大结点。

说明一下：这样实现可能会导致增加了维护最大和最小节点的成本，每次插入和删除都得判断一下，不过也还好。

因此：这里我们只是实现正向的迭代器，反向的迭代器我们没有写，如果不采用库里的结构，我们也可以用友元+指针+前置类型声明的方式进行实现。

self& operator--()
{
	Node* cur = _node;
	if (cur->_left)
	{
		//访问最右结点
		Node* most_right = cur->_left;
		while (most_right && most_right->_right)
		{
			most_right = most_right->_right;
		}
		_node = most_right;
	}
	else
	{
		Node* parent = cur->_parent;
		if (parent->_right == cur)
		{
			//父节点右为cur，该访问父节点了。
			_node = parent;
		}
		else
		{
			//找到父亲作为cur的结点。
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
	}

	return *this;
}

3.1.3 *

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

3.1.4 ->

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

3.1.5 !=

bool operator!=(const __TreeIterator& it)
{
	return _node != it._node;
}

完整版代码

	template<class T,class Ref,class Ptr>
	struct __TreeIterator
	{

		typedef __TreeIterator<T, T&, T*> iterator;
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T,Ref,Ptr> self;

		__TreeIterator(Node* val)
			:_node(val)
		{}
		__TreeIterator(const iterator& val)
			:_node(val._node)
		{}

		//前置++
		self& operator++()
		{
			Node* cur = _node;
			assert(cur);
			if (cur->_right)
			{
				//如果右子树不为空，访问其右子树的最左结点。
				Node* MostLeft = cur->_right;
				while (MostLeft && MostLeft->_left)
				{
					MostLeft = MostLeft->_left;
				}
				_node = MostLeft;
			}
			else
			{
				//右子树为空，访问其祖先

				Node* parent = cur->_parent;

				//结点为其父节点的左边，访问父节点即可
				if (parent && parent->_left == cur)
				{
					_node = parent;
				}
				//结点为其父节点的右边，访问父亲的父亲
				else
				{
					while (parent && parent->_right == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}
			return *this;
		}

		self operator++(int)
		{
			 self tmp(_node);
			 ++(*this);
			 return tmp;
		}
		self& operator--()
		{
			Node* cur = _node;
			if (cur->_left)
			{
				//访问最右结点
				Node* most_right = cur->_left;
				while (most_right && most_right->_right)
				{
					most_right = most_right->_right;
				}
				_node = most_right;
			}
			else
			{
				Node* parent = cur->_parent;
				if (parent->_right == cur)
				{
					//父节点右为cur，该访问父节点了。
					_node = parent;
				}
				else
				{
					//找到父亲作为cur的结点。
					while (parent && parent->_left == cur)
					{
						cur = parent;
						parent = parent->_parent;
					}
					_node = parent;
				}
			}

			return *this;
		}
		self operator--(int)
		{
			self tmp(_node);
			(*this)++;
			return tmp;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(_node->_data);
		}
		bool operator!=(const __TreeIterator& it)
		{
			return _node != it._node;
		}
		Node* _node;
	};

4.[]（map）

我们要实现的insert接口为：
在这里插入图片描述

因此我们实现的红黑树的接口为：

pair<iterator,bool> insert(const T& val)
{
	//第一步：插入操作
	//如果根节点为空
	if (_root == nullptr)
	{
		_root = new Node(val);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}
	else
	{
		KeyOfT sel;//select里面的key
		Node* cur = _root, *parent = _root;
		while (cur)
		{
			if (sel(cur->_data) > sel(val))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (sel(cur->_data) < sel(val))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(val);
		if (sel(parent->_data) > sel(val))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		//变色逻辑略，重点在框架。
		return make_pair(iterator(newnode), true);
	}
}

map接口的实现为：

pair<iterator,bool> insert(const pair<K,V>& data)
{
	return _tree.insert(data);
}
mapped_type& operator[](const key_type& data)
{
	pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type()));
	return x.first->second;
}

set的接口为：

pair<iterator,bool> insert(const K& data)
{
	pair<typename rb_type::iterator, bool> k = _tree.insert(data);
	return pair<iterator,bool>(k.first,k.second);
}

补充小知识：迭代器转const迭代器

先强调：

const迭代器与非const迭代器是两种完全不同的自定义类型。
内置类型默认支持隐式类型转换，自定义类型需要有合适的构造函数才可实现隐式类型的转换，且explict可阻止隐式类型转换的发生。

因此：我们需要在模板内部写一个合适的构造函数，且其成员是公有的，才可实现自定义类型的转换。

框架

1.红黑树

运用封装知识的框架：

	template<class Key,class T,class KeyOfT>
	class RBTree
	{
	public:
		typedef RBTreeNode<T> Node;
		typedef __TreeIterator<T,T&,T*> iterator;
		typedef __TreeIterator<T, const T&, const T*> const_iterator;
		const_iterator begin()const
		{
			Node* mostleft = _root;
			while (mostleft && mostleft->_left)
			{
				mostleft = mostleft->_left;
			}
			return mostleft;
		}
		iterator begin()
		{
			Node* mostleft = _root;
			while (mostleft && mostleft->_left)
			{
				mostleft = mostleft->_left;
			}
			return mostleft;
		}
		const_iterator end()const
		{
			return nullptr;
		}
		iterator end()
		{
			return nullptr;
		}
		Node* find(const Key& key)
		{
			KeyOfT sel;
			Node* cur = _root;
			while (cur)
			{
				if (sel(cur->_data) > key)
				{
					cur = cur->_right;
				}
				else if (sel(cur->_data) < key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}
		pair<iterator,bool> insert(const T& val)
		{
			//第一步：插入操作
			//如果根节点为空
			if (_root == nullptr)
			{
				_root = new Node(val);
				_root->_col = BLACK;
				return make_pair(iterator(_root), true);
			}
			else
			{
				KeyOfT sel;
				Node* cur = _root, * parent = _root;
				while (cur)
				{
					if (sel(cur->_data) > sel(val))
					{
						parent = cur;
						cur = cur->_left;

					}
					else if (sel(cur->_data) < sel(val))
					{
						parent = cur;
						cur = cur->_right;

					}
					else
					{
						return make_pair(iterator(cur), false);
					}
				}
				cur = new Node(val);
				if (sel(parent->_data) > sel(val))
				{
					parent->_left = cur;
				}
				else
				{
					parent->_right = cur;
				}

				//根节点可能为红色,不管红色还是黑色都弄成黑色
				_root->_col = BLACK;
				return make_pair(iterator(newnode), true);
			}
		}
	private:

		Node* _root = nullptr;
	};
};

2.set

	template<class K>
	class set
	{
		template<class K>
		struct SetOfT
		{
			K operator()(const K& val)
			{
				return val;
			}
		};
		//typedef
		//类型
		typedef K key_type;
		typedef K val_type;
		typedef SetOfT<K> set_of_key;
		typedef RBTree<key_type, val_type, set_of_key> rb_type;
		typedef K key_type;
		typedef K val_type;
		typedef SetOfT<K> set_of_key;
		typedef RBTree<key_type, val_type, set_of_key> rb_type;
		//typename的作用：声明其为类型。
		typedef typename rb_type::Node Node;
	public:
		//迭代器
		typedef typename rb_type::const_iterator const_iterator;
		//不管是普通还是const迭代器set的key值都不可被修改。
		typedef const_iterator iterator;
		const_iterator begin() const
		{
			return _tree.begin();
		}
		const_iterator end() const
		{
			return _tree.end();
		}
	public:
		Node* find(const K& key)
		{
			return _tree.find(key);
		}
		pair<iterator,bool> insert(const K& data)
		{
			pair<typename rb_type::iterator, bool> k = _tree.insert(data);
			//这里涉及到普通迭代器转换成const迭代器。
			return pair<iterator,bool>(k.first,k.second);
		}
	private:
		rb_type _tree;
	};

3.map

template<class K,class V>
class map
{
	//类型
	typedef K key_type;
	typedef pair<const K, V> val_type;
	template<class K, class V>
	struct MapOfT
	{
		const K operator()(const  pair<const K, V>& val)
		{
			return val.first;
		}
	};
	typedef MapOfT<K, V> map_of_key;
	typedef RBTree<key_type, val_type, map_of_key> rb_type;
public:
	
	typedef typename rb_type::Node Node;
	//迭代器
	typedef typename rb_type::iterator iterator;
	typedef typename rb_type::const_iterator const_iterator;
	typedef V mapped_type;
	iterator begin()
	{
		return _tree.begin();
	}
	const_iterator begin()const
	{
		return _tree.begin();
	}
	iterator end()
	{
		return _tree.end();
	}
	const_iterator end()const
	{
		return _tree.end();
	}
	bool find(const K& key)
	{
		return _tree.find(key);
	}
	pair<iterator,bool> insert(const pair<K,V>& data)
	{
		return _tree.insert(data);
	}
	mapped_type& operator[](const key_type& data)
	{
		pair<iterator, bool> x = _tree.insert(val_type(data,mapped_type()));
		return x.first->second;
	}

private:

	rb_type _tree;
};

总结

模板，迭代器，仿函数，分开起来，或许不难，但是合起来，还是有点难度的，毕竟封装也是套娃，也挺麻烦的，尤其是模板的一大缺陷，增加了编译器识别问题的难度。

如果有所帮助，不妨点个赞鼓励一下吧！

上一篇：【小程序开发】uniapp引入iconfont图标及使用方式
下一篇：JAVA -华为真题-分奖金