您现在的位置是:首页 >技术交流 >【C++】用红黑树迭代器封装map和set网站首页技术交流

【C++】用红黑树迭代器封装map和set

朵猫猫. 2024-06-19 00:01:02
简介【C++】用红黑树迭代器封装map和set

封装有点难 - . -

文章目录


前言

因为我们要将红黑树封装让map和set使用,所以我们要在原来的基础上将红黑树代码进行修改,最主要的是修改模板参数,下面我们直接进入正题:


一、红黑树原先代码的修改

首先我们拿出STL中的源代码,看看大佬是如何进行封装的:

我们可以看到在STL中map的模板参数是Key和T,这没毛病很显然是KV结构,那么底层红黑树key_type和value_type是什么?其中Key是KeyType的别名,value是pair的别名,也就是说map有两个模板参数一个是key,一个是为pair的value,这个pair大家要记住也是一个键值对。那么这到底是怎么回事呢?别急,我们再看看set的实现然后给出答案:

 我们可以看到,set整体的模板参数还是Key,但是在底层红黑树的参数变成了key_type和value_type,而这两个参数都是同一个Key重命名而来的,也就是说set的底层用红黑树是两个Key做模板参数,到这其实我们应该是明白了,真正在红黑树中存储的是key还是kv结构是由第二个模板参数Value_type来决定的,因为map中的value_type是pair,set中的value_type是key.那么第一个参数key有什么用呢?为什么要多传这一个参数呢?因为在我们用find查找以及erase删除接口的时候,我们都是用的key值啊,举个例子,map中的find接口要查找不能用pair直接查找吧,我们是用的pair中的first来进行查找,但是由于set是key可以直接使用,pair要拿到first才能查找,所以干脆就多传一个参数,这个参数就是我们查找呀什么的那些接口所需要的类型,下面是红黑树的源码:

 我们可以看到红黑树的节点确实通过一个模板参数来控制,然后红黑树中两个模板参数,源码中实现了一个头结点和记录节点的多少,我们没有实现所以不用管这个,了解了以上知识我们就可以将之前的红黑树代码先修改一下:

template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	T _data;
	Colour _col;
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{

	}
};

 首先将红黑树节点修改完毕,我们将原来的pair变成一个data类型,这个类型在set中是key,在map中是pair。

template <class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:

bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点必须为黑色
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (parent->_data < data)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//开始红黑树
        //...........省略
}

上面是我们将红黑树进行了修改,因为我们将红黑树的节点模板参数设为T,所以我们在红黑树中需要修改一下将第二个参数设置为T,然后insert函数也需要改变,因为我们直接插入的是一个pair值,但是很明显这样是解决不了set的问题的,所以我们插入的是一个T类型的data,这个T类型的data就是红黑树节点中存储的值,将这些修改完毕后我们就可以实现map和set了,下面我们先实现set:

namespace sxy
{
	template <class K>
	class set
	{

	public:

		bool insert(const K& key)
		{
			return _t.insert(key);
		}
	private:
		RBTree<K, K> _t;
	};
	void test_set()
	{
		set<int> s;
		s.insert(1);
		s.insert(2);
		s.insert(3);
		/*set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}*/
	}
}

如我们之前所讲,set只需要一个参数key,但是在底层红黑树中是需要传两个K的,然后用红黑树的插入接口等即可,下面我们先演示一下:

 展开后2的左边是1右边是3,下面我们在简单实现一下map的:

namespace sxy
{
	template<class K, class V>
	class map
	{

	public:
		bool insert(const pair<const K, V>& kv)
		{
			return _t.insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>> _t;
	};
	void test_map()
	{
		map<int, int> mp;
		mp.insert(make_pair(1, 1));
		mp.insert(make_pair(2, 2));
		mp.insert(make_pair(3, 3));
	}
}

在map中我们需要的是KV结构,然后再调用底层红黑树的时候第一个参数为K,第二个参数为pair类型,pair的first加上const是因为map中的first不允许修改,但是second可以修改。同样我们跑起来演示一下:

 可以看到2的左边是1,1,右边是3,3.下面我们总结一下,map和set在用底层红黑树的时候set会多用一个模板参数,理由是:

1.第一个参数拿到单独K的类型,因为find,erase这些接口函数的参数是K。

2.第二个模板参数决定了树的节点里面存什么。。 K or KV

测试完毕后我们讲解源码中红黑树的第三个模板参数KeyOfT,这个参数实际上就是一个仿函数,通过一个仿函数将pair中的first拿到或者直接拿到set中的key。

template <class K>
	class set
	{
		//仿函数
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:

