C++ set map 的模拟实现-CSDN博客

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

在这里插入图片描述

set 的模拟实现

我们在很早之前就提到过set 的底层数据结构是红黑树。红黑树的实现一般都是 key-value 的结构。但是我们在使用 set 的时候明明只传入了一个模板参数哇我们来看库中的实现

在这里插入图片描述

我们可以看到set 的模板参数 Key 就是存储的数据类型库中对 Key 进行了重命名key_type 和 value_type然后将 key_type 和 value_type 分别作为红黑树的 key 和 value。因此 set 的底层就是存储了两个 key 的红黑树。

我们仿照库里面的实现方式就可以定义出来我们自己的 set 的结构啦

#pragma once
#include"RBTree.h"

namespace Tchey
{
    template<class K>
    class set
    {
    public:


    private:
        RBTree<K, K> _t;
    };
}

记得复制一份我们自己实现的红黑树哦

修改红黑树节点的定义

为了使得一个红黑树的模板类能同时适配出来 map 和 set 我们需要对红黑树节点的定义做修改

在上面的 set 类中成员属性是这么写的RBTree<K, K> _t。在使用 map 的时候我们知道 map 的数据是以 key-value 的形式存储的。那 map 类中成员属性该怎么写呢是这样吗RBTree<K, V> _t。我们先来看我们之前实现的红黑树对于节点的定义

template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	Color _col; //节点的颜色

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED) //节点默认的颜色是红色
	{}
};

这是以 key-value 的形式定义的红黑树节点。如果 map 就是上面那样定义的话那么节点中的 K 和 V 都是存储的数据。

  • 当我们在实现红黑树的迭代器的时候重载 * 运算符的返回值就很难书写对于 set 返回 K 就行但是对于 map 就必须返回 pair<K, V> 无法做到统一那么意味着你就需要对 set 写一个红黑树迭代器的实现map 写一个红黑树迭代器的实现。就会有大量重复的代码这是不被容忍的
  • 其次这么写在 set 插入数据的时候就必须插入一个 pair<K, K> 导致红黑树中的节点中存储了冗余的数据。

因此我们就需要对红黑树的节点稍作修改使得一个红黑树就能适配出 map 和 set。在我们之前实现其他容器的时候我们已经积累了相关的经验只要不一样直接将不一样的地方提炼成模板参数就行啦根据传入参数的不同实例化出来不同的类型。

于是我们对红黑树节点做出如下修改

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;
	Color _col; //节点的颜色

	RBTreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED) //节点默认的颜色是红色
	{}
};

修改红黑树的成员属性

在 RBTree 的实现中成员变量是红黑树的根节点当时我们是这样定义的

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
    Node* _root;
}

现在我们修改了红黑树节点的定义自然不能这么写了联想到 set 中是这么使用红黑树的RBTree<K, K> _t 看上去定义 Node 既可以传 K 也可以传 V。但是为了适配 map我们会选择传递 V 过去像下面这样

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<V> Node;
    Node* _root;
}

改到这里想必你就明白了 map 中的红黑树应该怎么定义了真正的数据类型是 RBTree 的第二个模板参数因此 map 中应该这么使用红黑树RBTree<K, pair<K, V>> _t。

通过这样的方式构造出来的红黑树节点里面的数据既不会冗余也可以做到同时适配 map 和 set。

迭代器实现

红黑树节点的物理空间不连续无法使用原生指针作为红黑树的迭代器需要对节点进行封装构造一个迭代器类同 list 的迭代器因为我们不仅要实现普通的迭代器还需要实现 const 的迭代器所以还需要加上两个模板参数用来控制 operator* 和 operator-> 返回不同的值。

下面就是最基本的结构啦

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNodeL<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> self;

	Node* _node;
};

构造函数

在等会实现 beginend 等接口时都需要构造迭代器返回。迭代器的构造显然是通过节点的指针来的

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNodeL<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> self;
	__TreeIterator(Node* node)
		:_node(node)
	{}

	Node* _node;
};

Ref operator*() 和 Ptr operator->()

有了前面的铺垫我们知道 operator* 和 operator-> 是可以直接适配 map 和 set 的直接上手写就行啦。

Ref operator*()
{
    return _node->_data;
}

Ptr operator->()
{
    return &_node->_data;
}

bool operator!=(const self& s) const

判断两个迭代器是不是不想等就是判断节点的指针是否相等

bool operator!=(const self& s) const
{
    return _node != s._node;
}

