【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的底层的框架进行搭建。

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来查找的，所以这里我们应该传递两个参数，第一个参数用于查找和比较，第二个参数用于插入。

迭代器

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++()

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–()

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!=()

//！=
bool operator!=(const Self& s) const
{
	return _node != s._node;//迭代器比较就是两个指针相不相等
}
//==
bool operator==(const Self& s) const
{
	return _node == s._node;
}

operator*()

//返回节点中的data
Ref operator*()
{
	return _node->_data;//data是T&
}

operator->()

//pair的迭代器可以访问first和second
Ptr operator->()
{
	return &(_node->_data);
}

insert

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

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

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

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

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

namespace lyrics
{
	template<class K,class V>
	class map
	{
	public:
	
	private:
		RBTree<K, pair<const K, V>，MapKeyOfT> _t;
	};
}

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

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[] ()，所以改完之后整体就是下面的：

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：

pair<iterator,bool> Insert(const pair<K, V>& kv)
{
	return _t.Insert(kv);
}

begin()

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封装：

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

end()

//用空代表end
ConstIterator End()const 
{
	return ConstIterator(nullptr, _root);//引用nullptr构造一个迭代器
}
Iterator End()
{
	return Iterator(nullptr, _root);//引用nullptr构造一个迭代器
}

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

对map进行封装：

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

operator[] ()

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

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

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

map的所有代码：

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的简单

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;
	};
}

迭代器的封装

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 删除

实践