C++：用红黑树封装map与set-1

devtools/2024/11/25 10:17:38/

在这里插入图片描述

文章目录

  • 前言
  • 一、STL源码分析
  • 二、红黑树的构建
  • 三、map与set整体框架的搭建与解析
  • 四、如何取出进行比较？
    • 1. met与set的数据是不同的
    • 2. 取出数据进行比较
      • 1）问题发现
      • 2）仿函数解决
  • 五、封装插入
  • 六、迭代器的实现
    • 1. operator* 与operator->
    • 2. operator!=
    • 3. operator++
    • 4. operator- -
    • 5. 套用普通迭代器
  • 七、const迭代器
  • 八、查找
  • 总结

前言

之前我们学习了红黑树的实现，现在我们一起来看一看如何使用红黑树封装出set与map~~~

一、STL源码分析

我们一起来分析分析STL源码，看一看库中是如何实现的🥰🥰

在这里插入图片描述
首先，库里面stl_set与stl_map中，

对于set来说，key_type是key，value_type也是key，也就是说set是一个rbTree<Key, Key>的模型。

对于map来说，key_type是key，但是value_type是pair<const key, T>，也就是说map是一个rbTree<Key, pair<Key, Value>>的模型。

我们再来看一下rb_tree的结构：

在这里插入图片描述

rb_tree中，前两个参数是<key, value>，而__rb_tree_node<value>里面的参数传的是value，因此我们可以总结出，这里map的结点中存储的是pair<key, value>，而set的结点中存储的是key。

在这里插入图片描述

那么到底为什么是这样的结构呢？
我们将在下面的讲解中逐一解释🥰

二、红黑树的构建

对于红黑树的构建，J桑之前的文章有详细的讲解，因此这里就直接给出代码啦，还不清楚的观众老爷门可以点击下方的传送门🥰🥰🥰

深入探索：C++红黑树原理与实现

当然，我们之前红黑树是默认存储pair，现在要同时满足map与set，因此一些地方需要改变，之后总结的时候会给出完整的更改后的代码，下面讲解也会被提到。

#pragma once
#include<iostream>using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;RBTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};template<class K, class V> 
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){// 树为空，直接插入然后返回if (_root == nullptr){_root = new Node(kv);// 根节点必须是黑色_root->_col = BLACK;return true;}Node* cur = _root;Node* parent = nullptr;while (cur){// 小于往左走if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first)   // 大于往右走{parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);// 其他结点初始颜色为红色cur->_col = RED;// 链接if (cur->_kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 如果我们parent是黑色，不用处理，就结束了// 情况一：cur为红，parent为红，grandfather为黑，uncle不确定// 用while循环是因为我们要不断的向上调整while (parent && parent->_col == RED){// 首先我们要找到grandfatherNode* grandfather = parent->_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather->_leftif (parent == grandfather->_left){// 说明uncle在右边Node* uncle = grandfather->_right;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;// 但是走到这里有一个问题，如果当前parent就是根，// 并且parent是红色，我们要把它变为黑色，// 处理方式是：出循环后，暴力将_root->_col变为黑色}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋if (cur == parent->_left){//     g//   p// cRotateR(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 左右双旋{//     g//   p//		cRotateL(parent);RotateR(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}// 旋转变色完就结束了，这里不加这个也可以，条件判断就会退出break;}}else //(parent == grandfather->_right)  // 如果parent是grandfather->_right{// 说明uncle在左边Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 满足上述情况，开始调整颜色parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;// 继续向上调整cur = grandfather;parent = cur->_parent;}else    // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);// 调整颜色parent->_col = BLACK;grandfather->_col = RED;}else // 右左双旋{// g//	  p// cRotateR(parent);RotateL(grandfather);// 调整颜色cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 这里保证根为黑色_root->_col = BLACK;return true;}// 左单旋void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;// 重新链接parent->_right = curleft;if (curleft) // 如果curleft存在{curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 右单旋void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (ppnode == nullptr){cur->_parent = nullptr;_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}private:Node* _root = nullptr;
};

mapset_385">三、map与set整体框架的搭建与解析

代码：

namespace jyf
{template<class k, class v>class map{public:private:RBTree<k, pair<k, v>> _t;};
}

namespace jyf
{template<class k>class set{public:private:RBTree<k, k> _t;};
}

解析：

首先无论是map还是set都有两个模板参数，第一个是key，这个key是多存的，它的作用体现在像find()这样的函数中，我们后面在做解析。

这里先看第二个参数，传给了RBTree的T，而T就是结点中储存的东西，也就是说，你是set，那么节点中就储存的是key, 你是map，那么节点中就储存的是pair<k, v>。

在这里插入图片描述

四、如何取出进行比较？

set_429">1. met与set的数据是不同的

