【C++】用红黑树封装map、set

1. 红黑树

• set是K模型，map是KV模型，二者底层都是使用红黑树来实现的，所以我们可以将红黑树设置为模板，即：set、map复用同一个类模板的红黑树。

1.1 模板参数的控制

1.1.1 Value

• Value决定你是k模型的set、还是KV模型的map。

enum Color {  //枚举，一一列举出事物具有的所有可能
	Red,  //枚举常量，给枚举变量进行赋值
	Black,
};

template<class T>//红黑树的节点
struct RBTreeNode {
	typedef RBTreeNode<T> Node;

	//三叉链-》优点：便于查找孩子、父亲节点
	Node* _left;      //该节点的左孩子
	Node* _right;    //该节点的右孩子
	Node* _parent;  //该节点的父亲，便于向上更新
	T _data;
	Color _col;

	RBTreeNode(const T& data, Color col = Red)  //构造函数
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(col)  //默认新插入节点的颜色为红色
	{ }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Value决定你是k模型的set、还是KV模型的map
template<class K, class T, class KeyOfT> 
class RBTree {  
public:
	typedef RBTreeNode<T> Node;
};
1
2
3
4
5
6

template<class K>
class set{   //K模型
public:   
       
private:  //set中的key不允许被修改
		RBTree<K, const K, SetKeyOfT> _t;  //红黑树对象
	};
}
1
2
3
4
5
6
7
8

template<class K, class V>
class map {   //KV模型  
public:

private:   //map中的key不允许被修改
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;  //红黑树对象
	};

};
1
2
3
4
5
6
7
8
9

1.1.2 KeyOfValue

• KeyOfT : 取出Value对象中的key。

// KeyOfT : 取出Value对象中的key
template<class K, class T, class KeyOfT> 
class RBTree {  };
1
2
3

struct SetKeyOfT{   
	const K& operator()(const K& key)
	{
		return key;  //key
	}
};
1
2
3
4
5
6

struct MapKeyOfT {
	const K& operator()(const pair<K, V>& kv)
	{
		return kv.first;  //pair中的key
	}
};
1
2
3
4
5
6

1.2 正向迭代器

1.2.1 构造函数

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/705989