【C++】从零开始map与set的封装

2024-05-28 08:27:10 浏览数 (2)

1 前言

为了map与set 的封装，我们进行了非常充足的知识储备！！！

首先，为了了解map 与 set 的底层原理我们开始学习二叉搜索树,二叉搜索树在二叉树的基础上增添了：

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
  • 注意通常二叉搜索树不会有相同的键值

这样可以在一定程度上满足高效搜索的需求，但是在极端的情况（单子树情况）其效率会下降到O(n)。因此就有了改进的二叉搜索树：AVL树和红黑树。他们都增加一些特性使其最大程度上近似平衡二叉树！

AVL 树 和 红黑树 都是在保持二叉搜索树基本性质的基础上，通过旋转和重新平衡等操作，确保树的高度保持在一个相对平衡的状态，从而保证了操作的时间复杂度始终为 O(logn)。它们的出现大大提高了二叉搜索树在实际应用中的性能和稳定性。

AVL树增加了以下特性：

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1 / 0 / 1 )

在平衡因子超出要求就会进行旋转，旋转分为：右单旋 ，左单旋，左右双旋，右左双旋。

红黑树加入以下特性:

  • ⚠️每个节点要么是红色，要么是黑色。
  • ⚠️根节点必须是黑色的。
  • ⚠️如果一个节点是红色的，则它的两个子节点必须是黑色的。
  • ⚠️对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。
  • ⚠️每个叶子节点都是黑色的。这里的叶子节点指的是为空的节点。

在不满足规则时也会进行旋转。但是旋转的频率比AVL树要少很多，红黑树是只是接近平衡，AVL树几乎就是平衡的！

map与set大多数情况是用来检索的工具，我们底层使用红黑树来完成map与set的封装。

进行封装之前，我们先来实现一个非常重要的东西：迭代器

2 红黑树的迭代器

迭代器的好处是可以方便遍历。如果想要给红黑树增加迭代器，需要考虑以前问题：

  1. 迭代器的框架如何实现，才能满足泛型编程的需求？？
  2. STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，这里为了方便就给nullptr。
  3. operator ()与operator–()要如何实现？这里的 和–要满足中序遍历的顺序，就不能简单的进行指针的移动了！

接下来我们来逐个实现。

首先我们来搭建一下迭代器的框架

代码语言：javascript复制
// 迭代器
//T 表示数据类型 Ref为引用 Ptr为指针
template<class T , class Ref , class Ptr>
struct _RBTreeIterator
{
	//为了方便调用，我们重命名一下
	typedef RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, Ref, Ptr> Self;
	//内部是节点指针
	Node* _node;
	_RBTreeIterator(Node* node)
		:_node(node)
	{}
	//两种指向方式
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator&()
	{
		return &_node->_data;
	}
	bool operator!= (const Self& s)
	{
		return _node != s._node;
	}
};

接下来我们来实现 和–的操作。

中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。所以在跌迭代器指向当前节点的时候，说明当前节点的左子树已经遍历完了，如果 ，就要去找右边的最左节点。如果没有右子树，说明该节点以下的部分已经遍历完了，接下来要去向上进行，找到是祖先左边的节点：

代码语言：javascript复制
//迭代器的   中序遍历的顺序
Self& operator  ()
{
	//首先，能访问到当前节点说明左子树的都已经访问过啦
	//所以就要分类讨论
	//如果右边有子树,就要去寻找右子树的最左节点
	if (_node->_right)
	{
		Node* cur = _node->_right;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		_node = cur;
	}
	//如果右边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行
	//找到祖先节点(注意祖先节点右边还没遍历)
	//此时也要进行分类讨论
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		//_node == parent->_right
		//说明parent的节点已经访问过了
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

–与 完全相反。

这样红黑树的迭代器就成功设置好了，我们的红黑树更加完美了！！！

实现了迭代器接下来我们就来实现map与set的封装

3 map与set的封装

3.1 红黑树的改进

我们先来看我们写的红黑树的节点代码：

代码语言：javascript复制
// 节点结构体
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	color _col;
	RBTreeNode(pair<K, V> kv)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_kv(kv),
		_col(Red)
	{}

};

可以发现，这个节点的设置是写死的，里面的数据就设置为了pair<K , V>。如果我们想实现set的封装还要在写一份红黑树代码，因为set的节点数据是K 。这样就太不优雅了！

为了更好实现map与set的封装，我们来看STL源码里是如何实现的吧！

可以看到STL源码中使用了非常巧妙的模版来支持我们上层的map与set:

  1. 首先最底层的节点结构体只使用一个模版参数value，用来表明储存什么数据类型，上层的红黑树通过什么value就使用使用什么
  2. 红黑树这层主要使用Key Value KeyOfValue:
    • KEY：表示键值的类型,在Findj函数里有大用处（利用Key值来寻找是否存在）！！！
    • Value:表示储存的数据类型
    • KeyOfValue：这是一个仿函数，用来从Value取出Key值。
  3. map与set这层分别有K V 和 K分别要提供给红黑树Key Value KeyOfValue：
    • map:就传给红黑树<K , pair<K,V> ...>
    • set: 就传给红黑树<K , K ...>

这样实现了上层的map与set的模版参数并不一样，却可以使用同一个底层红黑树代码！！！十分巧妙！！！

