【c++】set和map的封装

郭小明

13人浏览 · 2026-05-14 02:27:38

郭小明 · 2026-05-14 02:27:38 发布

一、框架搭建（如何实现红黑树的复用？）

set和map的底层都是红黑树，但由于存储元素的差异（一个只存储key，一个既存储key又存储value），我们要么创造出两棵稍微不一样的红黑树，或者是改变红黑树的结构，使其能完美匹配上set和map。库里面采用了后者。

1. 分析库里set与map的实现（分析RBTree的两个模板参数 Key, Value）

库里面RBTree的实现一共有5个模板参数，分别是 Key，Value，KeyOfValue，Compare和Alloc，我们主要分析前三个模板参数的作用）。Compare是控制比较规则的仿函数类型，Alloc是内存池。

在这里插入图片描述

对于set，它只有一个用来接收key类型的模板参数Key，并把Key同一个类型命名为key_type与value_type。
对于map，它有两个分别用来接收key和 value类型的模板参数Key和T。将Key重命名为key_type，将pair<const Key, T> 重命名为value_type。
它们复用同一棵红黑树，将4个类型传给红黑树。

在这里插入图片描述

重点观察Value这个模板参数，它的类型是节点所存储的元素的类型。set传过来的是Key类型，map传过来的是pair<const Key, T>类型。利用模板来控制红黑树所存储的类型，满足set和map不同的存储需求。

在这里插入图片描述

我们传递给map的只是key和value的类型，而map要存储的是pair<const key, value>类型（实现key和value的绑定，const实现不可修改以后再加），所以我们需要做一个加工。
既然有了接收存储元素类型的Value类型，而为什么不删除第一个用来单独存储key类型的模板参数Key，似乎用不上它，这个以后就能知道了。

2. 分析第三个模板参数KeyofValue

我们在进行插入时，需要根据key的大小来找到插入的位置，而由于set和map存储类型的不同，set直接用Value（key）类型的元素就好，而map则需要取出Value(pair<const key, value>)里面的key值来找到插入的位置。

在这里插入图片描述

而KeyOfValue这个模板参数就是用来接收功能为取出key的仿函数类型，KeyOfValue是匿名对象。可以参照库里的实现大胆猜测。

在这里插入图片描述

set里面传给KeyOfValue的是一个ideneity<value_type>类型的仿函数，identity在这里是本身的意思，它的功能就是取出key值就是value_type类型的元素它本身，而map里面传给KeyOfValue的是一个select1st<value_type>类型的仿函数，它的功能就是取出key值就是value_type类型元素里的第一个值。

在这里插入图片描述

所以我们在set和map里面的实现里面都要实现一个仿函数用来传递给KeyOfValue。

set：

代码语言：javascript

AI代码解释

namespace mosheng {
	template<class K>
	class identity
	{
	public:
		K& operator()(const K& key)
		{
			return key;
		}
	};
	template<class Key>
	class set
	{
		typedef RBTree<Key, Key, identity<Key>> rbType;
	};
}

map:

代码语言：javascript

AI代码解释

namespace mosheng {
	template<class K, class KV>
	class select1st
	{
	public:
		K& operator()(const KV& kv)
		{
			return kv.first;
		}
	};
	template<class Key, class Value>
	class map
	{
		typedef RBTree<Key, std::pair<Key, Value>, select1st<Key, std::pair<Key, Value>> rbType;
	};
}

不要忘了对应的红黑树的修改，主要是修改insert和find还有对应的模板参数，去用KeyOfValue提取key。然后框架搭建完毕。

代码语言：javascript

AI代码解释

#pragma once

enum Colour
{
	RED,
	BLACK
};

