【C++】map和set的封装

news/2024/10/18 8:32:24/

文章目录

    • 一、前情回顾
    • 二、简化源码
    • 三、仿函数
    • 四、迭代器
    • 五、set的实现
    • 六、map的实现
    • 七、红黑树代码

一、前情回顾

set 参数只有 key，但是map除了key还有value。我们还是需要KV模型的红黑树的：

#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{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;Color _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* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;//情况一：u存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2if (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}//情况3else{//       g//  p//    c RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else//parent==grandfater->_right{Node* uncle = grandfater->_left;//情况1：u存在且为红色if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2：u不存在/u存在为黑色//g//    p//        cif (cur == parent->_right){RotateL(grandfater);grandfater->_col = RED;parent->_col = BLACK;}//情况3//     g//         p//      celse{RotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}//根变黑_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool Check(Node*root,int blackNum,int ref){if (root == nullptr){//cout << blackNum << endl;if (blackNum != ref){cout << "违反规则：本条路径的黑色结点的数量根最左路径不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续的红色结点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left,blackNum,ref)&& Check(root->_right,blackNum,ref);}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}int ref = 0;Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root,0,ref);}
private:Node* _root = nullptr;
};

二、简化源码

翻开源码一看📕

RBTree的结构源码：是KV结构的红黑树

RBTree是通过传入的Value的值来判断类型，也就是一棵泛型的RBTree，通过不同的实例化，实现出了Map和Set：

对于map:传key，对于set:传pair

map的结构简化源码：

image-20230216171130319

set的结构简化源码：

image-20230216171212456

为了让我们的红黑树能够识别set与map我们增加一个模板参数T：

template<class K, class T>
class RBTree

对于T模板参数可能是键值Key，也可能是由Key和Value共同构成的键值对。

如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key：

template<class K>
class set
{private:RBTree<K,K> _t;
};

如果是map容器，传入底层红黑树的模板参数就是Key和Key和value的键值对：

class map
{
private:RBTree<K, pair<const K,V>> _t;
};

通过上面，我们可以知道，对于set和map的区别：我们只要通过第二个模板参数就能进行区分，那是不是第一个模板参数就没有意义了呢？

对于insert(const Value&v)来说，需要放入存入的值，确实是这个样子的，插入的值是value，对于set就是key，对于map就是pair。

但是对于find(const Key&key)来说，查找的参数不是value，找的不是pair而是Key，对于map容器来说就不行了。

**红黑树的节点**：set容器：K和T都是键值Key; map容器：K是键值Key，T由Key和Value构成的键值对；但是底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了，如果是set的时候，结点当中存储的是键值Key；如果是map的时候，结点当中存储的就是键值对,所以红黑树的结点定义如下,由T类型来决定红黑树存的是key还是pair：

template<class T>//三叉链结构
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};

三、仿函数

这里存在一个问题📝：插入的时候data的大小如何去进行比较：我们并不知道是什么类型是key，还是pair的比较，而我们刚开始kv结构就直接用kv.first去比较了。

对于set是Key，可以比较

对于map是pair，那我们要取其中的first来比较，但是pair的大小并不是直接按照first去进行比较的，而我们只需要按照first去进行比较

由于底层的红黑树不知道传的是map还是set容器，当需要进行两个结点键值的比较时，底层红黑树传入的仿函数来获取键值Key，进行两个结点键值的比较：这个时候我们就需要仿函数了，如果是set那就是用于返回T当中的键值Key,如果是map那就是用于返回pair的first：

仿函数/函数对象也是类，是一个类对象。仿函数要重载operator()。

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

namespace HWC
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:RBTree<K,K,SetKeyOfT> _t;};

博主画了个图更加容易进行比对👇

image-20230216191436991

查找过程，此时就可以套上我们所写的仿函数对象去进行数据的大小比较了：

        KeyOfT kot;//仿函数对象Node* parent = nullptr;Node* cur = _root;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 false;}}

四、迭代器

红黑树的正向迭代器是对结点指针进行了封装，所以这里的正向迭代器就只有一个成员变量：结点的指针，并没有什么其他的地方，迭代器的定义：

template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T,Ref,Ptr> Self;typedef __RBTreeIterator<T, T&, T*> iterator;Node* _node;__RBTreeIterator(Node*node):_node(node){}//普通迭代器的时候，它是拷贝构造//const迭代器的时候，它是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator& s):_node(s._node){}
}