我们要明白一个我问题，met与set结点中存储的数据是不一样的，因此，如果节点中还存储的是pair就不对了，因此，我们结点之中存储的数据因该是T类型的数据，如果是set就是key,如果是map就是pair。

在这里插入图片描述

2. 取出数据进行比较

1）问题发现

再insert函数中，我们之前的红黑树是这样实现的，比如这个找到插入位置的逻辑：

在这里插入图片描述
在这张图片里面，我们之前使用pair，但是现在对于map和set存储的数据不同，因此需要用data来比较。

但是！！！
对于map来说，它的value是pair，但是pair的比较逻辑能满足我们的需要吗？

在这里插入图片描述

可以看到，pair的比较逻辑是先比first，first一样就比second，但是，我们这里不需要比较second，key_value的模型中，只需要比较key不同，因此我们需要一种方法，重新定义我们的比较。

怎么重新比较呢？
这里我们通过观察发现，对于set来说，它的data是key，可以直接比较，唯一有问题的是map，因此我们采取的方式是仿函数。

2）仿函数解决

我们可以多定义一个模板参数KeyOfT，这个模板参数用来定义仿函数，他的作用是取出Set或Map中的Key。

对于Set，它的data直接就是key：

struct SetKeyOfT
{const K& operator()(const K& key){return key;}
};

对于Map，它的data是一个pair，我们需要pair的first，也就是key：

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

在这里插入图片描述

至此，我们在取出数据的时候，只要定义出一个对象，重载operator()，用()将data包起来，就得到了我们想要的数据。

可以说，这里set迁就了map~

五、封装插入

完成了上述步骤，我们就可以实现封装map与set的插入了~

对于set:

bool insert(const K& key)
{return _t.Insert(key);
}

对于map:

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

插入结果：
在这里插入图片描述

在这里插入图片描述

六、迭代器的实现

要实现迭代器，就要先理解迭代器是怎么用的：
下面是一个模板表示迭代器的使用：

it = s.begin();
while (it != s.end())
{cout << *it << endl;++it;
}

为了实现这个过程，我们需要重载很多东西。

我们先将框架搭出来：

template<class T>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self;Node* _node;__TreeIterator(Node* node):_node(node){}
};

1. operator* 与operator->

RBTree中：

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

2. operator!=

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

3. operator++

对于树的迭代器，++与- -就非常重要了，这里有很多坑~

首先对于一个红黑树，他走的是中序的排序，图如下：

在这里插入图片描述

那么，it.begin()是谁呢？
我们说中序是左-根-右，也就是说，begin应该是上图中的1。

其次，如果我们进行++操作，迭代器会到那里去呢？
这里分以下几种情况：

  1. 如果右不为空

那么下一个访问的，将是右树的最左：

在这里插入图片描述

  1. 如果右为空

这里又分两种情况：

  • cur是parent的左——下一个访问parent
    在这里插入图片描述

  • cur是parent的右——下一个访问没有被访问的祖先
    在这里插入图片描述

通过观察这两种情况我们可以发现：
也就是说，当右为空的时候，下一个访问的是孩子是父亲的左侧的那一个祖先。

代码总结：

Self& operator++ ()
{if (_node->_right != nullptr){Node* curleft = _node->_right;while (curleft->_left){curleft = curleft->_left;}_node = curleft;}else{// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点Node* cur = _node;Node* parent = _node->_parent;while (parent){if (parent->_left == cur){break;}else{cur = parent;parent = parent->_parent;}}_node = parent;}return *this;
}

4. operator- -

原理与++是一样的，只不过原本++的顺序是中序，即左-根-右，- - 是反过来的，因此是右-根-左

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;while (parent && cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}

5. 套用普通迭代器

RBTree中：

经过前面的分析，begin就是树最左边的结点，end我们设置为nullptr。

	typedef __TreeIterator<T> iterator;
public:iterator begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}

set与map中，我们要封装这个方法：

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

测试普通迭代器：

jyf::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));jyf::map<int, int>::iterator mit = m.begin();while (mit != m.end())
{mit->first = 1;mit->second = 2;cout << mit->first << ":" << mit->second << endl;++mit;
}
cout << endl;for (const auto& kv : m)
{cout << kv.first << ":" << kv.second << endl;
}
cout << endl;jyf::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);auto it = s.begin();
while (it != s.end())
{// Ӧ޸if (*it % 2 == 0){*it += 10;}cout << *it << " ";++it;
}
cout << endl;for (const auto& e : s)
{cout << e << " ";
}
cout << endl;

结果为：
在这里插入图片描述

七、const迭代器

我们知道set是不允许修改的，map的key不允许修改，而value允许修改，再通过观察库中的实现，我们可以发现:
在这里插入图片描述

