前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【C++进阶】map与set的封装实践

【C++进阶】map与set的封装实践

作者头像
用户11305458
发布2024-10-09 17:25:19
720
发布2024-10-09 17:25:19
举报
文章被收录于专栏:学习

map和set

通过观察stl的底层我们可以看见,map和set是通过红黑树实现的。

通过观察这些typedef就可以看到,map和set的封装基本都是套用的红黑树的迭代器来封装实现的,所以我们的map和set也可以通过完成的红黑树来进行封装。

map

map的框架

通过看stl的框架,我们可以看到set实际传递了两个key,但是两个key的重命名是不一样的,map也传递了两个key,第一个key是key,第二个key是pair,所以这里我们在搭建框架的时候,我们可以根据stl的底层的框架进行搭建。

代码语言:javascript
复制
namespace lyrics
{
	template<class K,class V>
	class map
	{
	public:
	
	private:
		RBTree<K, pair<const K, V>> _t;
	};
}

根据stl的源代码,map的框架可以简化为上面这种。 为什么要传递第一个参数呢?

因为虽然只传递一个参数,对于set来说没什么影响,但是如果我们想用一个红黑树来封装两个容器的话,这其实是有影响的,因为在比较的时候,set确实不会有影响,但是map在比较的时候,比较逻辑是通过k来比较而并非通过pair来比较,还有就是查找的话,查找set也可以通过一个模版参数来办到,但是对于map来说,查找也是通过pair的first来查找的,所以这里我们应该传递两个参数,第一个参数用于查找和比较,第二个参数用于插入。

迭代器

代码语言:javascript
复制
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T,Ref,Ptr> Self;//迭代器
	Node* _node;
	Node* _root;
	RBTreeIterator(Node* node, Node* root) :_node(node), _root(root) {}
};

先创建一个迭代器类,由于这里我们取不到原本红黑树中的root所以我们这里初始化的时候多传递一个参数,在这个迭代器类中多了一个参数root就是用来取原本红黑树中的root的。

