C++语法——map与set的封装原理

目录

一.数据类型封装

（一）.封装方式

（二）.封装后如何取key比较

 二.迭代器封装

（一）.底层迭代器（红黑树中）

①迭代器++

②迭代器-- 

（二）.begin&end&const

---

一.数据类型封装

（一）.封装方式

我们知道，map与set所使用的都是红黑树，但是map是key&value模型，set是key模型。

map需要传两个类型而set只用传一个类型，这在底层红黑树中该怎么兼容呢？

透过SGI版stl_tree.h我们可以看到，红黑树有两个模板参数分别表示key和value。重点来了：

对于map而言需要传入key和pair分别给红黑树的key和value。

set需要传key和key给红黑树的key和value。

再看map与set源码（进行部分截取）：

 如果自制的话，大致如此：

template<class K, class V>
class Map
{
	typedef rb_tree, MapOfV>> tree;
public:
	//...
 
private:
	tree _t;
};

template<class K>
class Set
{
	typedef rb_tree> tree;
public:
	//...
 
private:
	tree _t;
};

（二）.封装后如何取key比较

但是这种封装有一个问题，就是在底层红黑树中，是直接拿value进行比较，那这该怎么办呢？

用仿函数取value中key值来解决。

对于map而言，传仿函数给红黑树，调用仿函数取value（实际是pair）中的key值。

对于set而言，key和value中的值实际上都是key，也传仿函数取即可。

因此，对于上述代码我们看到map和set分别传入了仿函数MapOfV和SetOfV。

仿函数均在上层中（map/set）实现，传入底层红黑树。

代码实现如下（简易）：

template<class K, class V>
//传入分别是key和pair
//typedef rb_tree, MapOfV>> tree;
class MapOfV
{
public:
	K operator()(V kv) const
	{
		return kv.first;
	}
};

template<class K>
//typedef rb_tree> tree;
class SetOfV
{
public:
	K operator()(K k) const
	{
		return k;
	}
};

 二.迭代器封装

因为map和set底层都是红黑树，因此迭代器实现在红黑树中（底层），而map和set只是调用红黑树的迭代器。

（一）.底层迭代器（红黑树中）

因为红黑树也是由一个个节点组成，这就很容易想到list的迭代器。list迭代器是用类封装，迭代器内部定义一个指针指向节点，对迭代器的操作底层是对迭代器内部指针的操作。

红黑树的迭代器与之类似，也是使用一个类来表示迭代器，内部有一个指向树节点的指针。只要了解过list迭代器都能想出来，不了解可以看看这篇文章哦：为什么List的迭代器是类模板？

对于解引用*和箭头->的封装与list相同，直接转化成对节点指针的操作。

关键在于++和--。 

①迭代器++

红黑树也是二叉树，我们就直接以二叉树为例：

 这里要分两种情况： 

 第一种：节点有右子树，此时要向下走。

以1号节点为例，因为有右子树，++后就是6号节点？——错！

二叉树迭代是前序遍历的方式，++后应该是5号节点，即右子树的最左节点！

第二种：节点没有右子树，此时要向上走。

对比3号和5号节点，都是叶子节点，但是3号节点++后是1号节点，5号++后是6号节点。

得出结论：如果当前节点是父节点的左子树，那++后就是父节点。如果是右子树，那么需要向上找直到当前节点是父节点左子树，此时父节点是++后节点。

如果是节点7那么++会一直判断到根节点4，因此，迭代器end()可以设置为root的父节点（null）。

原理很简单，如果是右子节点那说明对于父节点而言你就是++后会找到的节点，但是对于自己而言++后就不可能是父节点。

代码如下：

Self operator++()
{
	goBack();
	return *this;
}
void goBack()
{
	if (_node->right)//如果右子节点不为空
	{
		Node* right = _node->right;
		while (right->left)//直到找到右子树最左节点
		{
			right = right->left;
		}
		_node = right;
	}
	else//右子树为空
	{
		Node* parent = _node->parent, * cur = _node;
		while (parent && cur == parent->right)//直到cur是parent的左子节点为止
		{
			cur = parent;
			parent = cur->parent;
		}
		_node = parent;
	}
}

②迭代器-- 

有了++的理解，--操作就简单了。

还是以该树为例：
 也要分两种情况：
第一种：有左子树，向下走。

以根节点4为例，--之后不是节点2而是节点3。对于有左子树的节点而言，--之后的节点是左子树的最右子节点。

第二种：没有左子树，向上走。

对比节点3和节点5，节点3--之后是节点2，节点5--之后是节点4。可以看出，如果节点是父节点的右子节点，那么--之后就是父节点。但如果是左子节点，那么需要向上判断直到是父节点的右子节点为止。或者如节点1一样，一直判断到根节点为止。

其原理就是如果是父节点的左子节点，那么说明父节点在自己之后，如果是右子节点那么说明在父节点之后。

代码如下：

Self operator--(int)
{
	Self it(_node);
	goHead();
	return it;
}
void goHead()
{
	if (_node->left)//有左子树
	{
		Node* right = _node->left;
		while (right->right)//直到左子树的最右子节点
		{
			right = right->right;
		}
		_node = right;
	}
	else//无左子树
	{
		Node* parent = _node->parent, * cur = _node;
		while (parent&& cur = parent->left)//直到cur是parent的右子节点
		{
			cur = parent;
			parent = cur->parent;
		}
		_node = parent;
	}
}

（二）.begin&end&const

迭代器的begin和end只能在rb_tree中实现，对于begin而言，返回红黑树最左节点的迭代器，end返回root的父节点迭代器（空节点迭代器）。

对于const，首先我们应该知道不管map还是set均不支持对key的修改。

但在实现上map和set大有不同。

map采用在传入时就传入const key，而set采用将迭代器都使用底层const迭代器。

用几个小时来制定计划，可以节省几周的编程时间—— 未名

---

如有错误，敬请斧正