• 【C++】map和set的封装

    在这里插入图片描述

    🚀write in front🚀
    📜所属专栏： C++学习
    🛰️博客主页：睿睿的博客主页
    🛰️代码仓库：🎉VS2022_C语言仓库
    🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
    关注我，关注我，关注我，你们将会看到更多的优质内容！！

    在这里插入图片描述

    文章目录

    前言

      前面我们学习了红黑树的实现，而map和set的底层就是红黑树，那么我们如何使用封装map和set呢？这里我们主要是学习源码里面如何封装，我有点进入误区就是为什么不那样那样封装，其实源码这样封装肯定有他的道理，我想的怎么样封装到后面肯定会出现问题，所以一定不要纠结。因为这里确实很复杂，所以在写这篇博客的时候真的很痛苦，求大家给个赞吧呜呜呜。

    一.封装的大体思路

      我们通过查看源码，发现map和set的底层都是红黑树，用的同一个类模板，通过控制传不同的模板参数，从而实例化出不同的类。其实这里的红黑树就相当于一个适配器,通过我们的封装就可以使用这棵红黑树来帮我们解决问题。
    在这里插入图片描述

    二.封装的具体实现：

    1.结点的封装：

    在这里插入图片描述
    通过这张图我们可以发现，红黑树在map和set里面肯定生成了不同的类，但是set只有一个key的值，此时如果要与我们之前传的对应，这里的V对于map而言就要改成pair。其实这里就是为了适应set只用key一个值。

    map：
    在这里插入图片描述
    set：
    在这里插入图片描述

    修改后的RBtree:
    在这里插入图片描述
    结点修改后：

    template<class T>
struct RBtreeNode
{
	RBtreeNode<T>* _left = nullptr;
	RBtreeNode<T>* _right = nullptr;
	RBtreeNode<T>* _parent = nullptr;

	T _data;

	Colour _col = RED;
	RBtreeNode(const T& data) :_data(data)
	{}
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

      此时就是我们每一个结点存的就是一个T类型，而不是在结点里面构造pair类型。因为其实我们结点里面本身就是存储的是key或者pair的值，如果我们自己在节点里面构造pair的值，后面的有些操作就不好处理。

    2.iterator的封装：

      和list的迭代器一样，map和set里面的iterator也要自己封装。这里为了区分const迭代器和普通迭代器，也是通过传入模板的类型来构造不同的迭代器。

    这里有三个模板参数，Ptr和Ref可以通过传过来的是普通参数还是const参数来控制采用什么样的迭代器（普通迭代器或者const迭代器）；同时也为map中pair的两个参数通过了很好的访问方式Ref operator*()、Ptr operator->()

    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;
	Node* _node;
	//根据实例化的迭代器选择是构造还是拷贝构造
	__TreeIterator(const Iterator&it)
		:_node(it._node)
	{}

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

	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;
	}
	private:
	Node* _node;
	}
};

    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    随后我们要实现++和–操作，其实++和–操作就是二叉遍历的一个另外一种过程，因为遍历的时候是有序的，说明begin是最左结点，end是空结点，与中序（左根右）不同，这里的访问顺序是从已经访问到最左结点，开始回溯到根和右结点。方法如下：
    在这里插入图片描述
    在这里插入图片描述

    self& operator++()
	{
		//若右边不为空：找到右边的子树的最左结点
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		//若右边不为空，就要找到父亲（什么时候叫找到父亲呢？一定是左子树遍历完了才找父亲，所以说找到父亲的左子树的第一个结点之后才算找到！）
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent)
			{
				if (parent->_left == cur)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
		}
		return *this;
	}


	self& operator--()
	{
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent)
			{
				if (parent->_right == cur)
				{
					
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
			
		}
		return *this;
	}

    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    随后在红黑树里面使用迭代器，便于外部使用。

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

public:
	//同一模板，不同参数实例化的不同的类型
	typedef __TreeIterator<T, T*, T&> iterator;
	typedef __TreeIterator<T, const T*, const T&> const_iterator;	//const迭代器

	//迭代器
	iterator begin()
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return leftMin;
	}

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

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

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
    
    // ... ...
    // ... ...
}


    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    在这里我们要明白的是，不同模板里面，如果有const值，那么两个模板是不一样的类型！！不能相互接收！！模板类要模板参数每一个参数都相同才能相互接收值。

    那么，在map和set类里面该如何封装iterator呢？

    set的封装:

    在这里插入图片描述
    set源码里面普通迭代器和const迭代器全部都是红黑树里面的const迭代器，所以这里的重命名是这样的：

    typedef typename RBtree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBtree<K, K, SetKeyOfT>::const_iterator const_iterator;
