map和set的实现原理

为了方便实现我们的map和set，我们肯定是要养成看源码的习惯的，看了源码之后你才会感受到大佬的强大！

在源码里面，对于map和set的实现，底层是用同一棵红黑树封装出来的，并不是用了两棵红黑树
那么大家肯定会有疑问了，一棵红黑树这么能两用呢，况且map和set的底层存储的节点类型不一样啊，map是存储的键值对，set只是存储key

这时设计map和set的大佬就想到了一个极佳的办法，在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型，这个类型可能是pair键值对，也有可能是key类型。

红黑树其实并不知道自己的节点是什么类型，只能用模板来接受存储对象的类型

enum Color {RED,BLACK};
template<class T>//节点存储对象类型，可能是键值对也有可能是key
class RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _col;

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

这样，我们就可以实现一树多用了！

我们就可以根据value的类型来去确定是map还是set了，但是大家可能会有一点小疑问，既然有了value就可以实现红黑树了，那我们还要关键码key有什么用呢？
这里的关键码key是必不可少的！

因为在红黑树搜索的时候，依靠的还是关键码进行搜索，通过所传关键码和红黑树结点中的关键码的大小关系，确定到红黑树中要搜索的某个结点。

红黑树的find函数的参数类型必须是key！

在实现map和set之前，我们先想一想，上一篇博文的红黑树有哪些地方需要进行改进的？

细心的朋友就会发现，上篇博文的代码，插入时比较的就只是在整形情况下的key的比较，但是map和set就只是存储整形吗？显然不是，所以我们就要想办法提取其他类型下的key关键码来进行比较，并且map的节点的value类型是键值对的话，要提取的first，set只需要直接比较key，该如何结局这个问题呢？

我们这个时候就可以使用仿函数了！
我们可以在map和set中各自增加一个仿函数类，在模板传参时，再增加一个仿函数类来提取节点的关键码的参数，我们将他命名为KeyOfT

set

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

private:
	RBTree<K, K, SetKeyOfT> _t;
};

map

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:

private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

rbtree

template<class K,class T,class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:

private:
	Node* _root = nullptr;
};

这样我们再插入的时候就可以直接提取关键码进行插入了

map和set的迭代器

关于map和set的迭代器的实现，设计库里面的源码的大佬很巧妙地运用了const

大家都知道，set是不可以修改的，map可以修改，但是修改的也只是pair键值对的value，pair里面的key可是不能修改的

对红黑树类型中的迭代器类型进行typedef时，可以看到我们在typedef后面加了typename，typename的作用就是告诉编译器后面的东西是一个类型，你先不要编译他，等到模板实例化为真正类型后，你再去取他里面的内嵌类型iterator。因为我们知道编译器是不编译模板的，编译的是模板实例化之后的代码，只有模板实例化之后，它里面的内嵌类型我们才可以取到，所以如果你不加typename，有可能取的不是类型，因为静态变量或函数都是可以通过类+域访问符进行访问的，所以如果你要取模板里面的类型，那就必须在模板前面加typename，告诉编译器你取的是类型。

rbtree迭代器实现

struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T> Self;
	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}

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

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

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}

			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		//右子树 根 左子树
		if (_node->_left)
		{
			//找左子树的最右结点，其实就是次大的结点
			_node = _node->_left;
			while (_node->_right)
			{
				_node = _node->_right;
			}
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;

			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//如果cur是parent的右，则直接让_node指向到parent即可
			_node = parent;
		}

		return *this;//返回迭代器对象
	}
	bool operator!=(const Self& it)const//const修饰表示在该成员函数内部，不能修改对象的任何成员变量
	{
		return this->_node != it._node;
	}

	bool operator==(const Self& it)const//const对象和非const对象都可以调用
	{
		return this->_node == it._node;
	}
};

那么map和set的实现就很简单了：

template <class K>	
	class set
	{
	public:
		//set表层的普通迭代器底层用的依旧是const_iterator，就是不允许对set的迭代器指向内容进行修改
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
		iterator begin()  const   //为了防止权限的放大，我们直接使用const，如果对象是const，调用const的begin，不是const也调用const的begin和end
		{
			return _t.begin();
		}
		iterator end()  const
		{
			return _t.end();
		}

map的迭代器是需要实现两个版本的，因为map容器中的数据是可以被修改的，如果你想修改map中的数据那就用iterator，如果你想修改map中的数据那就用const_iterator。
如果是const_iterator，那解引用或者→返回的就是键值对的常引用或const修饰的指向键值对的结构体指针，那么此时键值对的key和value都是不可以修改的。
如果是iterator，解引用或者→返回的就是键值对的普通引用或无const修饰的指向键值对的结构体指针，但此时键值对的key依旧不可以被修改，只能对键值对中的value进行修改所以即使你用的是iterator，他所指向的键值对的key依旧是不能修改的，我们只能修改他的value。

template <class K, class V>
class map
{
public:

	typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;

	//map的迭代器需要提供两个版本
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator begin()const
	{
		return _t.begin();
	}
	const_iterator end()const
	{
		return _t.end();
	}
private:
	RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

红黑树插入的改造

我们使得插入后其返回值为键值对，如果出现插入key值相等的情况，则将bool改为false即可。最后调色后返回键值对时，我们不能直接返回cur构造的迭代器，因为如果发生调色，则cur位置会更改，所以在插入结点后，用一个curit的结点指针记录一下插入结点的位置，最后返回由curit结点指针构造出来的迭代器

pair<iterator, bool> Insert(const T& data)
//红黑树必须通过结点里面存储的key来进行比较才可以插入结点，所以出现了kot仿函数对象
{
	KeyOfT kot;
	Node* parent = nullptr;
	Node* cur = _root;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(iterator(_root), true);
	}

	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* curit = cur;//保存一下cur的位置否则下面旋转调色过程中，cur有可能被改了
	if (kot(parent->_data) > kot(data))
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_right = cur;
		cur->_parent = parent;
	}

	while (parent && parent->_col == RED)
	{
		Node* grandparent = parent->_parent;
		if (parent == grandparent->_left)
		{
			Node* uncle = grandparent->_right;

			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandparent->_col = RED;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_left)
			{
				RotateR(grandparent);
				grandparent->_col = RED;
				parent->_col = BLACK;
				break;
			}
			else if (cur == parent->_right)
			{
				RotateL(parent);
				RotateR(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
		else
		{
			Node* uncle = grandparent->_left;
			if (uncle && uncle->_col == RED)
			{
				grandparent->_col = RED;
				uncle->_col = parent->_col = BLACK;

				cur = grandparent;
				parent = cur->_parent;
			}
			else if (cur == parent->_right)
			{
				RotateL(grandparent);
				parent->_col = BLACK;
				grandparent->_col = RED;
				break;
			}

			else if (cur == parent->_left)
			{
				RotateR(parent);
				RotateL(grandparent);
				cur->_col = BLACK;
				grandparent->_col = RED;
				break;
			}
			else
			{
				assert(false);
			}
		}
	}
	_root->_col = BLACK;
	
	return make_pair(iterator(curit), true);
}

map的[]重载

[]直接返回插入节点的值，如果[]内的key值不在红黑树中，就直接插入，若在其中也有进行修改，最后返回iterator的first的second

template <class K, class V>
class map
{
public:
	pair<iterator, bool> insert(const pair<const K, V>& kv)
	{
		return _t.Insert(kv);
	}
	
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));

		return (ret.first)->second;
	}
private:
	RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

由于博主的能力有限，部分讲解不到位，等我巩固知识后再做修正！希望大家指正！本篇博文的分享到这里就结束了，感谢大家的支持！