封装map和set

文章目录

封装
map
set
红黑树
- 成员变量
- 节点定义
- KeyOfT
- MapKeyOfT
- SetKeyOfT
begin() && end()
迭代器
- 迭代器类
- operator++
- operator- -
insert

封装

map和set的底层都是通过红黑树来实现的，那么是怎么做到共用同一份代码，但让map存储的是键值对，set只存储键值的呢？

map

template<class K, class V>
class map
{
private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

set

template<class K> 
class set
{
private:
		RBTree<K, K, SetKeyOfT> _t;	
	};
}

上面的map和set的成员变量类型分别是RBTree<K, pair<const K, V>, MapKeyOfT>和RBTree<K, K, MapKeyOfT>,它在实例化时会调用底层的红黑树，对于map而言它调用的红黑树会将节点存储的value实例化成键值对pair<const K, V>，而对于set它会将节点实例化成键值。

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

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	//pair<K, V> _kv;
	T _data;
	Colour _col;

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)//新节点默认为红色
	{

	}
};

红黑树

成员变量

// set->RBTree<K, K, SetKeyOfT> _t;
//map->RBTree<K, pair<K, V>, MapKeyOfT> _t
template <class K, class T, class KeyOfT>
struct RBTree
{
	//typedef RBTreeNode<K, V> Node;
	typedef RBTreeNode<T> Node;
public:
	//同一个类模板,传不同的实参实例化出的不同类型
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T, const T*, const T&> const_iterator;
	private:
	Node* _root = nullptr;
public:
	size_t _rotateCount = 0;//旋转次数
};

通过上面我们会发现，对于set而言T会实例化成key，而对于map它的T会实例化成pair<K, V>,那么我们就又会有个疑问，这不都已经把key都给传过来了吗？为什么还要一个单独的模板参数K，它是为了解决例如为了满足find函数，因为我们在找一个值的时候，是按Key去找的，因此给一个K模板参数会使得find更方便还有erase函数等

节点定义

这个节点可能存的是关键字K，也可能是键值对<K,V>结构
节点成员变量存储的数据要怎么设计呢？是存储K，还是<K,V>呢？
不怕，我们有模板参数，我们只需要传递给该节点一个类型就可以了，如果是set我们就传递K对应类型就可以了，如果是map我们就传给他一个pair<K, V>类型

enum Colour
{
	RED,
	BLACK
};

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)//新节点默认为红色
	{

	}
};

因此如果是map这里的_data实例化出的类型就是pair<K, V>，如果是set它的类型就是K
为什么新插入的节点默认设为红色？
因为如果将新插入的节点设为黑色的话，那么每一条路径黑色节点都与该路径黑色节点个数不同，就要调整所有路径，而设为红色，都有可能不需要调整的情况，所以综合考虑，新插入节点设为红色对我们来说更加有利。

KeyOfT

为什么要在第一层封装时，设计出仿函数mapKeyOfT和setKeyOfT？
因为底层实现是相同的，我们在插入一个新的元素时，都要用K去比较，然后找到合适的位置进行插入，对于set而言它的K就是节点中的_data，而对于map而言，_data类型是键值对，它的K是_data.first，如果是这样的话，我们在底层就不容易实现一份代码既可以对set的K比较，又要同时满足map的K比较。因此我们添加了一个仿函数，来获取map和set的K值。

MapKeyOfT

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

SetKeyOfT

struct SetKeyOfT
{
	const K& operator()(const K& key)
	{
		return key;
	}
};

因此在插入等操作需要进行比较时，我们直接调用仿函数来获取该节点对应的K值即可。
那么为什么不直接在仿函数中比较好，而是只返回对应的key值呢？因为我们不仅要满足K与K，键值对与键值对的比较，还要满足K与键值对.first的比较，当然你要想在这比较好也可以，只不过就要实现多份仿函数重载例如const K& operator()(const pair<K, V>& kv，const K& key），const K& operator()(const K& key， const pair<K, V>& kv）

Node* cur = _root;
Node* parent = nullptr;
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// if(kv.first == cur->_kv.first)
	{
		//assert(false);
		//return false;
		return make_pair(iterator(cur), false);
	}
}

begin() && end()

第一层：
map

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

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

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

	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}

set

public:
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}

set无论是普通对象还是const对应调用的都是const迭代器，因此我们只写一份const对象调用即可
红黑树对应的底层实现:
树的遍历是中序遍历，是有序的，因此begin的返回值是最左边的，在左小右大的情况下就是返回最小的节点指针，而end()返回值是nullptr