set实现不能修改的原因是——interator迭代器与const_iterator都是const迭代器。

而map实现key不能修改，value可以修改的方法是，在定义map的value的时候，pair<K, V>修改为pair<const K, V>

具体的逻辑我们下一次在进行讲解~

八、查找

查找是通过key来查找的，而不是通过value来查找的，这也就解释了为什么最开始定义模板参数还要多定义一个key。

同样，为了取出对应的值，我们也需要仿函数来包上data。

Node* Find(const K& key)
{Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

总结

红黑树在 STL 的应用
set 与 map 的实现：

set 节点存储 key（rbTree<Key, Key> 模型）。

map 节点存储 pair<const Key, T>（rbTree<Key, pair<Key, Value>> 模型）。

rbTree 的设计：
节点使用 __rb_tree_node，value 的具体含义根据容器类型不同而不同。

在这里插入图片描述


http://www.ppmy.cn/devtools/136812.html

相关文章

Dubbo Golang快速开发Rpc服务

Dubbo Golang快速开发Rpc服务

开发 RPC Server & RPC Client 基于 Dubbo 定义的 Triple 协议&#xff0c;你可以轻松编写浏览器、gRPC 兼容的 RPC 服务&#xff0c;并让这些服务同时运行在 HTTP/1 和 HTTP/2 上。Dubbo Go SDK 支持使用 IDL 或编程语言特有的方式定义服务&#xff0c;并提供一套轻量的 …
阅读更多...
【计算机网络】IP协议

【计算机网络】IP协议

一、IP协议的功能 提供将数据从A主机跨网络送到主机B的能力 (在复杂的网络环境中确定一个合适的路径) 二、IP协议格式 ​​​​​​​1.报头的含义 &#xff08;1&#xff09;一般字段 ① 4位版本&#xff1a;指定IP协议的版本&#xff0c;对于IPv4来说就是4 ② 4位首部长度…
阅读更多...
定时/延时任务-Timer用法

定时/延时任务-Timer用法

文章目录 1. 概要2. 简述2.1 固定速率2.2 固定延时2.3 区别 3. Timer 的用法3.1 固定延时 - public void schedule(TimerTask task, long delay, long period)3.1.1 解释 3.2 固定延时 - public void schedule(TimerTask task, Date firstTime, long period)3.3 固定速率 - pub…
阅读更多...
mfc100u.dll是什么?分享几种mfc100u.dll丢失的解决方法

mfc100u.dll是什么?分享几种mfc100u.dll丢失的解决方法

mfc100u.dll 是一个动态链接库&#xff08;DLL&#xff09;文件&#xff0c;属于 Microsoft Foundation Classes (MFC) 库的一部分。MFC 是微软公司开发的一套用于快速开发 Windows 应用程序的 C 类库。mfc100u.dll 文件包含了 MFC 库中一些常用的函数和类的定义&#xff0c;这…
阅读更多...
C++设计模式：建造者模式（Builder） 房屋建造案例

C++设计模式：建造者模式（Builder） 房屋建造案例

什么是建造者模式&#xff1f; 建造者模式是一种创建型设计模式&#xff0c;它用于一步步地构建一个复杂对象&#xff0c;同时将对象的构建过程与它的表示分离开。简单来说&#xff1a; 它将复杂对象的“建造步骤”分成多部分&#xff0c;让我们可以灵活地控制这些步骤。通过…
阅读更多...
设计模式-创建型-建造者模式

设计模式-创建型-建造者模式

1.概念 建造者设计模式&#xff08;Builder Design Pattern&#xff09;是一种创建型设计模式&#xff0c;它通过将一个复杂对象的构建过程与它的表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 2.作用 用于简化对复杂对象的创建 3.应用场景 当我们有一个非…
阅读更多...
P1 练习卷（C++4道题）

P1 练习卷（C++4道题）

1.纷繁世界 内存限制&#xff1a;256MB 时间限制&#xff1a;1s 问题描述 这是一个纷繁复杂的世界。 某一天清晨你起床很迟&#xff0c;没有吃上早饭。于是你骑着自行车去超市&#xff0c;但是你又发现商店的工作人员已经重新贴上了价格标签&#xff0c;零食价格都涨了50%。你…
阅读更多...
Redis核心数据结构与高性能原理

Redis核心数据结构与高性能原理

一、Redis安装 下载地址&#xff1a;http://redis.io/download 安装步骤&#xff1a; # 安装gcc yum install gcc# 把下载好的redis-5.0.3.tar.gz放在/usr/local文件夹下&#xff0c;并解压 wget http://download.redis.io/releases/redis-5.0.3.tar.gz tar -zxvf redis-5.0.3…
阅读更多...
最新文章

Copyright @ 2022~2023