STL — Map和Set的简易实现

水深无声 2022-06-06 14:28 133阅读 0赞

# Map和Set的简易实现 #

前面两篇博客我分别介绍了 [Map容器的使用][Map]以及 [Set容器的使用][Set]， 我们了解到它的用法以及明白了它的底部实现其实就是[红黑树][Link 1]. 这个时候可能有人就不

理 解 了.底层是红黑树Map为什么可以存储一个主键一个键值. 而Set只拥有一个主键.这里就是STL的强大之处. 利用巧妙地方法极大的提升了代码的

复用. 当然 在实现之前我也看了Map和Set的源码. 我这里实现的只是最简易的Map和Set，并没有很多复杂的功能. 可以插入，删除,迭代器的加加.减

减操作. 好了 那我们进入正题.

首先思考第一个问题. Map和Set的元素个数不同.当然如果你说我给Map设计一个红黑树容器，再给Set设计一个红黑树容器.这样没问题，但是你的代码

是 不是但有点太长了.如果这里不是红黑树是一个很大的项目呢？ 所以需要使用同一个红黑树的底层容器来提升代码复用.当然你可以让Map在这里传入

一个 pair<>，让Set在这里传入一 个Key，这个思想没问题.但红黑树里面需要用到键值之间的比较，Set在这里可以直接使用Key进行比较.但是Map的

pair<K,V> 需要使用其中的.first来进 行比较？ 那么这里应该如何实现呢？ 这里需要用到仿函数的知识，以及巧妙的运用模板. 下面我贴出来代码

还有一张过程步骤图帮大家理解这个过程.

**Map的封装代码:**

#include"RBTree.h"
    
    template<class K,class V>
    class MakeMap
    {
    
    public:
    	typedef pair<K, V> ValueType;
    
    	struct KeyOfValue
    	{
    		const K& operator()(const ValueType& kv)
    		{
    			return kv.first;
    		}
    	};
    
    	typedef typename RBTree<K, ValueType,KeyOfValue>::Iterator Iterator;
    
    	pair<Iterator, bool> Insert(const ValueType& v)
    	{
    		return _Tree.Insert(v);
    	}
    
    	V& operator[](const K& key)
    	{
    		pair<Iterator,bool> ret = _Tree.Insert(make_pair(key, V()));
    		//模板参数的V() 缺省值.
    		return ret.first;
    	}
    	Iterator Begin()
    	{
    		return _Tree.Begin();
    	}
    
    	Iterator End()
    	{
    		return _Tree.End();
    	}
    private:
    	RBTree<K, ValueType, KeyOfValue> _Tree;
    };
    
    void Test()
    {
    	MakeMap<string, string> dict;
    
    	dict.Insert(make_pair("liangliang", "亮亮"));
    	dict.Insert(make_pair("MT", "梦婷"));
    	dict.Insert(make_pair("Steam", "蓝洞"));
    	dict.Insert(make_pair("type", "字节"));
    
    	MakeMap<string, string>::Iterator it = dict.Begin();
    
    	while (it != dict.End())
    	{
    		cout << it->second << " ";
    		++it;
    	}
    }

**Set的封装代码:**

#include"RBTree.h"
    
    template<class K>
    class mySet
    {
    public:
    	typedef K ValueType;
    	struct KeyOfKey
    	{
    		const ValueType& operator()(const ValueType& key)
    		{
    			return key;
    		}
    	};
    
    	typedef typename RBTree<K, K,KeyOfValue>::Iterator Iterator;
    	//如果没有typename，编译器就会去RBTree里面去寻找Iterator.但是RBTree并没有实例化，所以会找不到
    	//然后报错. 所以typename告诉编译器这个类型是一个模板的类型，现在先不要确定它的类型.
    
    	pair<Iterator, bool>insert(const K& key)
    	{
    		return Tree.Insert(key);
    	}
    
    	Iterator Begin()
    	{
    		return Tree.Begin();
    	}
    
    	Iterator End()
    	{
    		return Tree.End();
    	}
    
    
    protected:
    
    	RBTree<K, ValueType, KeyOfKey> Tree;
    };
    
    
    void Test()
    {
    	mySet<int> T;
    
    	T.insert(1);
    	T.insert(2);
    	T.insert(3);
    	T.insert(4);
    	T.insert(5);
    	T.insert(6);
    	T.insert(7);
    
    	mySet<int>::Iterator it = T.Begin();
    
    	while (it != T.End())
    	{
    		cout << *it << " ";
    		++it;
    	}
    
    	cout << endl;
    
    }

**RBTree的实现代码:**