self& operator++()

我们通过例子来看看 operator++() 的逻辑是怎么样的在 set 的学习部分我们知道了使用迭代器遍历 set 之后得到的是一个有序的序列显然迭代器遍历的顺序就是走的中序遍历。

如下图所示的例子iterator 对应的节点是 13 那么加加之后显然就是 15。我们来抽一下假设 15 是一颗红黑树而不是单纯的一个节点那么 13 这个节点对应的迭代器加加之后就是右子树对应的最左节点。

在这里插入图片描述

经过这么抽象我们就得到了 operator++ 的关键操作之一如果当前迭代器对应的节点的右子树不为空那么加加之后的结果就是右子树的最小节点(右子树的最左节点)。

那么如果右子树为空怎么办呢

我们来看下面的情况iterator 对应的节点值为 22那么这个位置的迭代器加加之后显然就是 25 这个节点对应的迭代器。根据这个现象如果当前 iterator 对应节点的右子树为空那么就是父节点对应位置的迭代器嘛

在这里插入图片描述

答案是不完全是哦我们来看下面的情况

这个 iterator 对应的节点为 15那么加加之后该指向哪个节点呢是 13 吗根据中序遍历的结果来看加加之后正确的结果应该是 17 这个节点的迭代器嘛

在这里插入图片描述

显然当右子树为空的时候父节点不一定是当前位置的迭代器加加之后的结果。只有当 当前节点位于父节点的左侧的时候加加的结果才是父节点对应的迭代器。如果当前节点位于父节点的右侧那么就要向上跟新 cur(当前节点) 和 parent(父节点) 直到 cur(当前节点) 位于 parent(父节点) 的左侧此时的父节点就是加加之后的结果。

Self& operator++()
{
    if (_node->_right)
    {
        // 右树的最左节点(最小节点)
        Node* subLeft = _node->_right;
        while (subLeft->_left)
        {
            subLeft = subLeft->_left;
        }

        _node = subLeft;
    }
    else
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        // 找孩子是父亲左的那个祖先节点就是下一个要访问的节点
        while (parent && cur == parent->_right)
        {
            cur = cur->_parent;
            parent = parent->_parent;	
        }

        _node = parent;
    }

    return *this;
}

self& operator–()

减减的逻辑和加加的逻辑差不多减减就是先判断左子树是不是为 nullptr如果不为空那么就找到左子树的最右节点(最大节点)。要是当前节点的左子树为空如果当前节点位于父节点的右侧那么父节点就是减减之后的结果如果当前节点位于父节点的左侧那么就需要向上更新 cur(当前节点) 和 parent(父节点) 直到 cur 位于 parent 的右侧此时 parent 对应位置的迭代器就是减减之后的结果。

Self& operator--()
{
    if (_node->_left) //如果左子树不为空找到左子树的最大节点(最右节点)
    {
        Node* subRight = _node->_left;
        while (subRight->_right)
        {
            subRight = subRight->_right;
        }

        _node = subRight;
    }
    else
    {
        // 当前节点的左子树为空
        Node* cur = _node;
        Node* parent = cur->_parent;
        //找到cur 位于 parent 右侧的那个节点这个 parent 就是减减之后的结果
        while (parent && cur == parent->_left)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        _node = parent;
    }

    return *this;
}

红黑树的 begin()

begin 返回的迭代器就是整颗红黑树中最小的那个节点也就是整颗红黑树中最左侧的那个节点。

iterator begin()
{
    Node* cur = _root;
    while(cur && cur->_left)
    {
        cur = cur->_left;
    }
    return cur; //单参数的构造函数支持隐士类型转化
}

//这是 const 的版本
const_iterator end() const
{
    return nullptr;
}

红黑树的 end()

end 返回的迭代器可以是用 nullptr 构造出来的迭代器。

iterator end()
{
    return nullptr;
}

const_iterator end() const
{
    return nullptr;
}

set 的 begin 和 end

还记得我们在 set 的使用部分讲的set 中的元素为什么不能被修改嘛。因为无论是普通的迭代器还是 const 迭代器本质上都是红黑树的 const 迭代器所以通过迭代器来修改 set 中的值是不现实的。根据这个逻辑我们自己就能实现 set 的 begin 和 end 啦。

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

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

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

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

因为在 set 中无论是 iterator 还是 const_iterator 实际上都是 const_iterator所以不加 const 版本的 begin() 和 end() 可以不写的。