我们按照源码改进我们的红黑树：

代码语言：javascript复制
//-------------------------------------------
//---------------- 红黑树实现 -----------------
//-------------------------------------------
//-------- 适配map 与 set 的进阶版本 -----------
//-------------------------------------------
#include<utility>
enum color
{
	Black,
	Red
};
// 节点结构体
// T在这里是 pair<key , value>
template<class T>
struct RBTreeNode
{	
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	
	T _data;
	color _col;
	RBTreeNode(T data)
		:_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_data(data),
		_col(Red)
	{}

};

//适配map与set 的版本
// 迭代器
template<class T , class Ref , class Ptr>
struct _RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, Ref, Ptr> Self;

	Node* _node;
	_RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator&()
	{
		return &_node->_data;
	}
	bool operator!= (const Self& s)
	{
		return _node != s._node;
	}
	//迭代器的   中序遍历的顺序
	Self& operator  ()
	{
	}
	Self& operator--()
	{
	}
};
//K 为键值 T 为储存的结构（pair<K ,V>） KeyOfValue 是取出Key的方式
template<class K, class T , class KeyOfValue>
class RBTree
{
public:
	typedef _RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeNode<T> Node;

	Iterator begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}
		return Iterator(cur);
	}
	Iterator end()
	{
		return Iterator(nullptr);
	}

	//右单旋
	void RotateR(Node* parent)
	{
	}
	//左右双旋
	void RotateLR(Node* parent)
	{
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
	}
	//------------------
	//返回需要比较的值
	KeyOfValue kot;
	//------------------
	//插入函数	
	bool Insert(T data)
	{
	}

private:
	void _IsBalance(Node* root , int num)
	{
	}
	bool Check(Node* root, int blackNum, const int refNum)
	{
	}

	void _InOrder(Node* cur)
	{
	}
	RBTreeNode<T>* _root = nullptr;
};

注意插入函数等里面的比较方式统一改成类似kot(data) < kot(node.data)的样子哦！！！因为map与set的取出key的方式不同！！！

3.2 map的封装

实现了红黑树的改进，接下来就简单了！

在上层操作我们只需要调用对应的底层代码，给予对应的模版参数就好了！！！

  1. map 要满足K V的模版参数的传入
  2. map 要实现一个仿函数用来取出Key
  3. map 类里要有一个底层红黑树类,传入对应的模版参数<K , pair<const K , V> , MapOfValue> (注意键值不可更改哦，所以使用pair<const K , V>)
  4. map 类里要实例化一个迭代器。只需要提供基本的begin()与end()接口（直接调用红黑树的就可以），剩下 -- ！ 交给迭代器操作交给红黑树的迭代器。
代码语言：javascript复制
//----------------------------------
//----------  MAP 的实现  -----------
//----------------------------------
#include"RBTree.h"
#include<utility>

//层层递进,
//map 上层要提供 key value 键值对
//相应的要改造红黑树的代码 使其满足泛型编程
template<class K , class V>
class map 
{
	struct MapOfValue
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	typedef typename RBTree<K, pair<const K, V>, MapOfValue>::Iterator iterator;
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	bool Insert(pair<const K, V> kv)
	{
		return _t.Insert(kv);
	}
	void InOrder()
	{
		_t.InOrder();
	}
private:
	//底层是红黑树
	//需要提供对应的键值 储存结构 比较方式
	RBTree<K, pair<const K, V>, MapOfValue > _t;
};

这样就实现了map 的封装！！！

3.3 set 的封装

在上层操作我们只需要调用对应的底层代码，给予对应的模版参数就好了！！！

  1. set 要满足K 的模版参数的传入
  2. set 要实现一个仿函数用来取出Key
  3. set 类里要有一个底层红黑树类,传入对应的模版参数<K , const K , MapOfValue> (注意键值不可更改哦，所以使用 const K )
  4. set 类里要实例化一个迭代器。只需要提供基本的begin()与end()接口（直接调用红黑树的就可以），剩下 -- ！ 交给迭代器操作交给红黑树的迭代器。
代码语言：javascript复制
//----------------------------------
//----------  SET 的实现  -----------
//----------------------------------


#include"RBTree.h"
#include<utility>


//层层递进,
//set 上层要提供 key 键值
//相应的要改造红黑树的代码 使其满足泛型编程

template<class K>
class set
{
	struct SetOfValue
	{
		const K& operator()(const K& k)
		{
			return k;
		}
	};
public:
	typedef typename RBTree<K, const K, SetOfValue>::Iterator iterator;
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	bool Insert(K kv)
	{
		return _t.Insert(kv);
	}
	void InOrder()
	{
		_t.InOrder();
	}
private:
	//底层是红黑树
	//需要提供对应的键值 储存结构 比较方式
	RBTree<K, K, SetOfValue > _t;
};

这样就实现了set的封装！！！

4 总结

通过近一周的学习，我们终于将map和set从零建立起来了，这里不仅需要二叉搜索树的知识还需要AVL树和红黑树的使用！！！甚至还需要对于模版的更深理解！！！

我们写完了发现上层的map和set并没有使用多少代码，大部分是调用底层的代码，所以只有根基稳固才能走到更远！！！

map和set的封装是很值得回味的内容！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！

c++ map set 遍历 搜索

0 人点赞