		bool insert(const K& key)
		{
			return _t.insert(key);
		}
	private:
		RBTree<K, K> _t;
	};

可以看到set中的仿函数就是直接返回key。

template<class K, class V>
	class map
	{
		//仿函数
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool insert(const pair<const K, V>& kv)
		{
			return _t.insert(kv);
		}
	private:
		RBTree<K, pair<const K, V>> _t;
	};

map中的仿函数需要返回pair中的first,下面我们将红黑树的模板参数加入KeyOfT:

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	bool insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点必须为黑色
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

可以看到我们在insert函数中加入了kot这个仿函数,这个仿函数重载了()符号,所以我们用kot(cur->data)就拿到了set中的key或者map中的pair.first,对了,前面我们没加仿函数但是程序可以运行的原因是:pair是有自己的比较方法的,也是通过仿函数实现的,当first不相等就用first比较,当first相等就用second比较,但是这不是我们想要的,我们想要的只是通过first比较,所以我们用仿函数来控制确定只拿出first。因为加入了一个模板参数所以map和set肯定是需要修改的:

 将这里的仿函数加入后我们就正式将红黑树部分搞定了,下面画张图让大家理解一下set和map如何调用红黑树的:

 下面就开始实现迭代器了。

二、红黑树迭代器的实现

迭代器的实现同样我们参考源码:

 我们可以看到源码中对于普通迭代器和const迭代器都用了const迭代器,这也就证明了为什么我们在使用map和set的时候不可以用迭代器修改其Key值,rep_type是红黑树的迭代器,也就是说map和set都用的红黑树内部的迭代器,当我们要使用模板类的使用要用typename否则编译器会报错以为没有实现迭代器,加了typename就会等模板实例化后。

 我们可以看到,红黑树的迭代器在源码中typedef了很多,下面我们就实现一下:

因为红黑树每一个都是节点,所以我们的迭代器实现和list的迭代器一样,底层用一个节点就解决了:

template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{

	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	Self& operator++()
	{
		//....
	}
};

这里的Ref就是T&,Ptr就是T*,这里的玩法我们在list的迭代器就玩过了,这样可以让模板生成普通迭代器和const迭代器,如果调用者传的const T&,const T*那么就是const迭代器。然后迭代器的构造就是通过一个节点来构造,*(解引用)就是返回节点的data值的引用,->如果是pair类型本来需要两次->才能访问到pair的first但是我们重载后一个->就能访问到节点中的data,并且我们返回的是T*,引用的本质也是指针所以直接返回引用。下面我们就实现迭代器中的++:

首先我们要知道,红黑树的迭代器的begin位置是在中序遍历的第一个位置(因为中序才能排序),所以我们直接看下图:

 对于下面这张图我们的it就是迭代器,在中序的第一个位置,++后我们要访问6这个位置,这个位置有什么要求呢?首先如果1这个节点有右子树并且6有左子树还需要依次往6这个节点的左子树走(因为中序遍历:左子树,根,右子树),如果1这个节点没有右子树那么++后的节点是8所以我们要判断的就是是否有右子树,如果有就访问右子树的最左节点,如果没有就要回溯,回溯也并不简单我们用代码来演示:

Self& operator++()
	{
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

我们直接说else语句中的代码,当发现右边为空时那就说明该向上回溯了,而我们通过图可以看到:当迭代器在6这个位置,正好6的右子树为空,++只能向上走,向上的时候1是parent是存在的并且1的右子树是cur,所以向上继续找parent变成8cur变成1,这个时候不满足8的右边是cur,所以这个时候parent的节点就是++后的节点,找到后返回*this(*this就是++后的迭代器).下面我们将迭代器放到红黑树中:

template <class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> iterator;
public:
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator end()
	{
		return iterator(nullptr);
	}

begin我们已经说过是中序的第一个节点,拿到中序第一个节点后直接返回用这个节点构造的迭代器即可。end我们直接返回由空指针构造的迭代器即可,因为end必须是最后一个节点的后一个位置,而最后一个节点的后一个位置本来也是空。(这里源代码中是增加一个高于根节点的头结点,让end最后指向头结点,但是我们的nullptr也可以完成任务只不过不能从end--回到上一个节点(因为end为空)),而源代码是可以让end--在返回上一个节点的)接下来我们将迭代器放到set中看一下:

template <class K>
	class set
	{
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;
	};

这里我们先用的普通迭代器,因为const迭代器还有一个很难理解的问题需要我们详细讲解。因为这里用了红黑树的迭代器,所以红黑树中我们对于迭代器的typedef都放在public中,否则会有权限的问题:

 可以看到我们的迭代器没毛病,下面我们再用一下map:

template<class K, class V>
	class map
	{
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
	void test_map()
	{
		map<int, int> mp;
		mp.insert(make_pair(1, 1));
		mp.insert(make_pair(2, 2));
		mp.insert(make_pair(3, 3));
		for (auto& e : mp)
		{
			cout << e.first << ":" << e.second << endl;
		}
		cout << "-------------------------------- -" << endl;
		map<int, int>::iterator it = mp.begin();
		while (it != mp.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
	}

 可以看到我们的迭代器用于set和map都没问题,然后刚刚我们没有实现迭代器--现在实现一下:

--直接就是++的相反,比如++是左中右遍历,那么--就是右中左遍历:

Self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}