//这里的const_iterator和iterator是同一个类型，都是const_iterator类型

    • 1
    • 2
    • 3

    这里要强调的就是这个模板类里面的：：因为会产生歧义，一定要标明是不是类型，加一个typename

    但是这里就会出问题：
    按照正常的迭代器应该这样写的：

    //错误写法：
		const_iterator begin()const
		{
			return _t.begin();
		}

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

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

		iterator end()
		{
			return _t.end();
		}
//这样的话除非set是const类型，都只会调用没有const修饰的那个begin，此时t返回的iterator就是普通迭代器，无法通过const迭代器接收。


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

    但是这里却不行，因为我们的_t在调用begin()和end()函数的时候，因为_t的类型不是const，他只会调用普通迭代器的begin()和end()，而set里面全都是const_iterator。下面有两种解决方案：

    方案1：

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    这里加const就修饰了*this,然后这个函数里面*this的类型就变成了const *this（范围变小），也就是set里面的所有东西的类型都变成const了，t的类型也变成了const，在用t调调用begin()，此时传的t的this指针类型就是const *this,就会调用const_iterator的那个begin()。

    方案2：
    在迭代器里面多写一个构造函数,这个构造函数可以用普通迭代器初始化const迭代器，解决了普通迭代器不能初始化const迭代器的问题。

    typedef __TreeIterator<T, T&, T*> iterator
