一.map和set理解

1.set

set从简单的角度理解，就是一颗二叉搜索树，每个节点存放一个元素，并且不允许有相同元素的节点出现，被要求的是，节点的值不能被修改，但可以增加或删除。

---

 2.map 

而map则是在set的基础上，将存储数据更替为键值对pair<K,V>，其中K一般是不能更改的，而V是能够更改的。

---

二.map和set实现

由于map和set的底层都是红黑树，所以这里我们分享一种map和set共用一份红黑树代码的实现方式。

---

1.基本框架

首先我们要知道，map和set存储的数据类型是有区别的，前者为pair<K,V>键值对，后者为单一的数据类型K，所以对于红黑树的数据类型，我们需要做出更改：

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

能够看出，我们直接将数据类型改为模版T，用来替换pair<K,V>和K，数据直接用data代替。 

当进行插入操作时，我们又会面临一些问题：

• 如果是set，当进行比较操作时直接比较K，无妨。
• 但是如果是map，比较时则会比较pair，虽然pair类型可以进行比较，但是其底层的比较方式却与我们想要的结果不同。

为了让map也进行key的比较，我们引入仿函数，通过仿函数，来获取到map中pair的key：

		struct MapKeyOfT
		{
			const K& operator(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
		struct SetKeyOfT
		{
			const K& operator(const K& key)
			{
				return key;
			}
		};

为了帮助map完成操作，set也同样需要一个仿函数。

由于仿函数需要创建对象使用，所以我们还需引入新的模版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;
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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;
			}
		}

那么为什么我们这里还要保留模版参数K呢？？

这是因为当使用find函数和erase等函数时，无论是map还是set，我们只需要传入K即可。

 进行数据比较时，只需调用仿函数，即可完成key的比较。

到此，两个容器的基本框架才算完成：

#include"RBTree.h"
namespace MyMapSet
{
	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, SetKeyOfT> _t;
	};
}

#include"RBTree.h"
namespace MyMapSet
{
	template<class K,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};
	public:
		bool Insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<K, pair<K,V>, MapKeyOfT> _t;
	};
}

---

2.迭代器

那么map和set只要是C++的容器，就一定会存在迭代器，下面我们直接通过代码来分析迭代器的常用功能该如何实现。

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

创建一个迭代器类能更好的帮助我们在红黑树类中实现迭代器功能。

这些功能容易理解，这里就不做过多解释。

下面我们来分析关键功能++。

 首先红黑树是二叉搜索树，其数据本质上是按升序的顺序排序，所以当使用++时，我们得到的一定是按升序的下一个数据。

而我们已经知道，红黑树的中序遍历结果即为升序，所以在一棵同时包含父子节点的树中，其三个节点的大小顺序为：左子节点 < 根节点 < 右子节点。

所以如果该节点为左子节点，那么++之后的节点就是其父节点，如果该节点为父节点，那么++之后的节点则会是其右子树的最小节点。而如果该节点为右子节点，那么就说明其为该棵同时包含父子节点的树中的最大节点，此时就要循环往上遍历，直至循环至根节点，说明此时已经为整棵树的最大节点，再++即为空。

或者循环过程中cur节点为父节点的子节点，再++则为父节点。

	Self& operator++()
	{
		if (_node->_right)//有右子树，去找右子树的最左子节点
		{
			Node* leftMin = _node->_right;
			while (leftMin && leftMin->_left)
			{
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		else//没有右子树，则找到其父节点
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//如果该节点为父节点的右子树，则向上循环
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;//直至循环至根节点，或者循环过程中cur节点为父节点的子节点
		}
		return *this;
	}

完成迭代器类的实现之后，紧接着就是将其封装在红黑树类中：

template<class K, class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __RBTreeIterator<T, T&, T*> Iterator;
	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return Iterator(leftMin);
	}
	Iterator End()
	{
		return Iterator(nullptr);
	}

 而迭代器的begin，即为整棵树的最左节点，end即为空。

最后再将其分别封装到map和set中，即可完成迭代器的实现：

set：

	public:
		typedef typename RBTree<K, K, SetKeyOfT>::Iterator iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}

map：

	public:
		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator iterator;
		iterator begin()
		{
			return _t.Begin();
		}
		iterator end()
		{
			return _t.End();
		}

 测试如下：

最后还有一个值得关注的问题，就是set和map的key都是不能被修改的，但是我们上边的代码并不能实现：

这是不合理的，而解决的方法为：

map：       

RBTree<K, pair<const K,V>, MapKeyOfT> _t;

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
set：        

RBTree<K, const K, SetKeyOfT> _t;
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

在封装时即将key定义为const类型，便可保证其不能被修改。 

---

3.map重载[]

map不同于set的另外一点就在于其重载了运算符[]，可以使得map通过key来直接得到其value。

当key存在时，就返回其对应的value，不存在则会新插入该key，并返回其迭代器。

所以想要重载[]，我们还需对插入函数进行改进：

pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根给黑色
			return make_pair(Iterator(_root),true);//树为空，创建并返回迭代器
		}
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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 make_pair(Iterator(cur), false);//节点存在，返回
			}
		}
        cur = new Node(data);
		Node* newnode = cur;//插入后cur会变，所以提前记录
		cur->_col = RED;//新增节点给红色
        //此处省略插入步骤
       _root->_col = BLACK;
		return make_pair(Iterator(newnode), true);//树不为空，但不存在，返回新节点
	}

要将插入函数的返回值改为pair类型，同时包含Iterator和bool。

此时我们便可在map中重载[]：

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

定义ret去接收返回值，其中ret.first得到的是迭代器，而迭代器中也包含data的pair类型，所以再取second即可返回value。 

测试如下：