【C++】从零开始map与set的封装

// 迭代器
//T 表示数据类型 Ref为引用 Ptr为指针
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++()
{
	//首先，能访问到当前节点说明左子树的都已经访问过啦
	//所以就要分类讨论
	//如果右边有子树,就要去寻找右子树的最左节点
	if (_node->_right)
	{
		Node* cur = _node->_right;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		_node = cur;
	}
	//如果右边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行
	//找到祖先节点(注意祖先节点右边还没遍历)
	//此时也要进行分类讨论
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		//_node == parent->_right
		//说明parent的节点已经访问过了
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

// 节点结构体
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	color _col;
	RBTreeNode(pair<K, V> kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(Red)
	{}

};

//-------------------------------------------
//---------------- 红黑树实现 -----------------
//-------------------------------------------
//-------- 适配map 与 set 的进阶版本 -----------
//-------------------------------------------
#include<utility>
enum color
{
	Black,
	Red
};
// 节点结构体
// T在这里是 pair<key , value>
template<class T>
struct RBTreeNode
{	
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	
	T _data;
	color _col;
	RBTreeNode(T data)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(Red)
	{}

};

//适配map与set 的版本
// 迭代器
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++()
	{
	}
	Self& operator--()
	{
	}
};
//K 为键值 T 为储存的结构（pair<K ,V>） KeyOfValue 是取出Key的方式
template<class K, class T , class KeyOfValue>
class RBTree
{
public:
	typedef _RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeNode<T> Node;

	Iterator begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur);
	}
	Iterator end()
	{
		return Iterator(nullptr);
	}

	//右单旋
	void RotateR(Node* parent)
	{
	}
	//左右双旋
	void RotateLR(Node* parent)
	{
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
	}
	//------------------
	//返回需要比较的值
	KeyOfValue kot;
	//------------------
	//插入函数	
	bool Insert(T data)
	{
	}

private:
	void _IsBalance(Node* root , int num)
	{
	}
	bool Check(Node* root, int blackNum, const int refNum)
	{
	}

	void _InOrder(Node* cur)
	{
	}
	RBTreeNode<T>* _root = nullptr;
};

//----------------------------------
//----------  MAP 的实现  -----------
//----------------------------------
#include"RBTree.h"
#include<utility>

//层层递进,
//map 上层要提供 key value 键值对
//相应的要改造红黑树的代码 使其满足泛型编程
template<class K , class V>
class map 
{
	struct MapOfValue
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	typedef typename RBTree<K, pair<const K, V>, MapOfValue>::Iterator iterator;
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	bool Insert(pair<const K, V> kv)
	{
		return _t.Insert(kv);
	}
	void InOrder()
	{
		_t.InOrder();
	}
private:
	//底层是红黑树
	//需要提供对应的键值 储存结构 比较方式
	RBTree<K, pair<const K, V>, MapOfValue > _t;
};

//----------------------------------
//----------  SET 的实现  -----------
//----------------------------------


#include"RBTree.h"
#include<utility>


//层层递进,
//set 上层要提供 key 键值
//相应的要改造红黑树的代码 使其满足泛型编程

template<class K>
class set
{
	struct SetOfValue
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};
public:
	typedef typename RBTree<K, const K, SetOfValue>::Iterator iterator;
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	bool Insert(K kv)
	{
		return _t.Insert(kv);
	}
	void InOrder()
	{
		_t.InOrder();
	}
private:
	//底层是红黑树
	//需要提供对应的键值 储存结构 比较方式
	RBTree<K, K, SetOfValue > _t;
};