map和set的封装用红黑树

标签：node map set const parent operator 用红 root 节点

1.iterator迭代器

迭代器。迭代器的作用——容器的类型有很多种但是不是每一个容器的取值方式都是一样的。比如说list是箭头->和解引用*的方式，string则是通过方括号的方式访问的。所以为了统一的访问这些容器所以我们就设置出了迭代器。统一用一种方式这里是，箭头->和解引用*的方式。迭代器里面就是存一个节点或一个数据的指针，通过一些运算符重载方式进行统一。所以我们可以理解迭代器成“指针”，但是迭代器本质还是一个类。我们用模版去实现。

template<class T,class Ref,class Ptr>//Ref是引用，Ptr是指针
struct RBTreeiterator//我们将红黑树的迭代器命名成RBTreeiterator
{

}；

第一个参数T是RBNode中的唯一模版参数，传进来是为了在迭代器中有效储存数据。因为我们需要再迭代器中存一个“数据”的指针（这个数据可以是某个节点也可以是某个内置类型）。第二个参数代表T类型的引用，Ptr代表T类型的指针。

首先我们需要储存数据的指针。 RBNode<T>* _node;



template<class T,class Ref,class Ptr>//Ref是引用，Ptr是指针
struct RBTreeiterator//迭代器就是来实现数据与数据之间的操作的。与数据的类分开了
{

    typedef RBNode<T> Node;
    typedef RBTreeiterator<T,Ref,Ptr> Self;//这里重命名的原因是如果下次修改时，只需要修改这一个                    地方了。方便维修。
    Node* _node;
    Node* _root;
}；

然后就是写迭代器会有的操作，我们可以将迭代器比作指针，或者换一句话说就是数据本身的指针，那么我们通过类的运算符重载，它应该会有这些操作operator*(),operator->(),operatpr++(),operator--(),operator!=(),operator==()等等操作。_root是方便--的操作，在operator--中会有说明。

template<class T,class Ref,class Ptr>/
struct RBTreeiterator
{
    
    typedef RBNode<T> Node;
    typedef RBTreeiterator<T,Ref,Ptr> Self;
          
    Node* _node;

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

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

    bool operator!=(const Self&  s)
    {
    	return _node != s._node;;
    }

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

这些操作都比较基础，主要是operator++和operator--有点棘手。我们先来分析operator++。

operator++()

我们在拿到这个节点的迭代器后我们++应该指向哪一个节点呢。我们通过map和set的遍历知道，他们都是中序遍历，所以++后应该按照中序遍历的规则来。左子树根右子树是中序的遍历顺序。（注意：我们暂时将这个要++的节点称作node）此时我们需要分三种情况讨论了。

情况一：node是左子树

如果此时node位于左子树，那么++后应该是左子树的根也就是node的parent。parent不可能为空，因为如果node为空就不可能是左子树，所以parent一定存在。（注意：由于我们的RBNode类是三叉树结构也就是除了包含左，右子树的节点，还会额外包含父节点）。

情况二：node是根节点

如果此时node是根节点，那么按照中序的顺序应该是右子树。但是如果右子树不存在呢不存在++后应该返回parent节点，然后接着判断parent是左子树，根还是右子树。此时就只有两种情况，1.一直是右子树直到空，2.遇到是左子树的情况。那么就回到情况一了。

情况三：node是右子树

如果此时node是右子树，那么按照中序的顺序++后应该讨论node的下一个节点的右接单存不存在如果不存在就返回到上一层，判断parent的parent是左子树，根还是右子树。如果存在就找到node的右节点的最左节点。我们发现有些是回到情况二的情况了。所以我们综上我们要分为两大类。node的右节点是否为空。

template<class T,class Ref,class Ptr>//Ref是引用，Ptr是指针
struct RBTreeiterator
{
	/
    /
	Self& operator++()//函数()中没有加int代表是前置++，operator++(int)是后置++
	{
		//是中序遍历，所以++也是按照中序的顺序来的
		//按照中序递归的规律来走
		//如果cur没有右节点了，那就往上左找到cur==parent->left的节点 _node=parent。如果没有就_node==nullptr。
		//如果cur存在右节点，就是右节点的最左节点。
		assert(_node);
		Node* cur = _node;
		if (cur->right)
		{
			Node* curRLmost = cur->right;
			while (curRLmost->left)
			{
				curRLmost = curRLmost->left;
			}
			_node= curRLmost;
		}
		else
		{
			Node* parent = cur->parent;
			while (parent && cur == parent->right)//这个条件写的很好，如果parent为空代表一直为右，如果cur不是parent的右代表是整棵树的左边，此时就是要找节点。写条件的技巧，只需写循环一直走下去我们要达到的结果，即是条件。
			{
				cur = parent;
				parent = parent->parent;
			}
			_node = parent;
		}
		return *this;
	}
};

operator--()

operator--()就是中序的反顺序，本来++是按照中序来的，那么--就是反的：右子树根左子树。这么一个顺序来的。那么在逻辑上是operator++是相反的那么一样是分三种情况，两大类去写。这里就不再复述了。但是这里需要注意的是，如果node是从end()开始的就找不到树中来了，所以我们需要早迭代器中加一个_root节点，具体代码如下。


template<class T,class Ref,class Ptr>//Ref是引用，Ptr是指针
struct RBTreeiterator
{
	/
    /
	Self& operator--()
	{
		Node* node = _node;
		if (node->left)//存在那么此时是根节点。
		{
			Node* MostRight = node->left;
			while (MostRight->right)
			{
				MostRight = MostRight->right;
			}
			_node = MostRight;//这个指针就指向--后的地方了。
		}
		else//node的左边不存在向上查找。
		{
			Node* parent = node->parent;
			//一种是parent为空，一种是parent转向了
			while (parent && node == parent->right)
			{
				node = parent;
				parent = node->parent;
			}
			_node = parent;//这个指针就指向--后的地方了。
		}
		return *this;
	}
};

1.2const迭代器

和普通迭代器不同的是key值的是否能修改。我们只需要在传入参数时在key的模版参数上加一个const就行了。


//map中

typedef typename RBTree<k, pair<const k, v>, keyOFvalnu>::Iterator iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类
typedef typename RBTree<k, pair<const k, v>, keyOFvalnu>::ConstIterator const_iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类

//set中
typedef typename RBTree<k, const k, keyOFvalnu>::Iterator iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类
typedef typename RBTree<k, const k, keyOFvalnu>::ConstIterator const_iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类

然后在RBTree中加上这么一句代码就行了，不同的V值会实例化不同的迭代器。