operator++()
代码语言:javascript
复制
Self& operator++()
{
	//要找到当前节点的右子树的最左节点,因为遍历到当前节点说明左子树已经走完了
	if (_node->_right)
	{
		Node* leftMost = _node->_right;
		while (leftMost->_left)
			leftMost = leftMost->_left;
		_node = leftMost;
	}
	//右为空,代表这棵树已经访问完了,所以应该找到父亲,因为当前节点是父亲的左子树
	//所以左 中 右
	//下一个访问的节点应该是访问祖先
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

我们可以通过上面的红黑树来观察,假设当前遍历到的节点就是13,由于红黑树的遍历是中序遍历,所以可是知道,当前左子树已经遍历完了,所以所以下一个节点只看能在右子树,++求的是下一个节点,肯定是求右子树最小的节点,所以就是当前节点的右子树的最左节点。

如果右子树为空,我们来看看这种情况假设我们当前节点是66,右子树是空的节点,再假设,当前节点是父亲的右子树,如果当前节点是父亲的右子树,那么说明当前节点连带父亲的左子树和右子树都已经访问完了,所以应该向上进行遍历,将当前节点移动到父亲的位置,继续向上遍历,当当前节点是父亲的左子树的节点的时候就不需要在遍历了,因为遍历顺序是左中右,所以左的下一个节点就是右就是当前的父亲节点

operator–()
代码语言:javascript
复制
Self& operator--()
{
	//_node是空,代表是end
	if (_node == nullptr)
	{
		//end--,则取的就是最右节点,也就是整棵树的最大节点
		Node* rightMost = _root;
		//找到左子树的最右节点
		while (rightMost && rightMost->_right)
			rightMost = rightMost->_right;
		_node = rightMost;
	}
	//--是左子树的最右节点
	else if (_node->_left)
	{
		Node* rightMost = _node->_left;
		//找到左子树的最右节点
		while (rightMost->_right) 
			rightMost = rightMost->_right;
		_node = rightMost;
	}
	//如果左为空
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		//因为是反过来的,所以是右根左
		while (parent && parent->_left == cur)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

–的操作其实是和++相似的,但是需要注意的是:

–的顺序是右中左,而不是左中右,如果是右中左的话,我们假设当前节点是13,那么–的话上一个节点就是11,–应该是求的是比当前节点小的最大的一个节点,所以比当前节点小,所以应该是当前节点的左子树,又是最大的,所以应该是当前节点的左子树的最右的节点。

但是有可能左子树是空树,所以我们我们拿上面的那个红黑树的图来举例,当节点是22的时候,可以看见左子树是空的,所以所以这时候应该去找父节点,如果当前节点是父节点的左节点,那么继续向上找,因为是左节点,由于是右中左,所以左节点访问完之后,连同当前节点的父节点和右子树的节点已经访问完了,所以应该将当前节点遍历到父节点继续向上找,如果当前节点是父节点的右节点的话,那么就可以停下来不用找了,因为遍历的顺序是右中左,当前节点是父节点的右节点,说明下一个节点是父节点,所以不用找了,直接返回父节点就可以了。

==注意:这里有一个特殊情况,当节点是end()的时候,需要特殊处理,因为对于第一段逻辑来说,我们需要去访问node的left,这里我们访问空指针的成员已经报错了,所以这里要对空指针进行特殊处理:

这里就体现出来我们在初始化迭代器的时候传递root的重要性了,这里空指针的情况,我们直接取最右节点,也就是整棵树最大的节点。

operator==()和operator!=()
代码语言:javascript
复制
//!=
bool operator!=(const Self& s) const
{
	return _node != s._node;//迭代器比较就是两个指针相不相等
}
//==
bool operator==(const Self& s) const
{
	return _node == s._node;
}
operator*()
代码语言:javascript
复制
//返回节点中的data
Ref operator*()
{
	return _node->_data;//data是T&
}
operator->()
代码语言:javascript
复制
//pair的迭代器可以访问first和second
Ptr operator->()
{
	return &(_node->_data);
}

insert

我们先看看之前的insert的代码:

首先可以看见的是我们之前的红黑树是写的比较死的,适用的范围很小,为了,让其更模版话,我们可以将实际需要插入的类型用一个模版类型T来表示。

修改之后可以看见,这种形式,在传参的时候只需要根据是map或者是set来看传递pair还是传递K。

但是我们接着来看红黑树的代码,可以发现,我们之前写的比较逻辑都是通过pair的比较逻辑去比较的,这里就涉及到一个问题,我们现在的data换成T了,所以之前比较的逻辑就不符合语法了。

可以看看之前的部分的比较逻辑,上面的比较逻辑是基于值是pair的时候成立的,但是现在我们需要的是能适用于map和set的两个容器的比较,所以这里我们必须进行修改,最好的办法就是我们需要传递一个类仿函数,我们将他以模版参数的形式传递,在map和set中写一个类仿函数,然后分别传递到红黑树中,这里就多出来了第三个模版参数。

代码语言:javascript
复制
namespace lyrics
{
	template<class K,class V>
	class map
	{
	public:
	
	private:
		RBTree<K, pair<const K, V>,MapKeyOfT> _t;
	};
}

这里第三个参数传递的是一个类仿函数,所以这里我们先写一个仿函数,这里我们写的目的就是要得到map中的pair的first。

代码语言:javascript
复制
struct MapKeyOfT
{
	const K& operator()(const pair < K, V>& kv)
	{
		return kv.first;
	}
};

这样我们就可以取到map中pair的第一个了。 接下来比较就方便多了,我们只需要创建一个对象即可,然后调用operator()()即可,接下来我们尝试改写一个insert的逻辑

将下面的代码的比较逻辑用这种方式进行修改之后的insert就适用于map和set了,但是在我们查看官方文档之后可以看到官方文档中的insert的返回值是pair<iterator,bool>,所以这里我们也应该修改成和官方文档相同的返回值,这样有利于我们后面封装operator[] (),所以改完之后整体就是下面的:

代码语言:javascript
复制
pair<Iterator,bool> Insert(const T& data)
{
	//根节点是空时,判断一下
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(Iterator(_root,_root), true);
	}
	//遍历节点,找到插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	KeyOfT kot;
	while (cur)
	{
		//比当前节点大小就去左子树
		if (kot(cur->_data) > kot(data))//这里调用operator()
		{
			parent = cur;
			cur = cur->_left;
		}
		//比当前节点大就去右子树
		else if (kot(cur->_data) < kot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		//插入失败返回false
		else return make_pair(Iterator(cur, _root), 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;
	//父亲是红色继续向上改变颜色
	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (grandparent->_left == parent)
		{
			Node* uncle = grandparent->_right;
			//叔叔存在为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				//改变指向
				cur = grandparent;
				parent = cur->_parent;
			}
			//叔叔不存在或者叔叔存在且为黑
			else
			{
				//单旋加变色
				if (cur == parent->_left)
				{
					RotateR(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				//双旋
				else
				{
					//双旋
					RotateL(parent);
					RotateR(grandparent);
					//双旋之后cur和parent是交换了,所以cur充当根
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
				//第一个节点是黑色节点,所以可以直接结束
				break;
			}
		}
		else
		{
			Node* uncle = grandparent->_left;
			//叔叔存在为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;
				//改变指向,向上更新
				cur = grandparent;
				parent = cur->_parent;
			}
			//叔叔不存在或者叔叔存在且为黑
			else
			{
				//单旋加变色
				if (cur == parent->_right)
				{
					RotateL(grandparent);
					parent->_col = BLACK;
					grandparent->_col = RED;
				}
				//双旋
				else
				{
					//双旋
					RotateR(parent);
					RotateL(grandparent);
					//双旋之后cur和parent是交换了,所以cur充当根
					cur->_col = BLACK;
					grandparent->_col = RED;
				}
				//第一个节点是黑色节点,所以可以直接结束
				break;
			}
		}
	}
	//暴力处理根节点的颜色
	_root->_col = BLACK;
	//父亲的颜色是黑色直接结束
	return make_pair(Iterator(newnode, _root), true);
}

map的insert:

代码语言:javascript
复制
pair<iterator,bool> Insert(const pair<K, V>& kv)
{
	return _t.Insert(kv);
}

begin()

代码语言:javascript
复制
Iterator Begin()
{
	Node* leftSub = _root;
	//最左节点就是第一个
	while (leftSub && leftSub->_left != nullptr)//找到最左节点
		leftSub = leftSub->_left;
	return Iterator(leftSub, _root);//用最左节点构造一个begin
}
ConstIterator Begin() const
{
	Node* leftSub = _root;
	//最左节点就是第一个
	while (leftSub && leftSub->_left != nullptr)//找到最左节点
		leftSub = leftSub->_left;
	return ConstIterator(leftSub, _root);//用最左节点构造一个begin
}

begin需要封装两个一个是const的begin一个是非const的迭代器。 begin很简单,begin就是取到最小的,如果当前节点不是nullptr直接访问这棵树的最左节点返回最左节点即可。 对map封装:

代码语言:javascript
复制
iterator begin()
{
	return _t.Begin();
}
const_iterator begin()const
{
	return _t.Begin();
}

end()

代码语言:javascript
复制
//用空代表end
ConstIterator End()const 
{
	return ConstIterator(nullptr, _root);//引用nullptr构造一个迭代器
}
Iterator End()
{
	return Iterator(nullptr, _root);//引用nullptr构造一个迭代器
}

end()我们可以直接返回nullptr。

对map进行封装:

代码语言:javascript
复制
iterator end()
{
	return _t.End();
}
const_iterator end()const
{
	return _t.End();
}

operator[] ()

这个我们查看官方文档可以看见:

这个operator[] ()是用insert来封装的,所以我们接下来不管三七二十一先取出来当前key对应的值

代码语言:javascript
复制
V& operator[](const K& key)
{
	pair<iterator, bool> ret = Insert(make_pair(key, V()));//这里第二个参数给缺省值,有可能插入成功,有可能插入失败
	return ret.first->second;
}

map的所有代码:

代码语言:javascript
复制
namespace lyrics
{
	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, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
		//这里底层取的是const key
		//这里取const,上层就不能修改,set也可以用两个const迭代器

		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>& kv)
		{
			return _t.Insert(kv);
		}
		iterator find(const K& key)
		{
			return _t.Find();
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = Insert(make_pair(key, V()));//这里第二个参数给缺省值,有可能插入成功,有可能插入失败
			return ret.first->second;
		}
		
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}

set的封装

set的封装和map的如出一辙,甚至比map的简单

代码语言:javascript
复制
namespace lyrics
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//因为类模版没有被实例化,所以没有被实例化
		//加上typename就表示等实例化之后去里面将其替换掉
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		//第二个K是给给底层的data用的,所以data不能修改,所以只用给第二个模版参数加上const就可以了
		typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
		iterator begin()
		{
			return _t.Begin();//调用RBTree的begin,只是套一层壳子而已
		}
		const_iterator begin()const
		{
			return _t.Begin();//调用RBTree的begin,只是套一层壳子而已
		}
		iterator end()
		{
			return _t.End();
		}
		const_iterator end()const
		{
			return _t.End();
		}
		pair<iterator,bool> Insert(const K& key)
		{
			return _t.Insert(key);
		}
		iterator find(const K& key)
		{
			return _t.Find(key);
		}
	private:
		RBTree<K, const K, SetKeyOfT> _t;
	};
}

迭代器的封装

代码语言:javascript
复制
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T,Ref,Ptr> Self;//迭代器
	Node* _node;
	Node* _root;
	//返回节点中的data
	Ref operator*()
	{
		return _node->_data;//data是T&
	}
	//pair的迭代器可以访问first和second
	Ptr operator->()
	{
		return &(_node->_data);
	}
	//构造函数,通过节点的指针进行构造
	RBTreeIterator(Node* node, Node* root) :_node(node), _root(root) {}
	//!=
	bool operator!=(const Self& s) const
	{
		return _node != s._node;//迭代器比较就是两个指针相不相等
	}
	//==
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
	//前置++
	Self& operator++()
	{
		//要找到当前节点的右子树的最左节点,因为遍历到当前节点说明左子树已经走完了
		if (_node->_right)
		{
			Node* leftMost = _node->_right;
			while (leftMost->_left)
				leftMost = leftMost->_left;
			_node = leftMost;
		}
		//右为空,代表这棵树已经访问完了,所以应该找到父亲,因为当前节点是父亲的左子树
		//所以左 中 右
		//下一个访问的节点应该是访问祖先
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self& operator--()
	{
		//_node是空,代表是end
		if (_node == nullptr)
		{
			//end--,则取的就是最右节点,也就是整棵树的最大节点
			Node* rightMost = _root;
			//找到左子树的最右节点
			while (rightMost && rightMost->_right)
				rightMost = rightMost->_right;
			_node = rightMost;
		}
		//--是左子树的最右节点
		else if (_node->_left)
		{
			Node* rightMost = _node->_left;
			//找到左子树的最右节点
			while (rightMost->_right) 
				rightMost = rightMost->_right;
			_node = rightMost;
		}
		//如果左为空
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			//因为是反过来的,所以是右根左
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

总结

通过对 map 和 set 的封装,我们可以简化代码的使用方式,增强数据操作的安全性和可维护性,同时根据具体需求扩展功能。这不仅提高了代码的可读性和复用性,还在多线程环境下提供了更好的保障。尽管封装需要额外的设计和实现工作,但它带来的长远收益是显而易见的。未来,我们可以进一步探索封装的优化方向,如支持更多类型的容器或集成其他数据结构,以适应更复杂的应用场景。在实际项目中,合理地利用封装技术,将使我们的C++开发工作更加高效和灵活。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-10-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • map和set
  • map
    • map的框架
      • 迭代器
        • operator++()
        • operator–()
        • operator==()和operator!=()
        • operator*()
        • operator->()
      • insert
        • begin()
          • end()
            • operator[] ()
              • map的所有代码:
              • set的封装
              • 迭代器的封装
              • 总结
              相关产品与服务
              容器服务
              腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档