• 【C++】map&set利用红黑树进行简单封装

    前言

            大家好~~~~呀！很荣幸你能点击这篇文章。本篇也是我的一份学习笔记，让我们一起共同成长吧~ing......

    C++红黑树的简单插入实现博客~

    【C++】红黑树的插入实现_柒海啦的博客-CSDN博客

    二叉搜索树的基本结构和实现博客~

    【C++】二叉搜索树_柒海啦的博客-CSDN博客_c++二叉搜索树

            本篇笔记基于红黑树的基本插入实现，实现简单的map和set的包装，掌握底层的基本原理即可~

     （嘿嘿玉子阔爱~~~）

    目录

    一、map和set的基本使用

    1.set的使用

    1.1set的模板参数：

    1.2set的迭代器：

    1.3set的修改：

    1.4set的操作：

    1.5代码测试：

    2.map的使用

    2.1map的模板参数：

    2.2map的迭代器：

    2.3map的修改：

    2.4map的操作： 

    2.5代码操作：

    二、基于插入实现的红黑树进行封装

    1.优化红黑树的模板参数

    上层代码初步实现：

    下层红黑树代码：

     2.红黑树的迭代器实现

    重载++/--运算符：

    3.map、set上层对红黑树迭代器的相关封装：

    4.mapset综合简单封装代码：

    一、map和set的基本使用

            在一开始，我们接触的C++STL容器比如：vector、list、stack、deque....这些容器的底层都是为线性序列的数据结构，存储的就是元素本身。这些就是序列式容器。

            除了序列式容器外，还有关联式容器。它也是存储数据的，只不过和序列式容器不同的是内部存储的是key-value结构的键值对，并且数据结构也是非线性的（二叉树）。而现在我们要介绍的map和set均为关联式容器。

    1.set的使用

    set文档：set - C++ Reference (cplusplus.com)

    multiset文档：multiset - C++ Reference (cplusplus.com)

    1.set是按照一定顺序进行存储的容器。

    2.set/multiset 底层数据均是的键值对。插入只需要一个key类型即可。

    3.set的元素不可重复，multiset的元素可重复。

    4.使用set的迭代器进行遍历可以得到有序序列。

    5.set的元素默认按照小于来比较，查找某个元素时间复杂度为log_2 N，并且元素不可修改。

    6.底层使用二叉搜索树-红黑树进行实现。

    （注：下述以set为准，multiset使用接口类似）

    1.1set的模板参数：

    T -  插入元素的数据类型。

    Compare - 比较仿函数。默认给的less为库中实现的小于比较。

    Alloc - 内存分配

    （上述模板在模拟实现中目前只关注T）

    1.2set的迭代器：

    （解引用返回的就是T这个元素类型） 

    1.3set的修改：

    insert -  插入T类型的元素，或者在一段迭代器区间进行插入（模拟实现只实现第一种） erase - 删除对应迭代器指向元素，或者一段迭代器区间的元素（模拟实现只实现第一种）

    1.4set的操作：

    find - 根据传入的元素返回一个迭代器。没有找到返回的就是end()。

    count - 根据传入的元素返回其出现的个数（对于multiset有效）

    1.5代码测试：

    1. void test2()
    2. {
    3. 	//set的使用 - 底层使用的是红黑树进行封装的
    4. 	set<int> s;
    5. 	int arr[] = { 4, 2, 1, 1, 4, 3, 9, 101, 87, -3 };
    6. 	// 特性：去重，迭代器访问是有序的
    7. 	for (auto e : arr) s.insert(e);
    8. 	set<int>::iterator si = s.begin();
    9. 	while (si != s.end())
    10. 	{
    11. 		cout << *si << " ";
    12. 		//*si = 2;  set不允许修改值
    13. 		si++;
    14. 	}
    15. 	cout << endl;
    16. 	set<int, greater<int>> s2;  // 第二个是配置的仿函数 - 给其底层对应key的比较大小
    17. 	for (auto e : arr) s2.insert(e);
    18. 	si = s2.begin();
    19. 	while (si != s2.end())
    20. 	{
    21. 		cout << *si << " ";  // 101 87 9 4 3 2 1 -3
    22. 		si++;
    23. 	}
    24. 	cout << endl;
    25. 	// 可删除
    26. 	s2.erase(-3);
    27. 	s2.erase(s2.begin());
    28. 	si = s2.begin();
    29. 	while (si != s2.end())
    30. 	{
    31. 		cout << *si << " ";  // 87 9 4 3 2 1
    32. 		si++;
    33. 	}
    34. 	cout << endl;
    35. 	cout << s2.count(4) << endl;  // 返回对应个数 -- 对于不可冗余的set没啥用
    36. 	// 查找，返回迭代器 set具有const，无法修改
    37. 	cout << *s2.find(87) << endl;
    38. 	//cout << *s2.find(10) << endl;  // 返回的是end
    39. 	multiset<int> ms(arr, arr + (sizeof(arr) / sizeof(arr[0])));  // 可以使用迭代器构造 - 使用的是multi 可以重复的使用元素哦~
    40. 	cout << ms.count(4) << endl;  // 2
    41. }

    运行结果： 

    2.map的使用

    map文档：map - C++ Reference (cplusplus.com)

    multimap文档：multimap - C++ Reference (cplusplus.com)

    1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素（pair）。

    2.同样的默认小于进行比较，比较的元素也key类型的元素。查找类型同样是key，时间复杂度也是log_2 N。并且key不可修改，但是对应的value可以进行修改。

    3.针对于key元素，利用迭代器遍历可以得到有序序列。

    4.支持[]进行访问。

    5.map的key不可重复，multimap的key允许重复。

    6.底层使用二叉搜索树-红黑树进行实现。

    （注：下述以map为准，multimap使用接口类似）

    2.1map的模板参数：

    Key、T - 对应键值对中的key-value。之后插入比较均以key类型元素为基准。

    Compare - 比较仿函数。默认给的less为库中实现的小于比较。

    Alloc - 内存分配

    2.2map的迭代器：

     （此时返回的迭代器类型解用引用后是个pair元素）

    2.3map的修改：

    operator[] - 

    访问对应key下标的value值。如果key不存在，那么就进行新的插入，返回值为以T类型调用的默认构造。

    at - 访问key下标对应的value值。如果key不存在，则抛异常。

    insert - 

     erase - 

    2.4map的操作： 

    find - 根据传入的元素返回一个迭代器。没有找到返回的就是end()。

    count - 根据传入的key返回其出现的对数（对于multimap有效）

    2.5代码操作：

    1. void test3()
    2. {
    3. 	// map的使用
    4. 	map m;
    5. 	m.insert(pair("China", "中国"));
    6. 	cout << m["China"] << endl;  // 重载的有[] - []功能强大
    7. 	m["Japan"] = "日本";  // 还能直接插入
    8. 	cout << m["Japan"] << endl;
    9.  
    10. 	string ar[] = {"西瓜", "苹果", "香蕉", "香蕉", "苹果", "西瓜", "苹果", "香蕉", "西瓜", "苹果", "苹果", "苹果", "西瓜", "苹果", "香蕉"};
    11. 	mapint> m2;
    12. 	for (auto e : ar)
    13. 	{
    14. 		m2[e]++;  // int() = 0 第一次就是0 + 1 = 1， 存在就++
    15. 	}
    16. 	auto it = m2.begin();
    17. 	while (it != m2.end())
    18. 	{
    19. 		cout << (*it).first << ":" << (*it).second << endl;
    20. 		it++;
    21. 	}
    22. 	cout << (*m2.find("西瓜")).second << endl;  // 同样的返回迭代器
    23. 	cout << m2.find("西瓜")->second << endl;  // 同样的返回迭代器
    24. }

    运行结果： 

     

    二、基于插入实现的红黑树进行封装

            在了解了基本map和set的基本使用后，我们可以利用之前实现的简单插入实现的红黑树进行封装，文章链接在前言哦~

    1.优化红黑树的模板参数

            首先，因为我们实现的红黑树利用的K-Value模型。为了兼容set和map的存储结构（一个只是value、一个是key - value），我们就保留K这个模板参数，利用T这个模板参数一个存储value、一个存储pair。

            那么此时插入数据就是T类型的数据。由于是上层封装，所以传到红黑树这一层，就不知道T类型究竟是value还是一个键值对。此时同样需要上层传入一个仿函数，每次控制对应类型取出对应的key值。set key就是本身，map pair->frist。

    上层代码初步实现：

    map:

    1. namespace YuShen
    2. {
    3. 	template<class K, class V>
    4. 	class map
    5. 	{
    6. 		struct MapKeyOfT
    7. 		{
    8. 			const K& operator()(const pair& kv)  // 重载()
    9. 			{
    10. 				return kv.first;
    11. 			}
    12. 		};
    13. 	public:
    14.     // ......
    15. 	private:
    16. 		RBTree, MapKeyOfT> _t; // 红黑树结构
    17. 	};
    18. }

    set：

    1. namespace YuShen
    2. {
    3. 	template<class K>
    4. 	class set
    5. 	{
    6. 		struct SetKeyOfT
    7. 		{
    8. 			const K& operator()(const K& key)
    9. 			{
    10. 				return key;
    11. 			}
    12. 		};
    13.  
    14. 	public:
    15.     // ......
    16. 	private:
    17. 		RBTree _t;
    18. 	};
    19. }

    下层红黑树代码：

    1. template<class K, class T, class KeyOfT>
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node;
    5.     // .......
    6. };
    7.  
    8. // 红黑树结点结构
    9. template<class T>
    10. struct RBTreeNode
    11. {
    12.     //......
    13. };

            此时原本的红黑树key和value模型就混在一起了，需要将所有需要取出key的地方（比如比较的地方）都要利用传入的仿函数对象进行比较，比如：

     2.红黑树的迭代器实现

            在上述的使用中，我们发现map和set都是可以控制迭代器的。实际上，它们调用的就是底层红黑树自己实现的迭代器。

            此时迭代器也就需要自己实现了。首先红黑树是一个二叉树结构，非线性结构，和list的模拟实现类似。

            其次红黑树是一个二叉搜索树。因为控制了所以结点值大于对应结点的左子树的值，小于对应结点的右子树的值的性质，所以对二叉搜索树来说，中序遍历是有序的。那么在接下来的迭代器实现中++或者--就要按照中序的性质进行实现：

    红黑树迭代器简单实现：-模板类

    模板参数：（STL迭代器三样）class T, class Ref, class Ptr （T T& T*）

    重载运算符：

            *解引用        ->箭头访问（指针）        ==/!=        ++ --

    解引用、箭头访问、== !=的简单实现：

    1. template<class T, class Ref, class Ptr>  // T T& T*
    2. struct __RBTreeIterator
    3. {
    4. 	RBTreeNode* node;
    5. 	typedef __RBTreeIterator Self;
    6.  
    7. 	__RBTreeIterator(RBTreeNode* root)
    8. 		:node(root)
    9. 	{}
    10. 	Ref operator*()
    11. 	{
    12. 		return node->_data;
    13. 	}
    14.  
    15. 	Ptr operator->()
    16. 	{
    17. 		return &node->_data;
    18. 	}
    19.  
    20. 	bool operator==(const Self& it) const
    21. 	{
    22. 		return it.node == node;
    23. 	}
    24.  
    25. 	bool operator!=(const Self& it) const
    26. 	{
    27. 		return it.node != node;
    28. 	}
    29.     // ..... ..
    30.  
    31. }

    重载++/--运算符：

            由于实现红黑树的迭代器，当前迭代器存储的结点，要让它指向++后也就是中序的下一个。我们想想中序的时候是如何进行遍历的？左子树，当前结点，右子树。所以，当到此结点后，表示此结点的左子树已经遍历过了，我们就遍历到右子树即可。

            到右子树就要找到右子树中的最左的结点。但是，如果右子树为空呢？按照之前的中序递归方式，此时就会返回到上一层也就是父节点的地方。但是以下面的的一张图为例，有着两种不同的情况：

            如果当前结点为1，那么++后就是3结点。 但是如果当前结点为4的话，那么++后的结点就应该是5结点。此时找的条件就是孩子不是父右子树的节点。一直找到空表示此时中序遍历到空了。

            -- 是完全反过来的，首先当前结点，那么右子树已经遍历过了，此时找到左子树的最右结点。如果为空，那么就找到孩子不是父左子树的结点即可。

    简单代码实现：

    1. 	Self& operator++()
    2. 	{
    3. 		// 中序访问-只不过是碎片化的进行访问
    4. 		if (node->_right)
    5. 		{
    6. 			// 找到右子树最左结点 -- 
    7. 			node = node->_right;
    8. 			while (node->_left) node = node->_left;
    9. 		}
    10. 		else
    11. 		{
    12. 			// 右子树为空，直接访问父节点吗？不一定哦，需要向上找孩子不是父亲的右结点的那个祖先
    13. 			RBTreeNode* parent = node->_parent;
    14. 			while (parent && parent->_right == node)
    15. 			{
    16. 				node = parent;
    17. 				parent = node->_parent;
    18. 			}
    19. 			node = parent;
    20. 		}
    21. 		return *this;
    22. 	}
    23.  
    24. 	Self& operator--()  // 反过来了
    25. 	{
    26. 		if (node->_left)
    27. 		{
    28. 			node = node->_left;
    29. 			while (node->_right) node = node->_right;
    30. 		}
    31. 		else
    32. 		{
    33. 			// 右子树为空，直接访问父节点吗？不一定哦，需要向上找孩子不是父亲的右结点的那个祖先
    34. 			RBTreeNode* parent = node->_parent;
    35. 			while (parent && parent->_left == node)
    36. 			{
    37. 				node = parent;
    38. 				parent = node->_parent;
    39. 			}
    40. 			node = parent;
    41. 		}
    42. 		return *this;
    43. 	}

    3.map、set上层对红黑树迭代器的相关封装：

            在实现了红黑树的迭代器后，就可以具体写出begin和end了，begin就当前红黑树存储的根结点。end只需要给一个空结点过去即可。

             map和set首先对此红黑树类型中的iterator类型进行重命名。由于是通过域访问符::进行访问的，所以编译器编译的时候不好判断其究竟是静态变量还是类型，所以类型的前面就需要加上typename表示这是一个类型以保证编译过的去：

    1. // map		
    2.     typedef typename RBTree, MapKeyOfT>::iterator iterator;
    3. // set
    4.     typedef typename RBTree::iterator iterator;

            那么对于插入insert，我们的返回值可以是一个pair，里面存放迭代器和一个bool值。插入失败就返回对应元素的迭代器和false，插入成功就返回插入新结点的迭代器和true值。

    1. 		pairbool>insert(const K& key)
    2. 		{
    3. 			return _t.Insert(key);
    4. 		}

            对于map来说，此结构还可以方便我们实现[]重载。因为在之前的使用中，我们发现对于map的[]，如果对应key数据存在就返回其对应的value值，如果不存在就会创建新的键值对。实际上就是在调用[]调用红黑树的inset，传入key和利用其V的默认构造进行插入，传入失败就说明存在元素，然后返回对应的迭代器的value值即可，插入成功同样返回迭代器的value值即可：

    1. 		V& operator[](const K& key)
    2. 		{
    3. 			pairbool> ret = _t.Insert(pair(key, V()));
    4. 			return ret.first->second;
    5. 		}

            find同样的类似实现，返回迭代器即可。

    4.mapset综合简单封装代码：

    1. // map.h
    2. #pragma once
    3. #include "RBTree.h"
    4.  
    5. // 利用自己实现的红黑树去封装map
    6. // 实验基本功能：数据不冗余，基本实现insert、[]等功能 
    7. namespace YuShen
    8. {
    9. 	template<class K, class V>
    10. 	class map
    11. 	{
    12. 		struct MapKeyOfT
    13. 		{
    14. 			const K& operator()(const pair& kv)  // 重载()
    15. 			{
    16. 				return kv.first;
    17. 			}
    18. 		};
    19. 	public:
    20. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    21.  
    22. 		iterator begin()
    23. 		{
    24. 			return _t.begin();
    25. 		}
    26. 		iterator end()
    27. 		{
    28. 			return _t.end();
    29. 		}
    30. 		pairbool> insert(const pair& kv)
    31. 		{
    32. 			return _t.Insert(kv);
    33. 		}
    34.  
    35. 		V& operator[](const K& key)
    36. 		{
    37. 			pairbool> ret = _t.Insert(pair(key, V()));
    38. 			return ret.first->second;
    39. 		}
    40.  
    41. 		iterator find(const K& key)
    42. 		{
    43. 			return _t.find(key);
    44. 		}
    45. 	private:
    46. 		RBTree, MapKeyOfT> _t; // 红黑树结构
    47. 	};
    48. }
    1. // set.h
    2. #pragma once
    3.  
    4. namespace YuShen
    5. {
    6. 	template<class K>
    7. 	class set
    8. 	{
    9. 		struct SetKeyOfT
    10. 		{
    11. 			const K& operator()(const K& key)
    12. 			{
    13. 				return key;
    14. 			}
    15. 		};
    16.  
    17. 	public:
    18. 		typedef typename RBTree::iterator iterator;
    19.  
    20. 		pairbool>insert(const K& key)
    21. 		{
    22. 			return _t.Insert(key);
    23. 		}
    24.  
    25. 		iterator begin()
    26. 		{
    27. 			return _t.begin();
    28. 		}
    29.  
    30. 		iterator end()
    31. 		{
    32. 			return _t.end();
    33. 		}
    34.  
    35. 		iterator find(const K& key)
    36. 		{
    37. 			return _t.find(key);
    38. 		}
    39. 	private:
    40. 		RBTree _t;
    41. 	};
    42. }

    另外，加上红黑树中的find实现：

    1. 	iterator find(const K& key)
    2. 	{
    3. 		Node* tmp = _root;
    4. 		KeyOfT kot;
    5. 		while (tmp)
    6. 		{
    7. 			if (key > kot(tmp->_data)) tmp = tmp->_right;
    8. 			else if (key < kot(tmp->_data)) tmp = tmp->_left;
    9. 			else return iterator(tmp);
    10. 		}
    11. 		return iterator(nullptr);
    12. 	}
  • 相关阅读:
    Mybatis 拦截器 说明和使用 （二）
    Docker kill 1无效
    Vuex概述及核心概念
    DNS基础之通过dig命令理解DNS域名解析中的A记录，AAAA记录，CNAME记录，MX记录，NS记录
    趣学算法：分治算法
    Numpy入门[18]——数组读写
    Shopee、Lazada卖家不得不看的提升销量技巧，自养号测评打造权重
    MySQL高级SQL语句
    y122.第七章 服务网格与治理-Istio从入门到精通 -- 流量治理实战进阶(八)
    Flutter开发桌面应用的一些探索分享
  • 原文地址：https://blog.csdn.net/weixin_61508423/article/details/127883440