• 红黑树实现map、set基本功能



    一、map、set部分源码

    map源码成员变量

    template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
    class map {
    public:
      typedef Key key_type;
      typedef T data_type;
      typedef T mapped_type;
      typedef pair<const Key, T> value_type;
      typedef Compare key_compare;
    private:
      typedef rb_tree<key_type, value_type, 
                      select1st<value_type>, key_compare, Alloc> rep_type;
      rep_type t;  // red-black tree representing map
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    set源码成员变量

    template <class Key, class Compare = less<Key>, class Alloc = alloc>
    class set {
    public:
      typedef Key key_type;
      typedef Key value_type;
      typedef Compare key_compare;
      typedef Compare value_compare;
    private:
      typedef rb_tree<key_type, value_type, 
                      identity<value_type>, key_compare, Alloc> rep_type;
      rep_type t;  // red-black tree representing set
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    红黑树主要成员变量

    template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
    class rb_tree {
    	typedef rb_tree_node* link_type;
    protected:
    	typedef __rb_tree_node<Value> rb_tree_node;
    	link_type header; 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    map 和 set用的是用一棵红黑树,但是它们存储的类型不同,是怎么实现的呢?

    两个传给红黑树的类型参数个数相同,只是真正的类型不同

      typedef rb_tree<key_type, value_type, 
                      identity<value_type>, key_compare, Alloc> rep_type;
    
    • 1
    • 2

    map 传给红黑树的类型是:

      typedef Key key_type;
      typedef pair<const Key, T> value_type;
    
    • 1
    • 2

    set 传给红黑树的类型是:

      typedef Key key_type;
      typedef Key value_type;
    
    • 1
    • 2

    map传入的value_type是一个KV元组类型,set的是K类型,这就是模板的好处,但是红黑树里面有需要key来比较时候,这就需要上层(map、set)传入一个仿函数来获取到存储类型的key值用于比较。

    class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc
    红黑树模板参数类型解释:

    • Key: key的类型,时候会用到,模板参数传入的类型不是值
    • Value: 存储值的类型,map是一个元组,set只有key
    • KeyOfValue: 获取到存储类型的key值的仿函数,使得一颗红黑树实现两种不同的存储类型
    • Compare: 用于key值比较的仿函数
    • Alloc: 内存分配相关,暂时不用关心

    二、红黑树的完善

    2.1 迭代器的实现

    2.1.1 基本功能

    template<class T, class Ref, class Ptr>
    struct RBTreeIterator
    {
    	typedef RBTreeIterator<T, Ref, Ptr> Self;
    	typedef RBTreeNode<T> Node;
    	Node* _node;
    
    	RBTreeIterator(Node* node)
    		:_node(node)
    	{}
    
    	Ref operator*()
    	{
    		return _node->data;
    	}
    	Ptr operator->()
    	{
    		return &_node->_data;
    	} 
    		bool operator!=(const Self& t)
    	{
    		return _node != t._node;
    	}
    	bool operator==(const Self& t)
    	{
    		return _node == t._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

    2.1.2 迭代器的加减

    需要按中序遍历(有序)来实现迭代器的加减。
    寻找下一个结点
    即 ++ 迭代器

    1. 右子树不为空,下一个结点就是右子树的最小值结点(即最左结点)
    2. 右子树为空,表示本身所在子树已经结束,需要沿着到根节点的路径走,找到一个结点是父节点的左孩子,那这个父节点就是下一个结点,直到父节点为空。
    Self operator++()
    {
    	if (_node->_right != nullptr)
    	{
    		// 找右子树最小结点
    		Node* minNode = _node->_right;
    		while (minNode->_left != nullptr)
    		{
    			minNode = minNode->_left;
    		}
    		_node = minNode;
    	}
    	else
    	{
    		// 找到 cur == parent->left
    		Node* parent = _node->_parent;
    		Node* cur = _node;
    		while (cur != parent->_left && parent != nullptr)
    		{
    			cur = parent;
    			parent = _node->_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

    寻找前一个结点
    即 – 迭代器

    1. 左子树不为空,前一个结点就是左子树的最大结点(即最右结点)
    2. 左子树为空,需要沿着到根结点的路径上查找,找到一个结点是父节点的右孩子,那么这个父节点就是前一个结点,直到父节点为空。
    Self operator--()
    {
    	if (_node->_left != nullptr)
    	{
    		// 找左子树最大结点
    		Node* maxNode = _node->_left;
    		while (maxNode->_right != nullptr)
    		{
    			maxNode = maxNode->_right;
    		}
    		_node = maxNode;
    	}
    	else
    	{
    		// 找到 cur == parent->_right
    		Node* parent = _node->_parent;
    		Node* cur = _node;
    		while (cur != parent->_right && parent != nullptr)
    		{
    			cur = parent;
    			parent = _node->_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

    2.1.3 获取迭代器

    	typedef RBTreeIterator<T, T&, T*> iterator;
    	typedef RBTreeIterator<T, const T&, const T*> const_iterator;
    
    
    	iterator begin()
    	{
    		Node* min = _root;
    		while (min && min->_left)
    		{
    			min = min->_left;
    		}
    
    		return iterator(min);
    	}
    
    	iterator end()
    	{
    		return iterator(nullptr);
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2.2 默认成员函数的实现

    2.2.1 拷贝构造函数

    	// 拷贝构造函数
    	RBTree(const RBTree<K, T, KeyOfT>& t)
    	{
    		_root = Copy(t._root);
    	}
    	Node Copy(Node* node)
    	{
    		if (node == nullptr) return nullptr;
    		Node* newNode = new T(node->_data);
    
    		newNode->_col = node->_col;
    		// 链接左右孩子
    		newNode->_left = Copy(node->_left);
    		newNode->_right = Copy(node->_right);
    
    		// 链接父节点
    		if (newNode->_left)
    			newNode->_left->_parent = newNode;
    		if (newNode->_right)
    			newNode->_right->_parent = newNode;
    		return newNode;
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    2.2.2 赋值运算符重载

    	// 赋值运算符重载
    	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
    	{
    		std::swap(t._root, _root);
    		return *this;
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2.2.3 析构函数

    	// 析构函数
    	~RBTree()
    	{
    		Destroy(_root);
    		_root = nullptr;
    	}
    	void Destroy(Node* root)
    	{
    		if (root == nullptr)
    			return;
    
    		Destroy(root->_left);
    		Destroy(root->_right);
    		delete root; // 调用Node的析构函数
    	}
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    三、封装形成map、set

    这下封装就很简单了直接调用红黑树的方法即可

    3.1 map基本功能

    #pragma once
    namespace sqin
    {
    	template<class K, class V>
    	class map
    	{
    	public:
    		// 获取类型的key值
    		struct MapKeyOfT
    		{
    			const K& operator()(const pair<K, V>& kv)
    			{
    				return kv.first;
    			}
    		};
    
    		typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
    		iterator begin()
    		{
    			return _t.begin();
    		}
    		iterator end()
    		{
    			return _t.end();
    		}
    		
    		pair<iterator, bool> insert(const pair<K,V>& kv)
    		{
    			return _t.Insert(kv);
    		}
    		iterator find(const K& k)
    		{
    			return _t.find(k);
    		}
    
    		// 利用插入返回值,实现[]功能
    		V& operator[](const K& k)
    		{
    			auto cur = _t.Insert(make_pair(k, V()));
    			return cur.first->second;
    		}
    
    	private:
    		RBTree<K, pair<K, V>, MapKeyOfT> _t;
    	};
    }
    
    • 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

    3.2 set基本功能

    #pragma once
    namespace sqin
    {
    	template<class K>
    	class set
    	{
    	public:
    		// 获取类型的key值
    		struct SetKeyOfT
    		{
    			const K& operator()(const K& k)
    			{
    				return k;
    			}
    		};
    
    		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    		iterator begin()
    		{
    			return _t.begin();
    		}
    		iterator end()
    		{
    			return _t.end();
    		}
    
    		pair<iterator, bool> insert(const K& k)
    		{
    			return _t.Insert(k);
    		}
    		iterator find(const K& k)
    		{
    			return _t.find(k);
    		}
    
    
    	private:
    		RBTree<K, K, SetKeyOfT> _t;
    	};
    }
    
    • 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
  • 相关阅读:
    一.node的http模块;二.同步和异步;三.异步操作的实现:ajax;四.jQuery中对ajax封装;五.Node的Web框架
    多副本技术在数据安全中的应用
    Triple协议 和dubbo协议
    JVM学习(宋红康)之堆空间概述
    C#开发的OpenRA游戏之金钱系统(4)
    车载相关名词--车载数据中心方案
    关于 Angular 部署以及 index.html 里 base hRef 属性的关联关系
    运动装备经营小程序商城效果如何
    5-4 jmu-报数游戏 (15分)
    JAVA集合问答
  • 原文地址:https://blog.csdn.net/qq_52145272/article/details/125468726