*:解引用操作，返回对应结点数据的引用:

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

->:成员访问操作符,返回结点数据的引用：

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

!=、==:比较简单

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

这里的迭代器重点是迭代器的++:

一个结点的正向迭代器进行++操作后，根据红黑树中序(左、根、右)找到当前结点的下一个结点，中序的第一个节点是最左，迭代器的++怎么去找：

如果节点的右子树不为空，++就是找右子树的最左节点

如果节点的右子树为空，++就是找祖先（孩子是父亲的左的那个祖先）

代码实现✍：

	Self& operator++(){if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}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--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent&&cur==parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}

不要忘记迭代器的两个核心成员：begin()与end()

begin()：返回中序（左、根、右）第一个结点的正向迭代器，即最左节点，返回的是最左节点,直接找最左节点即可

end()：返回中序（左、根、右）最后一个结点下一个位置的正向迭代器，这里直接用空指针

template<class K, class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T> iterator;iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}
}

五、set的实现

通过前面底层红黑树的接口进行套用即可实现set的实现：

值得注意的是🔴：typename:没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型

#pragma once
#include "RBTree.h"namespace hwc
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public://typename:没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;//key不可以修改typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const {return _t.begin();}iterator end() const {return _t.end();}pair<iterator,bool> insert(const K& key){//底层红黑树的iterator是普通迭代器pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret =  _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);//用普通迭代器构造const迭代器}private:RBTree<K, K,SetKeyOfT> _t;};void test_set(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };set<int> s;for (auto e : a){s.insert(e);}set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}
}

六、map的实现

同样是套用上底层红黑树的接口，不过map的实现有一个很重要的地方，那就是[]的实现

#pragma once
#include "RBTree.h"
namespace hwc
{template<class K,class V>class map{struct MapkeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public://typename:没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, MapkeyOfT>::const_iterator const_iterator;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<const 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;};void test_map(){int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };map<int, int> m;for (auto e : a){m.insert(make_pair(e, e));}map<int, int>::iterator it = m.begin();while(it!=m.end()){it->second++;cout << it->first << ":" << it->second << endl;++it;}cout << endl;map<string, int> countMap;string arr[] = { "苹果","西瓜","香蕉","苹果"};for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}

七、红黑树代码

最后，在这里送上源码：

#pragma once#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;
enum Color
{RED,BLACK,
};
template<class T>
struct RBTreeNode
{T _data;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};template<class T,class Ref,class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T,Ref,Ptr> Self;typedef __RBTreeIterator<T, T&, T*> iterator;Node* _node;__RBTreeIterator(Node*node):_node(node){}//普通迭代器的时候，它是拷贝构造//const迭代器的时候，它是构造，支持用普通迭代器构造const迭代器__RBTreeIterator(const iterator& s):_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){Node* min = _node->_right;while (min->_left){min = min->_left;}_node = min;}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--(){if (_node->_left){Node* max = _node->_left;while (max->_right){max = max->_right;}_node = max;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent&&cur==parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator !=(const Self & s) const{return _node != s._node;}bool operator ==(const Self& s) const{return _node == s._node;}
};template<class K, class T,class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef __RBTreeIterator<T,T&,T*> iterator;typedef __RBTreeIterator<T,const T&,const T*> const_iterator;const_iterator begin() const {Node* left = _root;while (left && left->_left){left = left->_left;}return const_iterator(left);}const_iterator end() const {return const_iterator(nullptr);}iterator begin(){Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pair<iterator,bool> Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root),true);}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;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;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;//情况一：u存在且为红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2if (cur == parent->_left){RotateR(grandfater);parent->_col = BLACK;grandfater->_col = RED;}//情况3else{//       g//  p//    c RotateL(parent);RotateR(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}else//parent==grandfater->_right{Node* uncle = grandfater->_left;//情况1：u存在且为红色if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandfater->_col = RED;//向上调整cur = grandfater;parent = cur->_parent;}else{//情况2：u不存在/u存在为黑色//g//    p//        cif (cur == parent->_right){RotateL(grandfater);grandfater->_col = RED;parent->_col = BLACK;}//情况3//     g//         p//      celse{RotateR(parent);RotateL(grandfater);cur->_col = BLACK;grandfater->_col = RED;}break;}}}//根变黑_root->_col = BLACK;return make_pair(iterator(newnode),true);}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR;if (ppNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subR;}else{ppNode->_right = subR;}subR->_parent = ppNode;}}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppNode = parent->_parent;parent->_parent = subL;subL->_right = parent;if (ppNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (ppNode->_left == parent){ppNode->_left = subL;}else{ppNode->_right = subL;}subL->_parent = ppNode;}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool Check(Node* root, int blackNum, int ref){if (root == nullptr){//cout << blackNum << endl;if (blackNum != ref){cout << "违反规则：本条路径的黑色结点的数量根最左路径不相等" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "违反规则：出现连续的红色结点" << endl;return false;}if (root->_col == BLACK){++blackNum;}return Check(root->_left, blackNum, ref)&& Check(root->_right, blackNum, ref);}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col != BLACK){return false;}int ref = 0;Node* left = _root;while (left){if (left->_col == BLACK){++ref;}left = left->_left;}return Check(_root, 0, ref);}
private:Node* _root = nullptr;
};