template<class Value>
struct RBTreeNode
{
	RBTreeNode(Value& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{
	};
	Value _kv;
	RBTreeNode<Value>* _left;
	RBTreeNode<Value>* _right;
	RBTreeNode<Value>* _parent;
	Colour _col = RED;
};

template<class Key, class Value, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<Value> Node;
public:
	bool Insert(Value& kv)
	{
		//处理空树的情况
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//找到要插入的位置
		else
		{
			Node* cur = _root;
			Node* parent = nullptr;

			while (cur)
			{
				if (KeyOfValue()(kv) < KeyOfValue()(cur->_kv))
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (KeyOfValue()(kv) > KeyOfValue()(cur->_kv))
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}
			//插入新节点
			cur = new Node(kv);
			if (KeyOfValue()(parent->_kv) > KeyOfValue()(kv))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;
			//父节点为红色的情况下需要进行处理
			if (parent->_col == RED)
			{
				while (parent && parent->_col == RED)
				{
					//记录节点
					Node* grandfather = parent->_parent;
					Node* uncle = nullptr;
					if (grandfather->_left == parent)
					{
						uncle = grandfather->_right;
					}
					else
					{
						uncle = grandfather->_left;
					}
					//uncle为红色的情况
					//仅变色
					if (uncle && uncle->_col == RED)
					{
						uncle->_col = parent->_col = BLACK;
						grandfather->_col = RED;
						//更新
						cur = grandfather;
						parent = cur->_parent;
					}
					//uncle为黑色或为空的情况
					else
					{
						//右旋转
						if (grandfather->_left == parent && parent->_left == cur)
						{
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;

							break;
						}
						//左旋转
						else if (grandfather->_right == parent && parent->_right == cur)
						{
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;

							break;
						}//左右双旋
						else if (grandfather->_left == parent && parent->_right == cur)
						{
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

							break;
						}
						//右左双旋
						else
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;

							break;
						}
					}
				}
			}

		}
		//处理根节点颜色

		_root->_col = BLACK;

		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	
	Node* Find(const Key& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (KeyOfValue()(cur->_kv) < key)
			{
				cur = cur->_right;
			}
			else if (KeyOfValue()(cur->_kv) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	Node* _root = nullptr;
};

可以使用匿名对象，但推荐构造一个对象kof来使用仿函数KefOfValue。
为什么保留第一个Key的模板参数在find函数上就有所体现：我们需要Key的类型，因为要根据Key的类型来寻找。KefOfValue无法提取出类型。

二、迭代器的实现

迭代器的实现也就是在节点指针的基础之上做封装操作，并重载一些运算符。map和set的迭代器是双向迭代器，关键是需要实现++和–的重载。

1. 普通迭代器iterator的实现

1.1 先搭一个基本框架

代码语言：javascript

AI代码解释

template<class Value>
class TreeIterator
{
	typedef RBTreeNode<Value> Node;
	typedef TreeIterator<Value> Self;
public:
	TreeIterator(Node* node)
		:_node(node)
	{}

	Value& operator* ()
	{
		return _node->_kv;
	}

	Value* operator->()
	{
		return &(_node->_kv);
	}

	bool operator==(const Self& s)const
	{
		return _node == s->_node;
	}

	bool operator!=(const Self& s)const
	{
		return _node != s->_node;
	}
private:
	Node* _node;
};

1.2 operator++与operator- -实现

operator++

我们希望达成的效果是++从当前节点移动到下一个按照中序遍历的节点。- -则是反过来。++只需要知道当前节点的下一个节点是哪一个。

在这里插入图片描述

现在我们有一棵红黑树，若当前节点为18，那么我们希望节点18++后的节点是节点25，节点25++后的节点是节点30，以此类推。
首先看节点10，它不是叶子节点，++后需要跳到节点15，也就是它的右节点，这是因为它的右子树不为空，按照中序遍历顺序，可以认为它的左子树是遍历完成的，只需要看它的右子树就行。所以首先要判断当前节点的右子树是否为空。再来看节点30，++后需要跳到节点35，是其右子树的最左节点。若不为空就会跳到节点30的左孩子节点40，节点40的左子树是还未访问过的，所以需要访问它的左子树，一直到最左端。