__TreeIterator(const iterator& it) 
{
	_node = it._node;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • const迭代器实例化，用普通迭代器初始化，此时是构造函数
    • 普通迭代器实例化，用普通迭代器初始化，是拷贝构造函数
    • const迭代器实例化，用cosnt迭代器初始化，是调用系统自己生成的拷贝构造函数

    这个地方是一个重点！！！

    map的封装：

    在这里插入图片描述
    map的key值是不允许修改的，而value是允许修改的，使用有const修饰pair里面的key值。这里的封装就和普通迭代器一样就可以了：

    
template<class K,class V>
	class map
	{
	private:
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& key)
			{
				return key.first;
			}
		};
		RBtree<K, pair<const K, V>, MapKeyOfT>_p;//key不能修改，value可以修改
	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 _p.begin();
		}
		iterator end()
		{
			return _p.end();
		}
		const_iterator begin()const
		{
			return _p.begin();
		}
		//这里加const首先是表示const迭代器指向的值不能修改（const self *this)，并且要和普通iterator重载，就要参数不同
		const_iterator end()const
		{
			return _p.end();
		}

		//!!!!const int*可以接收int*也可以接收const int*，但是当有int*的时候，就会优先构成重载,在test.cpp有体现
	};

    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    3.插入函数的修改：

      在前面的map和set的使用中，我们介绍了实际里面insert的返回值，是一个pair类型，所以我们要对之前的insert进行修改：

    pair<iterator,bool> Insert(const T& data)
	{
		Node* parent = nullptr;
	    Node* cur = _root;
		if (cur == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		KeyOfT get;
		//找到位置：
		while (cur)
		{
			if (get(cur->_data) > get(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (get(cur->_data) < get(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}
		//插入：
		cur = new Node(data);
		cur->_col = RED;
		if (get(parent->_data) < get(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		Node* newnode = cur;
		//修改颜色：
		//如果为黑色就已经正确了，当然前提是parent不为空
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)//为什么要分左右？  找到uncle！！
			{
				Node* uncle = grandfather->_right;

				//uncle为红的时候：
				if (uncle && uncle->_col == RED)
				{
					//变色
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle不存在或uncle为黑
				else
				{
					if (parent->_left == cur)
					{
						//右旋
							 //g
						   //p
						 //c

						   //p
						//c    g
						RotateR(grandfather);
						//调颜色：
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//左右旋
						//    g
						//   p
						//		c

						  //    g
						  //  c
						  //p

							// c
						  //p     g
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else  //为什么要分左右？  找到uncle！！
			{
				Node* uncle = grandfather->_left;

				//uncle为红的时候：
				if (uncle && uncle->_col == RED)
				{
					//变色
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;
					//向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				//uncle不存在或uncle为黑
				else
				{
					if (parent->_right == cur)
					{
						//左旋
						 //g
						 //	  p
						 //      c

						RotateL(grandfather);
						//调颜色：
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//右左旋：
						 //g
							//  p
						 //c
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}

		}
		_root->_col = BLACK;

		return make_pair(iterator(newnode),true);

	}

    • 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
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153

    这里出现的问题就是，对于set我们可以直接用key比较大小，但是对于map传的却是pair，这个时候到底该如何比大小呢？这个时候仿函数的意义就体现出来了。

    我们可以在set里面定义这样的仿函数，然后把定义的这个类当作一个类型传到模板里面去

    	struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
		RBtree<K, K, SetKeyOfT> _t;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    map也是一样的：

    	struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& key)
			{
				return key.first;
			}
		};
RBtree<K, pair<const K, V>, MapKeyOfT>_p;//key不能修改，value可以修改

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    事实上这里set在这里写这个仿函数只是工具人（就相当于你陪你你女朋友逛街一样，只是一个陪伴的效果）

    4.insert在map和set里面发封装：

    map里面很正常，直接封装就🆗了，因为他的迭代器没有出什么幺蛾子：

    pair<iterator,bool> insert(const pair<const K, V>& data)
		{
			return _p.Insert(data);
		}

    • 1
    • 2
    • 3
    • 4

    但是set就会有问题了：

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

    • 1
    • 2
    • 3
    • 4

    在这里，我们的pair里面的iterator是const_iterator类型，而我们Insert返回的是普通的迭代器,此时pair就不能相互接收，怎么办呢？

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

    • 1
    • 2
    • 3
    • 4
    • 5

    在这里我们自己构造一个const迭代器的pair，但是这里有一个点非常重要！！！我们迭代器里面必须有普通迭代器构造const迭代器的那个函数！！也就是上面的方案2：

    typedef __TreeIterator<T, T&, T*> iterator
__TreeIterator(const iterator& it) 
{
	_node = it._node;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    如果没有这个函数，我们的pair在进行构造时也无法让普通迭代器转成const迭代器。

    如果没有加这个构造函数：
    在这里插入图片描述

    5.map的[]:

    在封装完insert之后，就可以对map的[]进行操作了：

    	V& operator[](const K& key)
		{
			auto ret = insert(make_pair(key, V()));
			return ret.first->second;
		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 如果不存在，则插入值，并返回这个值的value的引用便于修改。
    • 如果存在，就返回该值的value便于你修改

    当然对于const map,大家在写一个const版本的[]就可以了。

    总结

    这里要总结几个小点，我搞混淆的点：

    1. 对于重载，参数类型为const int和int的两个函数是不能构成重载的，因为他们可以相互接收（拷贝嘛），而const指针和const引用就可以构成重载，因为他们两个在接收的时候会有权限问题。
    2. 对于为什么可以这样：
    list<int> ss;
list<int>::const_iterator it = ss.begin();

    • 1
    • 2

    一开始我是觉得模板传参不同，肯定不能相互接收呀，确实是这样，但是如果我们写了一个可以用普通迭代器构造const迭代器的构造函数，这个问题就可以迎刃而解！！

    这能说这篇文章真的干货满满，大家好好学吧呜呜呜

      更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

    专栏订阅：
    每日一题
    C语言学习
    算法
    智力题
    初阶数据结构
    Linux学习
    C++学习
    更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

    在这里插入图片描述

  • 相关阅读:
    【蓝桥杯选拔赛真题26】python统计字符个数 青少年组蓝桥杯python 选拔赛STEMA比赛真题解析
    LeetCode(力扣)860. 柠檬水找零Python
    前端知识3-JavaScript
    Hive数据定义语言-DDL-建表高阶语法（内外部、分区、分桶、事务、视图、物化视图）
    【spring cloud】(七)消息驱动——springcloud Stream
    Ubuntu下安装anaconda流程
    小抄 20240605
    华为eNSP配置专题-路由策略的配置
    [锁]：乐观锁与悲观锁
    Dajngo01_Django框架基础与环境搭建
  • 原文地址：https://blog.csdn.net/qq_74310471/article/details/133148331