【C++】map和set的封装

迈不过友情╰ 2024-04-26 11:02 82阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

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

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一.封装的大体思路
 *  二.封装的具体实现：
 *   *  1.结点的封装：
     *  2.iterator的封装：
     *   *  set的封装:
         *  map的封装：
     *  3.插入函数的修改：
     *  4.insert在map和set里面发封装：
     *  5.map的\[\]:
 *  总结

## 前言 ##

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

## 一.封装的大体思路 ##

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

## 二.封装的具体实现： ##

### 1.结点的封装： ###

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

**map：**  
![在这里插入图片描述][f90576e4cfcd4a30a1a7c31543d4739b.png]  
**set：**  
![在这里插入图片描述][0ff7461c1544458189bd9274f9bfbfd4.png]

**修改后的RBtree:**  
![在这里插入图片描述][6c38f19aaac54432a4d3711648529ccd.png]  
**结点修改后：**

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)
    	{
        }
    };

此时就是我们每一个结点存的就是一个T类型，而不是在结点里面构造pair类型。因为其实我们结点里面本身就是存储的是`key`或者`pair<key,value>`的值，如果我们自己在节点里面构造`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;
    	}
    };

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

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;
    	}

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

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);
    	}
        
        // ... ...
        // ... ...
    }

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

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

#### set的封装: ####

![在这里插入图片描述][a66cc67a5d994449aaf0a8442f853328.png]  
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类型

这里要强调的就是这个模板类里面的`：：`因为会产生歧义，一定要标明是不是类型，加一个`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迭代器接收。

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

**方案1：**

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

这里加`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;
    }

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

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

#### map的封装： ####

![在这里插入图片描述][16ab49a267b04b1a973f572e7e1cb311.png]  
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有体现
    	};

### 3.插入函数的修改： ###

在前面的map和set的使用中，我们介绍了实际里面insert的返回值，是一个`pair<iterator,bool>`类型，所以我们要对之前的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);
    
    	}

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

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

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

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可以修改

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

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

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

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

但是set就会有问题了：

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

在这里，我们的`pair<iterator,bool>`里面的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);
    		}

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

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

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

如果没有加这个构造函数：  
![在这里插入图片描述][14d0f2135763490eab275d16bd7eaff8.png]

### 5.map的\[\]: ###

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

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

*  如果不存在，则插入值，并返回这个值的value的引用便于修改。
 *  如果存在，就返回该值的value便于你修改

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

## 总结 ##

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

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

list<int> ss;
    list<int>::const_iterator it = ss.begin();

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

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

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

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

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/aab186fddbb74ccda6b640ee9cae4806.gif
[C]: https://blog.csdn.net/qq_74310471/category_12289978.html
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/94a562a7c9114f569b266555d4b57b31.gif
[fc44788ed6904110a73e1fd52804d942.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/735eb7af619c4d2b8e86eb862923b2da.png
[f90576e4cfcd4a30a1a7c31543d4739b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f3fc2a912ba841c59f13329474f3acec.png
[0ff7461c1544458189bd9274f9bfbfd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/01d5a5bcb29d453183d624d612b97439.png
[6c38f19aaac54432a4d3711648529ccd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/79e5504a04894fef81f86b8b58abe34c.png
[0cbc099d231b4632886b7f14c03bdfc8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c4e8a48e9b444c669b2afe61a58ace3c.png
[800ce06c3216447aa0057d6a053514d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ab4f748594594d308278bc1b42bcc3f0.png
[a66cc67a5d994449aaf0a8442f853328.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8ed11b6bde4d48e59bc00dc16829c1f7.png
[16ab49a267b04b1a973f572e7e1cb311.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5a5365b326da42238c56aa3fb367e948.png
[14d0f2135763490eab275d16bd7eaff8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/30f5e2428c5540d6acc9feebfd2b6a8a.png
[Link 2]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[C 1]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 5]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Linux]: https://blog.csdn.net/qq_74310471/category_12291120.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/21886d4a572d47cbb2634f54cfdc1da6.gif