中级C++：map和set的迷你实现

• 基建改造
• 红黑树的迭代器
• 封装成map
• • 红黑树的改造
• 封装成set
• 编者寄语

• 由于set使用的是K。map使用的K是pair中的first，需要新增的第二个模板参数 T，来确定是用的是哪一种类型。
• 由于红黑树这个类模板，也不知道这个类型到底具体是什么，所以再增加一个仿函数类型模板参数，获取K的类型。

template
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{
	}
	
};

	template
	class RBTree
	{
		....

• 用一个节点的指针初始化成迭代器，实现对STL所有容器进行统一方式的访问。
• 老三样，T，T&，T*；iterator要确保和官方迭代器名字一致就可以用范围for。
• *it（迭代器），拿到这个指针里面的数据。
• != 就是两个节点的指针不相等
• 红黑树的++：访问到容器的下一个节点：
  • 红黑树的 begin 则应该是中序里最左边的一个节点。
  • ++，看begin 的右侧，有的话，找右子树里面最左面的一个。
  • 若右侧也没有：代表我这一层的左子树右子树访问结束。返回上一层。
  • 由于这一层是从上一层的左子树下来的，要看当前节点是不是双亲结点的左侧；
    • 不是则一直迭代往上走；
    • 是就返回双亲结点。
      
      

template
struct RBTreeiterator   //类模板
{
	typedef RBTreeNode Node;...
	typedef RBTreeiterator Self;  
	Node* _node;

	RBTreeiterator(Node* node = nullptr)
		:_node(node)
	{
	}

	//*it 对一个指针解引用，取到的是节点里面的数据
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}

	//红黑树迭代器的前置++ 返回是自增以后的迭代器
	Self& operator++()
	{
		if (_node->_right)
		{
			//右边存在,找右子树最左边的那个节点
			Node* subRL = _node->_right;
			//左子树到头了，此刻的subRL就是右子树里最左边的节点
			while (subRL->_left)
			{
				subRL = subRL->_left;
			}
			_node = subRL;
		}
		else//代表当前这个子树访问完了，左 中 右 找此根的父亲，该父亲的左孩子是此根。
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent&& parent->_right==cur)
			{
				cur = parent;
				parent = cur->_parent;
			}

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

• 有了第二个模板参数，为什么还要第一个模板参数K呢；因为查找是按K值查找的…且STL原版就是这么设计的…
• 迭代器和插入用的都是红黑树的。参考官方文档可知：插入返回的时pair类型，第一个参数是插入结点或值相等结点的迭代器和布尔值。
• 还有一个 [ ] 重载，返回的时pair里面V的引用。make_pair(“呵呵哒”,“我C”)–“我C”
• typedef typename RBTree, MapKeyOfT>::iterator iterator;告诉编译器那一长托是个类型，不然编不过去。

template < class K, class V>
	class map
	{
		struct MapKeyOfT //把 K 提取出来
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}
//iterator --》 结点的数据类型
		pair insert(const pair& kv)
		{
			return _t.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair ret = _t.Insert(make_pair(key, V()));
			return ret.first->second;// iterator.operator->() data:pair的地址  -> second   
		}
	private:
		RBTree, MapKeyOfT> _t;//使用模板显式的声明使用的类型
	};

• T：set：int,char…；map：pair…

template
class RBTree
{
	typedef RBTreeNode Node; ....//T类型的节点
public:
	typedef RBTreeIterator iterator;  .....
	typedef RBTreeIterator const_iterator;

	iterator begin()
	{
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}

		//return left;
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	RBTree()
		:_root(nullptr)
	{}
	....
	Node* Find(const K& key);
	//插入
	pair Insert(const T& data)
	{
		if (_root == nullptr)
		{
				......
			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
			{
				return make_pair(iterator(cur), false);
			}
		}

		// 新增节点，颜色是红色，可能破坏规则3，产生连续红色节点
		cur = new Node(data);
		Node* newnode = cur;   //便于返回迭代器...
		cur->_col = RED;
		........
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

• 第二个模板参数也传K…

template < class K>
	class set
	{
		struct SetKeyOfT  
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree::iterator iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		pair insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree _t;
	};
----仿函数使用场景..
		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;
			}
....

• 现在一只半截的buff，迟早凉凉…该哈希了…