	typedef RBTreeiterator<V,V&, V*> Iterator;
	typedef RBTreeiterator<V,const V&,const V*> ConstIterator;

2.细节处理

2.1RBTree中的模版参数

为了实现RBTree的泛性，即能给set用也能给map用，因为set中只有一个数值，而map中有两个数值。为了统一我们将map中的两个值用pair来储存，而且RBTree的模版中接受数据的参数也加到两个。



template<class T, class V, class keyOFvalnu>
class RBTree
{
private:
	typedef RBNode< V> Node;
	Node* _root = nullptr;
}

第一个T是key的类型参数。第二个V是map和set的数据类型。为什么我们还需要一个T来接受key的参数呢，因为无论是在map还是在set中我们都是用key来去排序比较值，我们在Find函数中也是用key来查找的，所以我们必须知道key的类型。至于第三个我们讲解了Find才能去理解。

2.2RBTree中的Find()

在Find函数中我们是通过key去比较容器中的值的，但是map和set传入Find的参数不一样，map是pair，set是int，而且pair中比较大小的运算符重载并不符合我们的要求，我们只需判断pair中的first就行了，但是库中是先判断first接着会判断second。所以我们需要写一个仿函数去实现我们自己的判断。

2.2.3仿函数

我们写这么一个结构体，我们叫它keyOFvalnu。它的功能就是通过括号返回它的key值。



//map<class T class v>中
struct keyOFvalnu
{
	const v& operator()(const pair<k,v>& data)
	{
		return data.first;
	}
};


//set<class v>中
struct keyOFvalnu
{
	const v& operator()(const pair<k,v>& data)
	{
		return data.first;
	}
};

这样通过这么一个结构体我们不同的容器传入不同的keyOFvalnu返回都会返回key了。

所以返回到Find函数中应该这么写

Iterator Find(const V& kv)
{
	keyOFvalnu it;
	Node* root = _root;
	Node* parent = nullptr;
	while (root)
	{
		if (it(root->_data) < it(kv))
		{
			parent = root;
			root = root->right;
		}
		else if (it(root->_data) > it(kv))
		{
			parent = root;
			root = root->left;
		}
		else
		{
			return  Iterator(root,_root);//走到这一步代表找到了key的节点。
		}
	}//出来时代表没找到key节点。
	return Iterator(nullptr,_root);
}

理解Find后对于RBTree中的三个参数理解就加深了。

2.3其他细节

2.3.1Find和Insert函数的返回值。

Find函数的返回值是iterator。找到了就返回这个节点的指针+_root 没有就返回nullptr+_root。Insert函数的返回值是pair<Iterator,bool>。如果有这个值的节点了那么就返回这个节点+false，如果插入成功返回newnode+true。

2.3.2map和set中的套壳函数。

函数在RBTree中都实现好了，只需要在map或者set中套一层壳就好了。这里以map为例。

#include"RBTree.h"
namespace bit
{
	template<class k, class v>
	class map
	{
		struct keyOFvalnu
		{
			const v& operator()(const pair<k,v>& data)
			{
				return data.first;
			}
		};
	public:
		typedef typename RBTree<k, pair<const k, v>, keyOFvalnu>::Iterator iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类
		typedef typename RBTree<k, pair<const k, v>, keyOFvalnu>::ConstIterator const_iterator;//还没实例化的模板类中去取数据，编译器不知道取得是静态成员变量还是类，必须加个typename告诉编译器这是类

		v& operator[](const k& key)
		{
			auto it = _t.Insert(make_pair(key, v()));//传了个默认构造Insert的参数必须是pair类型的，查找key时要变成pair才能传进去。而第二个second则用v的默认构造。
			return it.first->second;
		}


		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);
		}
		void inOrder()//中序打印
		{
			_t.InOrder();
		}                        
	private:
		RBTree<k, pair<k, v>, keyOFvalnu> _t;

	};
}；

2.3.3map中的operator[]

map比set多了一个operator[]


		v& operator[](const k& key)
		{
			auto it = _t.Insert(make_pair(key, v()));//传了个默认构造Insert的参数必须是pair类型的，查找key时要变成pair才能传进去。而第二个second则用v的默认构造。
			return it.first->second;
		}

operator[]，我们需要实现的是，如果[]中的值存在那么就返回second，如果不存在那么就插入first，并返回second。不管有没有都是返回second。那么Insert正好可以满足我们的条件所以前面Insert那么写是为了方便些operator[]。

标签：node,map,set,const,parent,operator,用红,root,节点
From： https://blog.csdn.net/yanlou233/article/details/141267354