红黑树的 pair<iterator, bool> Insert(const T& data)

我们之前实现的红黑树 insert 的返回值都是 bool 类型的我们需要在每一个返回的位置都进行处理。

第一个要处理的位置寻找插入节点的比较方式。之前的比较是已经确定了插入的数据是一个 pair因此用插入数据的 first 和 节点存储的 pair 的 first 比较就可以确定插入位置。

在这里插入图片描述

然而为了同时适配 map 和 set 我们的存储类型已经变成了一个模板参数 T。对于 set红黑树节点存储 的数据类型 T 就是实例化 set 是传入的那个一个类型对于 map红黑树节点存储的数据类型就是一个 pair因此在比较的时候就没有办法做到统一怎么解决呢

答案就是仿函数

我们可以给 RBTree 增加一个模板参数 KeyOfT来获取到不同 T 对应的 key 值。你可能会说 RBTree 不是有一个 K 的模板参数嘛能直接用到这里嘛当然是不能的哦K 仅仅是一个类型不是节点存储的数据哦

在这里插入图片描述

我们来看看 set 怎么实例化红黑树的

template<class K>
class set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
public:

private:
    RBTree<K, K, SetKeyOfT> _t;
};

调用 operator() 的时候根据如果传入的是 K 类型的数据直接返回传入的 key 就行啦。但是如果传入的是 pair<K, V> 类型的数据那么就需要返回传入数据的 first 这才是我们比较需要的 Key 值。这个处理逻辑就是 map 的啦

template<class K, class V>
class map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:

private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

处理之后的结果就是这样啦接下来我们只需要在 set 的实现中复用红黑树的 Insert 接口就行啦。

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