 对于--大家让迭代器等于8或者等于6让其随着代码走一遍就知道正确与否。

有了迭代器后,我们就可以将map的[]运算符实现出来了,下面我们先修改insert函数:

pair<iterator,bool> insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点必须为黑色
			_root->_col = BLACK;
			//只有一个根节点,插入成功后返回根节点所在的迭代器
			return make_pair(iterator(_root), true);
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//cur找到与要插入节点相等的节点,但由于相等没有插入,返回cur这个位置的迭代器
				return make_pair(iterator(cur), false);
			}
		}
		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		//开始红黑树
	    //省略没有修改的地方......
		_root->_col = BLACK;
		//本来应该返回新插入节点的迭代器,但是由于cur在进入红黑树位置会发生调整,所以提前保存cur
		return make_pair(iterator(newnode), true);
	}

我们详细的介绍过map中的[]运算符,这个运算符可以实现:如果key不在就插入,如果在就返回second的引用(map中的second可以修改我们反复说过),唯一需要注意的地方是最后要返回新插入节点的迭代器,但是新节点在红黑树调整的过程中cur发生了变化,所以提前记录cur,最后返回之前记录的cur的这个节点即可。

 将map和set中insert的返回值修改完后我们实现[]:

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

首先[]要返回pair中second的引用,而second的模板参数是V所以返回值是V&,然后【】的插入是根据key来确定的,如果key存在bool为false,如果不存在就插入,但是不管怎么样我们都返回second,再插入的时候我们刚开始不知道K,V中的V具体是多少,所以我们给一个匿名对象去初始化即可,返回值这里就用到我们以前的知识了,首先ret是一个pair,先拿到pair中的迭代器,因为map迭代器里面存放的是pair,所以代码应该是:ret.first->_node->_data->second,但是由于我们重载了->符号所以可以直接访问到_data,然后返回_data->second即可下面我们测试一下是否成功:(如果对于->还有问题可以看一下下面第一张图:)

 it是一个迭代器,一旦通过->符号就拿到了红黑树节点中的_data,map中data存放的是KV模型,所以直接访问first,second。

void test_map2()
	{
		string arr[] = { "苹果","西瓜","西瓜","梨","葡萄" };
		map<string, int> mp;
		for (auto& e : arr)
		{
			mp[e]++;
		}
		for (auto& m : mp)
		{
			cout << m.first << ":" << m.second << endl;
		}
	}

 通过运行结果我们也发现是没问题的,接下来我们就要实现const迭代器了,首先先加入const迭代器:

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

 然后我们先用set做一下测试:

 运行起来报错了:

 错误原因在这里:

 我们已经将set的普通迭代器修改为红黑树中的const迭代器,但是红黑树中的begin()是一个普通迭代器,iterator经过typedef已经变成const迭代器,所以发生了报错,当然有人发现:

 将set的第二个参数加个const就可以,确实是这样,但是map该怎么办呢?map能在pair前面加上const吗?很明显是不能的,因为map中只有key也就是first不能修改,second是可以修改的,这该怎么办呢?下面我们参考一下源代码:

 首先set里面普通迭代器用const迭代器实现,const迭代器也用const迭代器来实现,并且begin和end()也没做任何修改,所以这里应该也面临着和我们一样的问题,那就是如何解决普通迭代器转化为const迭代器,我们继续看:

 我们可以看到源码中的迭代器比我们的迭代器多了一个构造函数,首先我们区分一下,iterator里面的参数都是不加const的所一iterator是普通迭代器,而self里面的参数是ref和ptr,当传参为const类型时self就变成了const迭代器,当传参为不带const就是普通迭代器,而最后的这个构造函数的参数是一个普通迭代器,那有什么作用呢?其实是这样:

1.当我本身的迭代器是普通迭代器时,参数也是一个普通迭代器这个时候就是一个拷贝构造函数。

2.当我本身是一个const迭代器时,参数是一个普通迭代器,这个时候就变成了用普通迭代器构造const迭代器,也就是说让普通迭代器和const迭代器之间进行转化了,再想想我们刚刚的报错,无法从普通迭代器转化为const迭代器,用上这个构造函数不就可以将红黑树中的普通迭代器转化为const迭代器了吗。 (现在搞懂这个构造函数为什么不用self来做参数了吧,因为self的参数如果是const那么self就变成const迭代器,那还如何转化呢)

 了解了以上知识我们直接加一个构造函数就可以了,一定要注意这个构造函数的参数是普通迭代器:

template <class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;
	RBTreeIterator(Node* node)
		:_node(node)
	{

	}
	RBTreeIterator(const RBTreeIterator<T, T&, T*>& it)
		:_node(it._node)
	{

	}

有了这个构造函数运行起来就不会报错了,下面我们看看map的迭代器:

 我们可以看到map中普通迭代器还是普通迭代器,const迭代器是const迭代器。

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

这样我们就搞定了set和map的底层,以上就是本文的所有内容了。


总结

对于这里的难点我认为迭代器确实是有难度的,并且有些方法也不是我们普通人可以想到的,所以要多看优秀的代码才能提升自己。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。