#include<iostream>
    #include<Windows.h>
    #include<string>
    #include<assert.h>
    using namespace std;
    
    enum colour
    {
    	RED,
    	BLACK
    };
    
    template<class ValueType>
    struct RBTreeNode
    {
    	ValueType _valueField;
    	RBTreeNode<ValueType>* _left;
    	RBTreeNode<ValueType>* _right;
    	RBTreeNode<ValueType>* _parent;
    
    	colour _col;
    
    	RBTreeNode(const ValueType& v)
    		:_valueField(v)
    		, _left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _col(RED)
    	{}
    };
    
    template<class ValueType>
    struct __RBtreeIteartor
    {
    	typedef RBTreeNode<ValueType> Node;
    	typedef __RBtreeIteartor<ValueType> self;
    
    public:
    
    	__RBtreeIteartor(Node* node)
    		:_node(node)
    	{}
    
    	__RBtreeIteartor(const self& node)
    		:_node(node._node)
    	{}
    
    	ValueType& operator*()
    	{
    		return _node->_valueField;
    	}
    
    	ValueType* operator->()
    	{
    		return &operator*();
    	}
    
    	self& operator=(const self& node)
    	{
    		_node = node._node;
    	}
    
    	self& operator++()
    	{
    		//1.如果右不为空，访问右树的最左节点
    		//2.如果我的右为空，下一个访问的就是沿着这个路径往上找，第一个右树不是我的节点
    		//然后访问该节点.
    		if (_node->_right)
    		{
    			Node* subR = _node->_right;
    			while (subR->_left)
    			{
    				subR = subR->_left;
    			}
    			_node = subR;
    		}
    		else
    		{
    			Node* cur = _node;
    			Node* parent = cur->_parent;
    			while (parent && cur == parent->_right)
    			{
    				cur = parent;
    				parent = cur->_parent;
    			}
    			_node = parent;
    		}
    		return *this;
    	}
    
    	self& operator--()
    	{
    		if (_node->_left)
    		{
    			Node* subL = _node->_left;
    			while (subL->_right)
    			{
    				subL = subL->_right;
    			}
    			_node = subleft;
    		}
    		else
    		{
    			Node* cur = _node;
    			Node* parent = cur->_parent;
    			while (parent && cur == parent->_left)
    			{
    				cur = parent;
    				parent = cur->_parent;
    			}
    			_node = parent;
    		}
    		return *this;
    	}
    
    	bool operator==(const self& s)
    	{
    		return _node == s._node;
    	}
    
    	bool operator!=(const self& s)
    	{
    		return _node != s._node;
    	}
    
    private:
    	Node* _node;
    
    };
    
    template<class K, class V,class KeyOfValue>
    class RBTree
    {
    	typedef  V ValueType;
    	typedef RBTreeNode<ValueType> Node;
    
    public:
    
    	typedef __RBtreeIteartor<ValueType> Iterator;
    
    	RBTree()
    		:_root(NULL)
    	{}
    	Iterator Begin()
    	{
    		Node* cur = _root;
    		while (cur && cur->_left != NULL)
    		{
    			cur = cur->_left;
    		}
    
    		return Iterator(cur);
    	}
    
    	Iterator End()
    	{
    		return Iterator(NULL);
    	}
    
    	pair<Iterator,bool> Insert(const ValueType& v)
    	{
    		//_Insert(_root, x, y);
    		if (_root == NULL)
    		{
    			_root = new Node(v);
    			_root->_col = BLACK;
    			return make_pair(Iterator(_root), true);
    		}
    
    		KeyOfValue keyofvalue;
    
    		Node* cur = _root;
    		Node* parent = cur;
    
    		while (cur)
    		{
    			if (keyofvalue(cur->_valueField) > keyofvalue(v))
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (keyofvalue(cur->_valueField) < keyofvalue(v))
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else if (keyofvalue(cur->_valueField) == keyofvalue(v))
    			{
    				return make_pair(Iterator(cur), false);
    			}
    		}
    
    		if (keyofvalue(parent->_valueField) > keyofvalue(v))
    		{
    			parent->_left = new Node(v);
    			parent->_left->_parent = parent;
    			cur = parent->_left;
    		}
    		else
    		{
    			parent->_right = new Node(v);
    			parent->_right->_parent = parent;
    			cur = parent->_right;
    		}
    
    		Node* newNode = cur;
    		//目前父亲节点，插入节点，叔叔节点已经就绪.
    		while (parent && parent->_col == RED)
    		{
    			Node* parentparent = parent->_parent;
    			Node* uncle = NULL;
    
    			if (parentparent->_left == parent)
    				uncle = parentparent->_right;
    
    			else
    				uncle = parentparent->_left;
    
    			if (uncle && uncle->_col == RED)
    			{
    				parentparent->_col = RED;
    				parent->_col = BLACK;
    				uncle->_col = BLACK;
    
    				cur = parentparent;
    				parent = cur->_parent;
    
    			}
    			else if (uncle == NULL || uncle->_col == BLACK)
    			{
    				if (parentparent->_left == parent)
    				{
    					if (parent->_left == cur)
    					{
    						RotateR(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateLR(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				else
    				{
    					if (parent->_right == cur)
    					{
    						RotateL(parentparent);
    						parent->_col = BLACK;
    					}
    					else
    					{
    						RotateRL(parentparent);
    						cur->_col = BLACK;
    					}
    				}
    				parentparent->_col = RED;
    				if (parentparent == _root)
    				{
    					_root = parent;
    				}
    
    			}
    			else
    			{
    				assert(false);
    			}
    		}
    		_root->_col = BLACK;
    		return make_pair(Iterator(newNode), true);
    		//担心经过旋转之后，找不到新增节点了,所以提前记录好.
    	}
    
    
    	Iterator Find(const K& key)
    	{
    		Node* cur = _root;
    		while (cur)
    		{
    			if (keyofvalue(cur->_valueField) > keyofvalue(key))
    			{
    				cur = cur->_right;
    			}
    			else if (keyofvalue(cur->_valueField) < keyofvalue(key))
    			{
    				cur = cur->_left;
    			}
    			else if (keyofvalue(cur->_valueField) == keyofvalue(key))
    			{
    				return Iterator(cur);
    			}
    		}
    		return Iterator(NULL);
    	}
    
    protected:
    
    	void RotateLR(Node*& parent)
    	{
    
    		RotateL(parent->_left);
    
    		RotateR(parent);
    	}
    
    	void RotateRL(Node*& parent)
    	{
    		RotateR(parent->_right);
    		RotateL(parent);
    	}
    
    	void RotateR(Node*& parent)
    	{
    		Node* subL = parent->_left;
    		Node* subLR = subL->_right;
    
    		parent->_left = subLR;
    		if (subLR)
    			subLR->_parent = parent;
    		Node* ppNode = parent->_parent;
    		subL->_right = parent;
    		parent->_parent = subL;
    		if (ppNode == NULL)
    		{
    			_root = subL;
    			_root->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    				ppNode->_left = subL;
    			else
    				ppNode->_right = subL;
    			subL->_parent = ppNode;
    		}
    	}
    
    	void RotateL(Node*& parent)
    	{
    		Node* subR = parent->_right;
    		Node* subRL = subR->_left;
    
    		parent->_right = subRL;
    		if (subRL)
    			subRL->_parent = parent;
    
    		Node* ppNode = parent->_parent;
    		subR->_left = parent;
    		parent->_parent = subR;
    
    		if (ppNode == NULL)
    		{
    			_root = subR;
    			_root->_parent = NULL;
    		}
    		else
    		{
    			if (ppNode->_left == parent)
    				ppNode->_left = subR;
    			else
    				ppNode->_right = subR;
    			subR->_parent = ppNode;
    		}
    	}
    private:
    	Node* _root;
    };

上面的代码我们可以看到. Set和Map其实就是一层马甲，对他们来说只是封装了底层的红黑树，只不过他们传入红黑树 KeyOfValue的参数不同.而后面

的KeyOfValue才是决定，RBTreeNode当中的\_valueField与key比较时，返回的是Key还是pair<>.first. 我下面还有一幅图用来帮大家理解这整个复用

代码的框架. 大家仔细看一定会明白这里的KeyOfValue模板参数，以及\_ValueType的作用. 如果理解这些那么Map和Set的简易实现应该就差不多了.

![20171112131051861][]

接下来我着重解释一下红黑树的迭代器，因为上一篇博客红黑树当中只是简单构建出来一颗[红黑树][Link 1]，并没有对它的迭代器进行实现，那么现在我们继续

了解它的迭代器:

首先迭代器就是封装一层指针，让我们能够方便的遍历每一个容器.使用相同的方法. 也就是说我们不需要知道容器的底层实现. 就会遍历这个容器.

所以迭代器就是增加了封装性.给外边暴露一个接口，让你只会用就行了，不用知道为什么.红黑树的迭代器的operator\*，operator->已经是老生常谈

了，所以我们今天的重点是明白迭代器的operator++()以为这是一个算法-> 因为红黑树遍历是中序遍历，所以我们只需要帮迭代器找到它下一个需要

访问的节点即可. 首先中序遍历的顺序是 左 中 右. 而我们这个算法就是找到中序遍历的下一个节点位置:

![20171112210212106][]

当然operator--我们只需要颠倒一下就可以~ 这个算法需要自己自己走一走过程就会理解他为什么这么吊！！！！！更多红黑树的知识我们可以去看

一下我的上一个博客. 当然map和set肯定不仅仅只有红黑树版本的. 我们以后还会有hash版本的map和set.其实代码复用的原理都一样. 只不过后面

hash的模板结构嵌套更加复杂一点. 但是只要你理解了之后，自己也就会设计出来这些结构. Map和Set的结构我们只要好好地认识上面的图就可以好好

理解. ![微笑][smile.gif]![微笑][smile.gif]![微笑][smile.gif]![微笑][smile.gif]

[Map]: http://blog.csdn.net/dawn_sf/article/details/78456747
[Set]: http://blog.csdn.net/dawn_sf/article/details/78458380
[Link 1]: http://blog.csdn.net/dawn_sf/article/details/78419286
[20171112131051861]: /images/20220606/ab25942c49e1475e9819aa02dc5e5d7d.png
[20171112210212106]: /images/20220606/96a884fcee444000ad20a185a85eea2a.png
[smile.gif]: /images/20220606/d95d2b1d2a0445e5a6536b3110c270ae.png