public:
	
	iterator begin()
	{
		Node* cur = _root;
		while(cur && cur->_left)
		{
			cur = cur->_left;
		}
		return cur; //单参数的构造函数支持隐士类型转化
	}

	const_iterator begin() const
	{
		Node* cur = _root;
		while(cur && cur->_left)
		{
			cur = cur->_left;
		}
		return cur; //单参数的构造函数支持隐士类型转化
	}

	iterator end()
	{
		return nullptr;
	}

	const_iterator end() const
	{
		return nullptr;
	}

	
	pair<iterator, bool> Insert(const T& data)
	{
		//插入的时候如果根节点为 nullptr, 申请一个节点将该节点的颜色改为黑色之后作为根节点就行啦
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		//记录父节点
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot; //实例化一个对象用来调用 operator()
		while (cur) //找到新节点的插入位置
		{
			if (kot(cur->_data) < kot(data)) //新插入的节点比根节点大与右子树的根节点比较
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data)) //新插入的节点比根节点小与左子树的根节点比较
			{
				parent = cur;
				cur = cur->_left;
			}
			else //如果有相同的节点插入失败
			{
				return make_pair(iterator(cur), false);
			}
		}
		//申请新的节点
		cur = new Node(data);

		Node* newNode = cur; //记录一下新插入的节点方便构造 

		//解耦操作
		cur->_col = RED;
		//确定新的节点插入到那个位置左孩子还是右孩子
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//向上链接父节点
		cur->_parent = parent;

		//调整节点的颜色使之满足红黑树的性质只有 parent 的颜色为红才会调整节点的颜色parent 为黑就直接完成插入了嘛
		while (parent && parent->_col == RED)
		{
			//祖父节点
			Node* grandfather = parent->_parent;
			//这里根据父节点在祖父节点的位置进行分类因为我们要确定 uncle 的位置嘛这样分类代码比较简洁
			//parent 位于 grandparent 的左侧
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				// uncle 存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else // uncle 不存在 或 uncle 存在且为黑
				{
					if (cur == parent->_left)
					{
						//     g
						//   p
						// c
						//右单旋
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//     g
						//   p
						//		c
						//左右双旋
						RotateL(parent);
						RotateR(grandfather);

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

					break; //一旦经过旋转调整颜色之后就一定满足红黑树的性质了直接结束循环
				}
			}
			else // parent == grandfather->_right
			{
				//找到叔叔节点
				Node* uncle = grandfather->_left;
				// uncle 存在且为红
				if (uncle && uncle->_col == RED)
				{
					// 变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续向上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						// g
						//	  p
						//       c
						//左单旋
						RotateL(grandfather);
						grandfather->_col = RED;
						parent->_col = BLACK;
					}
					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 的 insert()

你可能会说set 里面的 insert 直接复用红黑树里面的 insert 不就行了吗我们直接来试试

在这里插入图片描述

我们发现无法编译通过说什么无法转化。这是什么原因呢其实就是 set 的 iterator 有问题。因为 set 的 iterator 就是 const_iterator 调用红黑树里面的 insert 接口返回的是一个普通的迭代器而 set 中的insert 返回的实际上是一个 const_iterator。虽然红黑树中的 iterator 与 const_iterator 来自与同一个类模板但是因为传入模板参数的不同压根就是两个不同的类型不能转化实属正常。

你会怎么解决这个问题呢可以将红黑树中的 insert 的返回值改成 const_iterator 嘛这么改的确解决了 set 的问题。map 怎么办要是 map 调用红黑树中的 insert 得到的就是个 const_iterator但是 map 需要的是 iterator 哇这种办法行不通。

看来就只能提供一个 iterator 到 const_iterator 的转换函数啦怎么实现呢

template<class T, class Ref, class Ptr>
struct __TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __TreeIterator<T, Ref, Ptr> self;
	__TreeIterator(Node* node)
		:_node(node)
	{}

	typedef __TreeIterator<T, T&, T*> iterator;

	__TreeIterator(const iterator& it)
		:_node(it._node)
	{}
}

我们增加了一个看上去很像拷贝构造的构造函数。__TreeIterator 中的 iterator 模板参数的类型是 __TreeIterator<T, T&, T*>。说明这个 iterator 无论模板参数 Ref 和 Ptr 传入什么都是非 const 的iterator。当 Ref 和 Ptr 分别传入 T& 和 T* 那么 __TreeIterator(const iterator& it) 就是一个拷贝构造函数因为 iterator 与类实例化出来的对象时一个类型嘛当 Ref 和 Ptr 分别传入 const T& 和 const T* 那么 __TreeIterator(const iterator& it) 就是一个将非 const 的迭代器转化为 const 迭代器的构造函数。是不是相当美妙。

通过添加这个看上去十分像拷贝构造的函数就可以实现同时适配 map 和 set 啦
在这里插入图片描述

测试通过set 模拟实现完成。

map 的模拟实现

在 set 的模拟实现部分我们已经将红黑树改成同时适配 map 和 set 的结构了因此 map 的实现直接调用红黑树对应的接口就好啦

V& operator[]

map 的使用部分浅浅的讲过。opertor[] 就是先调用 insert 函数如果说插入成功返回插入成功的节点对应的 value 值就可以如果插入失败返回与新插入节点 key 值相同的那个节点对应的 value 值就行。这恰好根 insert 的返回值对应上了我们只需要返回 insert 的返回值中 first 迭代器对应节点的 value 值就大功告成了。

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

map 的代码

#pragma once
#include"RBTree.h"

namespace Tchey
{
    template<class K, class V>
    class map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<K, V>& kv)
            {
                return kv.first;
            }
        };
    
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

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

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

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

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

        pair<iterator, bool> insert(const pair<K, V>& kv)
        {
            return _t.Insert(kv);
        }
        
        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = insert(make_pair(key, V()));
            return ret.first->second;
        }

    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
    };
}

测试

在这里插入图片描述

到这里 map 和 set 的模拟实现就完成啦还是比较有意思的对吧。​

在这里插入图片描述

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：java中拼接“-CSDN博客

下一篇：解决kubernetes node节点flannel网卡始终不能添加成功的问题-CSDN博客

“C++ set map 的模拟实现-CSDN博客” 的相关文章

Xmake v2.7.6 发布，新增 Verilog 和 C++ Modules 分发支持1年前 (2023-02-02)
（黑马C++）L08 C++模板1年前 (2023-02-02)
【C++】STL六大组件之一——适配器（adapters）1年前 (2023-02-02)
【c++】noexcept关键字1年前 (2023-02-02)
C++程序设计——类的六个成员函数1年前 (2023-02-02)
从C和C++内存管理来谈谈JVM的垃圾回收算法设计-下1年前 (2023-02-02)
C++ 001：C++ 基础语法1年前 (2023-02-02)
C++基础语法 10（继承）1年前 (2023-02-02)
Visual C++6.0安装教程（win10版）及“应用程序无法正常启动（0x0150002）”解决办法1年前 (2023-02-02)
c++、php、java、python、javascript对比，同一功能用5种编程语言写一遍，谁才是最好的编程语言？_c++ java php1年前 (2023-02-02)

阿里云国际版