public:
	//同一个类模板,传不同的实参实例化出的不同类型
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T, const T*, const T&> const_iterator;

	//返回的是迭代器对象?
	iterator begin()
	{
		Node* leftNode = _root;
		while (leftNode && leftMin->_left)
		{
			leftNode = left->_left;
		}
		return iterator(leftNode);
	}

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

	const_iterator begin() const
	{
		Node* leftNode= _root;
		while (leftNode&& leftNode->_left)
		{
			leftNode= leftNode->_left;
		}
		return const_iterator(leftNode);
	}

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

迭代器

我们先解决一个重要问题，map和set是怎么做到共用一份代码的情况下set不允许修改但map.second允许被修改的？在红黑树底层做的？不是，是在第一层封装时进行实现的。
map

template<class K, class V>
class map
{
private:
	RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

set

template<class K> 
class set
{
private:
	RBTree<K, K, SetKeyOfT> _t;
};

注意map中的pair<const K, V>它的K是const的,因此这就首先保证了无论是普通迭代器还是const迭代器，map的K是一定不会被修改的。那么set又是怎么做到它的K无论是普通迭代器还是const迭代器都不允许被修改的呢？
map

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

set

public:
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

set在对迭代器进行typedef时，它是让普通迭代器和const迭代器在实例化时，都实例化成了const迭代器，因此就做到了K无论是普通迭代器还是const迭代器都不允许被修改，而map普通迭代器就是普通迭代器，const迭代器就是const迭代器。

迭代器类

template <class T, class Ptr, class Ref>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ptr, Ref> Self;
	typedef __TreeIterator<T, T*, T&> Iterator;

	__TreeIterator(const Iterator& it)//构造函数
		:_node(it._node)
	{

	}

	Node* _node;

	__TreeIterator(Node* node)//构造函数
		:_node(node)
	{}

operator++

++是中序遍历，找到下一个节点

Self& operator++()
{
	if (_node->_right)
	{
		// 右树的最左节点(最小节点)
		Node* subLeft = _node->_right;
		while (subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		_node = subLeft;
	}
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点
		while (parent && cur == parent->_right)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}

		_node = parent;
	}

	return *this;
}

就是一直向上去寻找直到找到当前cur节点是父亲的左孩子的那个节点，就是下一个要访问的节点

operator- -

–是倒着的中序遍历，也就是右根左

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

		_node = subRight;
	}
	else
	{
		// 孩子是父亲的右的那个节点
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_left)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}

		_node = parent;
	}
	return *this;
}

就是一直向上去寻找直到找到当前cur节点是父亲的右孩子的那个节点，就是下一个要访问的节点

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

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

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

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

Ref就是引用，Ptr就是指针

insert

insert是上层的接口，用于去插入一个节点
map

pair<iterator, bool> insert(const pair<K, V>& kv)
{
	return _t.insert(kv);
}

set

pair<iterator, bool> insert(const K& key)
{
	pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.insert(key);
	return pair<iterator, bool>(ret.first, ret.second);
}

map就是直接将这个键值对插入底层红黑树所得到的返回值返回即可，而对于set而言插入并没有这么简单，他不能直接返回红黑树的返回值，他还要借助一个中间变量将红黑树的返回值做一些修改才可以返回，这是为什么呢？
set中直接返回底层Insert的返回值出现的问题如下

pair<iterator, bool> insert(const K& key)
{	
	return _t.Insert(key);
}

在这里插入图片描述
出现该错误的原因是类型不匹配，注意这是个pair类型，不是指针或引用，不能由普通对象隐式转化为const对象，不匹配就是不匹配，那么为什么会出现这种问题，而对于map而言就可以直接把红黑树中Insert的返回值作为insert的返回值？
这是因为在set中无论是普通迭代器还是const在底层调用的都是const迭代器，这里_t是普通对象，当它调用底层Insert函数时，其实返回的pair对象first是普通迭代器，但是在set中返回值pair<iterator, bool> 的first是const迭代器，因此就会出现上面的问题，pair对象是一个整体，不能把first单拿出来说它是指针，可以由普通转换为const，pair对象就可以。
因此现在的问题也就是底层Insert返回的pair对象是普通的对象，我们要把这个返回值转换为const的然后去返回到上层，但是不能直接返回因为pair对象不支持隐式类型转换为const对象
如何解决？

pair<iterator, bool> insert(const K& key)
{
	pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
	return pair<iterator, bool>(ret.first, ret.second);		
}

我们把Insert的返回先保存起来，注意这里pair对象的first的类型为
typename RBTree<K, K, SetKeyOfT>::iterator，是底层红黑树对应的迭代器类型，也就是此时ret的first类型是普通的迭代器，保证了pair对象ret与Insert返回值对象的类型匹配。
在这里插入图片描述
接下来又会出现这种问题，为什么？因为此时没有匹配的构造函数

typedef __TreeIterator<T, T*, T&> Iterator;

__TreeIterator(const Iterator& it)//构造函数
	:_node(it._node)
{
}