本篇结束…


http://www.ppmy.cn/news/26572.html

相关文章

【C++】类和对象练习——日期类的实现

【C++】类和对象练习——日期类的实现

文章目录前言1. 日期的合法性判断2. 日期天数&#xff08;/&#xff09;2.1 和的重载2.2 对于两者复用的讨论3. 前置和后置重载4. 日期-天数&#xff08;-/-&#xff09;5. 前置- -和后置- -的重载6. 日期-日期7. 流插入<<重载8. 流提取>>重载9. 总结10. 源码展示前…
阅读更多...
【腾讯一面】我对我的Java基础不自信了

【腾讯一面】我对我的Java基础不自信了

我对我的Java基础不自信了1、List和set的区别&#xff1f;2、HashSet 是如何保证不重复的3、HashMap是线程安全的吗&#xff0c;为什么不是线程安全的&#xff1f;4、HashMap的扩容过程5、Java获取反射的三种方法6、Redis持久化机制原理7、redis持久化的方式各有哪些优缺点1、L…
阅读更多...
Spring中的AOP

Spring中的AOP

Spring中的AOP 文章目录Spring中的AOPAOP概述相关术语总结作用AOP概述 AOP(Aspect Programming) 是一种设计思想&#xff0c;是面向切面编程思想 跟OOP(面向对象编程)有什么关系呢&#xff1f; AOP面向切面编程然后是OOP&#xff08;面向对象编程&#xff09;的补充和完善。…
阅读更多...
计算机网络笔记（五）—— 网络层

计算机网络笔记（五）—— 网络层

网络层概述 网络层的主要任务是实现网络互连&#xff0c;进而实现数据包在各网络之间的传输。 需要解决的问题&#xff1a; 网络层提供的两种服务 1. 面向连接的虚电路&#xff08;逻辑上的连接&#xff0c;而不是物理连接&#xff09;服务 2. 无连接的数据报服务&#xff…
阅读更多...
第11篇：Java开发工具使用和代码规范配置

第11篇：Java开发工具使用和代码规范配置

目录 1、IntelliJ IDEA 简介 2. IntelliJ IDEA 下载 3. IntelliJ IDEA 安装和使用 3.1 安装到Windows下 3.2 快速编写 Hello World 程序
阅读更多...
模拟实现string

模拟实现string

目录 1、基本成员变量 2、默认成员函数 构造函数 析构函数 拷贝构造函数(深拷贝) 赋值运算符重载 3、容量与大小相关的函数 size capacity 4、字符串访问相关函数 operator [ ]重载 迭代器 5、增加的相关函数 reserve扩容 resize push_back追加字符 appe…
阅读更多...
使用Vue3实现一个可复制的表格

使用Vue3实现一个可复制的表格

前言 表格是前端非常常用的一个控件&#xff0c;但是每次都使用v-for指令手动绘制tr/th/td这些元素是非常麻烦的。同时&#xff0c;基础的 table 样式通常也是不满足需求的&#xff0c;因此一个好的表格封装就显得比较重要了。 最基础的表格封装 最基础基础的表格封装所要做…
阅读更多...
基于Spring Boot的零食商店

基于Spring Boot的零食商店

文章目录项目介绍主要功能截图&#xff1a;登录后台首页个人信息管理用户管理前台首页购物车部分代码展示设计总结项目获取方式&#x1f345; 作者主页&#xff1a;Java韩立 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关…
阅读更多...
最新文章

Copyright @ 2022~2023