• set和map的模拟

    目录

    1.介绍

    2.模拟实现

    2.1节点的改造

    2.2迭代器的实现

    2.2.1

    2.2.2

    3.完整代码

    1.介绍

    STL中的set和map的底层都是用红黑树模拟实现的。但set每次只存储一个值，而map存储的是键值对，那是否要写两份红黑树的代码呢？

    可写看下之前写的博客：可怕的红黑树_"派派"的博客-CSDN博客，实现是与map相似的。

    2.模拟实现

    2.1节点的改造

    我们可用模板对红黑树进行改造，让map和set同时适用。

    在红黑树的代码中，我们可把存储每个节点的结构代码体更改为：

    1. enum Colour
    2. {
    3. 	RED,
    4. 	BLACK,
    5. };
    6.  
    7. template<class T>
    8. struct RBTreeNode
    9. {
    10. 	RBTreeNode* _left;
    11. 	RBTreeNode* _right;
    12. 	RBTreeNode* _parent;
    13. 	T _data; // 存储数据
    14. 	Colour _col;
    15.  
    16. 	RBTreeNode(const T& data)
    17. 		:_data(data)
    18. 		, _left(nullptr)
    19. 		, _right(nullptr)
    20. 		, _parent(nullptr)
    21. 		, _col(RED)
    22. 	{}
    23. };

    其中根据T中的类型进行存储，例如：T可以是set传来的int类型等，map传来的键值对。

    但在插入时需要比较数据的大小，T可能为int类型或则键值对。所以需要再增加一个仿函数，用来提取第一个参数（map和set都是用第一个参数比较大小的）。

    set中：

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

    map中:

    1.   template<class K, class V>
    2. class Map
    3. {
    4. 	struct MapKeyOfT
    5. 	{
    6. 		const K& operator()(const pair& kv)//提取第一个参数
    7. 		{
    8. 			return kv.first;
    9. 		}
    10. 	};
    11. public:
    12. 	bool insert(const pair& kv)
    13. 	{
    14. 		_t.Insert(kv);
    15.  
    16. 	}
    17.  
    18.  
    19. private:
    20. 	RBTree, MapKeyOfT> _t;
    21. };

    红黑树的代码部分：

    1. template<class K, class T, class KeyOfT>//keyOfT用来接收仿函数
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node;
    5. public:
    6. 	bool Insert(const T& data)
    7. 	{
    8.  
    9. 		if (_root == nullptr)
    10. 		{
    11. 			_root = new Node(data);
    12. 			_root->_col = BLACK;
    13.  
    14. 			return true;
    15. 		}
    16.  
    17. 		KeyOfT kot;
    18. 		Node* parent = nullptr;
    19. 		Node* cur = _root;
    20. 		while (cur)
    21. 		{
    22. 			if (kot(cur->_data) < kot(data))
    23. 			{
    24. 				parent = cur;
    25. 				cur = cur->_right;
    26. 			}
    27. 			else if (kot(cur->_data) > kot(data))
    28. 			{
    29. 				parent = cur;
    30. 				cur = cur->_left;
    31. 			}
    32. 			else
    33. 			{
    34.  
    35. 				return false;
    36. 			}
    37. 		}
    38. 		cur = new Node(data);
    39. 		Node* newnode = cur;
    40. 		cur->_col = RED;
    41. 		if (kot(parent->_data) < kot(data))
    42. 		{
    43. 			parent->_right = cur;
    44. 		}
    45. 		else
    46. 		{
    47. 			parent->_left = cur;
    48. 		}
    49. 		cur->_parent = parent;
    50.        ..................
    51.        ..................
    52.        //旋转.....
    53. }
    54. }

    画图理解下：

     我们可验证下结果是否准确，可在红黑树中定义一个中序遍历代码，然后在set，map中调用。

    1. void test_set1()
    2. {
    3. 	Set<int> s;
    4. 	s.insert(8);
    5. 	s.insert(6);
    6. 	s.insert(5);
    7. 	s.insert(7);
    8. 	s.insert(2);
    9. 	s.insert(9);
    10. 	Mapint>m;
    11. 	m.insert(make_pair("香蕉", 1));
    12. 	m.insert(make_pair("苹果", 1));
    13. 	m.insert(make_pair("西瓜", 1));
    14. 	m.insert(make_pair("草莓", 1));
    15. 	s.Inorder();
    16. 	cout << endl;
    17. 	m.Inorder();
    18. }

     结果：

     

    2.2迭代器的实现

    红黑树也是可以像string，vector一样，通过迭代器像指针一样去遍历节点，不过它更像list的迭代器，不是一个原生指针，而是通过封装了节点的指针，对指针进行操作。

    在红黑树中增加下面的代码：

    1.     typedef __RBTreeIterator iterator;
    2. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    3. 	iterator Begin()//找其最左节点
    4. 	{
    5. 		Node* subLeft = _root;
    6. 		while (subLeft && subLeft->_left)
    7. 		{
    8. 			subLeft = subLeft->_left;
    9. 		}
    10.  
    11. 		return iterator(subLeft);
    12. 	}
    13.  
    14. 	iterator End()
    15. 	{
    16. 		return iterator(nullptr);
    17. 	}
    18.  
    19. 	const_iterator Begin() const
    20. 	{
    21. 		Node* subLeft = _root;
    22. 		while (subLeft && subLeft->_left)
    23. 		{
    24. 			subLeft = subLeft->_left;
    25. 		}
    26.  
    27. 		return const_iterator(subLeft);
    28. 	}
    29.  
    30. 	const_iterator End() const
    31. 	{
    32. 		return const_iterator(nullptr);
    33. 	}
    34.  
    35.     iterator Find(const K& key)//查找
    36. 	{
    37. 		Node* cur = _root;
    38. 		KeyOfT kot;
    39. 		while (cur)
    40. 		{
    41. 			if (kot(cur->_data) < key)
    42. 			{
    43. 				cur = cur->_right;
    44. 			}
    45. 			else if (kot(cur->_data) > key)
    46. 			{
    47. 				cur = cur->_left;
    48. 			}
    49. 			else
    50. 			{
    51. 				return iterator(cur);
    52. 			}
    53. 		}
    54.  
    55. 		return End();
    56. 	}

    迭代器的实现：

    2.2.1

    1. template<class T, class Ref, class Ptr>
    2. struct __RBTreeIterator
    3. {
    4. 	typedef RBTreeNode Node;
    5. 	typedef __RBTreeIterator Self;
    6. 	Node* _node;
    7.  
    8. 	__RBTreeIterator(Node* node)
    9. 		:_node(node)
    10. 	{}
    11.  
    12. 	Ref operator*()
    13. 	{
    14. 		return _node->_data;
    15. 	}
    16.  
    17. 	Ptr operator->()
    18. 	{
    19. 		return &_node->_data;
    20. 	}
    21. 	
    22. 	Self& operator++()
    23. 	{
    24.       ............
    25.       ............
    26. 	}
    27.  
    28. 	Self operator++(int)
    29. 	{
    30. 		Self tmp(*this);
    31. 		
    32. 		++(*this);
    33.  
    34. 		return tmp;
    35. 	}
    36.  
    37. 	Self& operator--()
    38. 	{
    39. 		..........
    40.         ..........
    41. 	}
    42.  
    43. 	Self operator--(int)
    44. 	{
    45. 		Self tmp(*this);
    46.  
    47. 		--(*this);
    48.  
    49. 		return tmp;
    50. 	}
    51.  
    52. 	bool operator!=(const Self& s) const
    53. 	{
    54. 		return _node != s._node;
    55. 	}
    56.  
    57. 	bool operator==(const Self& s) const
    58. 	{
    59. 		return _node == s->_node;
    60. 	}
    61. };

    2.2.2

    ++的实现：

    ++的实现与中序遍历的规则类似，但每次只走一步。

    思路：当一个节点有右子树时，对其节点++，之后指针是指向该右子树的最左节点。

               当一个节点无右子树时，对其节点++，之后指针是指向（在其祖先里，孩子是属于祖先左              孩子的）。

    如图：

    1.     Self& operator++()
    2. 	{
    3. 		if (_node->_right == nullptr)
    4. 		{
    5. 			// 找祖先里面，孩子是父亲左的那个
    6. 			Node* cur = _node;
    7. 			Node* parent = cur->_parent;
    8. 			while (parent && parent->_right == cur)
    9. 			{
    10. 				cur = cur->_parent;
    11. 				parent = parent->_parent;
    12. 			}
    13.  
    14. 			_node = parent;
    15. 		}
    16. 		else
    17. 		{
    18. 			// 右子树的最左节点
    19. 			Node* subLeft = _node->_right;
    20. 			while (subLeft->_left)
    21. 			{
    22. 				subLeft = subLeft->_left;
    23. 			}
    24.  
    25. 			_node = subLeft;
    26. 		}
    27. 		return *this;
    28. 	}

    --的实现：

    思路：当左子树不为空时，对其节点--，指向的是该左子树的最右节点。

               当左子树为空时，对其节点--，之后指针是指向（在其祖先里，孩子是属于祖先右                           孩子的）。

    如图：

    1. Self& operator--()
    2. 	{
    3. 		if (_node->_left == nullptr)
    4. 		{
    5. 			Node* cur = _node;
    6. 			Node* parent = cur->_parent;
    7. 			while (parent && cur == parent->_left)
    8. 			{
    9. 				cur = cur->_parent;
    10. 				parent = parent->_parent;
    11. 			}
    12.  
    13. 			_node = parent;
    14. 		}
    15. 		else
    16. 		{
    17. 			// 左子树的最右节点
    18. 			Node* subRight = _node->_left;
    19. 			while (subRight->_right)
    20. 			{
    21. 				subRight = subRight->_right;
    22. 			}
    23. 			_node = subRight;
    24. 		}
    25.  
    26. 		return *this;
    27. 	}

    当迭代器实现后，红黑树的插入代码要进行更改，insert函数返回值是pair，第一个参数是指向当前节点的迭代器，第二个参数是true/false;(插入成功返回true，否则返回false）。

    3.完整代码

    set:

    1. template<class K>
    2. 	class Set
    3. 	{
    4. 		struct SetKeyOfT
    5. 		{
    6. 			const K& operator()(const K& key)
    7. 			{
    8. 				return key;
    9. 			}
    10. 		};
    11. 	public:
    12. 		typedef typename RBTree::const_iterator iterator;
    13. 		typedef typename RBTree::const_iterator const_iterator;
    14.  
    15. 		iterator begin() const
    16. 		{
    17. 			return _t.Begin();
    18. 		}
    19.  
    20. 		iterator end() const
    21. 		{
    22. 			return _t.End();
    23. 		}
    24.  
    25. 		pairbool> insert(const K& key)
    26. 		{
    27. 			//pair::iterator, bool> ret = 
    28.             //                                        _t.Insert(key);
    29. 			auto ret = _t.Insert(key);
    30. 			return pairbool>(iterator(ret.first._node), ret.second);
    31. 		}
    32.  
    33. 		iterator find(const K& key)
    34. 		{
    35. 			return _t.Find(key);
    36. 		}
    37. 	private:
    38. 		RBTree _t;
    39. 	};

    map代码：

    1.    template<class K, class V>
    2. 	class Map
    3. 	{
    4. 		struct MapKeyOfT
    5. 		{
    6. 			const K& operator()(const pair& kv)
    7. 			{
    8. 				return kv.first;
    9. 			}
    10. 		};
    11. 	public:
    12. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    13. 		typedef typename RBTree, MapKeyOfT>::const_iterator const_iterator;
    14.  
    15. 		iterator begin()
    16. 		{
    17. 			return _t.Begin();
    18. 		}
    19.  
    20. 		iterator end()
    21. 		{
    22. 			return _t.End();
    23. 		}
    24.  
    25. 		pairbool> insert(const pair& kv)
    26. 		{
    27. 			return _t.Insert(kv);
    28. 		}
    29.  
    30. 		iterator find(const K& key)
    31. 		{
    32. 			return _t.Find(key);
    33. 		}
    34.  
    35. 		V& operator[](const K& key)
    36. 		{
    37. 			pairbool> ret = insert(make_pair(key, V()));
    38. 			return ret.first->second;
    39. 		}
    40.  
    41. 	private:
    42. 		RBTree, MapKeyOfT> _t;
    43. 	};

  • 相关阅读:
    Linux 搭建NFS
    【k8s】浅谈对kubernetes基本概念
    箭头函数的缺点
    用于远程医疗的无创、无袖带血压测量【翻译】
    SpringBoot项目如何引入外部jar及将外部jar打包到项目发布jar包
    python triangle库将一组闭合点转化为三角网格时网格过密的问题
    AiDocZh.com重磅发布！LlamaIndex中文文档上线啦！
    php反序列化
    python爬虫实战-京东商品数据
    浅谈电力电容器技术的发展及选型
  • 原文地址：https://blog.csdn.net/m0_64397669/article/details/126597312