封装map、set

embedded/2024/11/17 21:32:16/

红黑树中，封装map还是set是根据第二个节点参数决定的。
也就是说：树第一个参数是key，而第二个参数如果是set 就是 key，如果是map，则是pair。
请添加图片描述

RBTree.h#pragma once#include <iostream>
using namespace std;
#include <vector>
#include <set>enum Colour
{RED,BLACK
};template<class T> // T有可能是set中的key，也有可能是map中的pair
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){//中序遍历的下一个，对于当前节点而言，右树就是他的下一个，因此右不为空进循环if (_node->_right) {//下一个节点是右树的最左节点Node* leftMin = _node->_right;while (leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else //右树是空的，则向上找，找到一个节点是父亲的左节点停止{Node* cur = _node;Node* parent = cur->_parent;//向上找，如果父亲不为空且当前节点是父亲的右一直技能循环，直到找到一个节点是父亲的左节点停止while (parent&&cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};template<class K, class T, class KeyOfT> // T有可能是set中的key，也有可能是map中的pair
class RBTree
{typedef RBTreeNode<T> Node;
public:RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_data);newnode->_col = root->_col;newnode->_left = Copy(root->_left);if (newnode->_left)newnode->_left->_parent = newnode;newnode->_right = Copy(root->_right);if (newnode->_right)newnode->_right->_parent = newnode;return newnode;}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destory(_root);}void Destory(Node* root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}public:typedef __RBTreeIterator<T, T&, T*> Iterator;typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End() //迭代器是左闭右开的，因此End是最右节点的下一个 也就是NULL{return Iterator(nullptr);}ConstIterator Begin() const{Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return ConstIterator(leftMin);}ConstIterator End() const{return ConstIterator(nullptr);}Iterator Find(const K& key) //find需要第一个K的模板参数{Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_left;}else if (kot(cur->_data) >key){cur = cur->_right;}else{return Iterator(cur);}}return End();}pair<Iterator, bool> Insert(const T& data){//插入节点if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root), true);}//因此设计一个仿函数KeyOfT，利用这个函数返回出key就行了KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){//set data是key//map data是pair pair不支持所需要的比较，因为我只需要比较pair的第一个，而pair默认的可能会比较第二个值//kot对象 是用来取T类型的data中的keyif (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);//最后返回的是newnode的迭代器，因为如果发生了旋转，cur就不是插入的时候的cur了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;if (parent == grandfather->_left) //情况1{Node* uncle = grandfather->_right;//叔叔存在且为红->变色if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//变色后向上调整cur = grandfather;parent = cur->_parent;}else//叔叔不存在或者存在颜色为黑 则不用给u染色{if (cur == parent->_left) //情况2 3{RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else //cur == parent->right 情况4{RotateL(parent);RotateR(grandfather);cur->_col = BLACK; //旋转之后cur就在parent位置了，转变为94行代码的情况。grandfather->_col = RED;}break;}}else //右边的情况。{Node* uncle = grandfather->_left;//叔叔存在且为红色if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上调整cur = grandfather;parent = cur->_parent;}else //叔叔不存在或者是黑色{if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(Iterator(newnode), true);}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent; //得先把ppnode存下来才能更改parent->_parentparent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = subR;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = subR;}else{ppnode->_left = subR;}subR->_parent = ppnode;}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED)return false;int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refNum++;cur = cur->_left;}return _IsBalance(_root, 0, refNum);}private:bool _IsBalance(Node* root, int blackNum, const int refNum){if (root == nullptr){if (blackNum != refNum){cout << "存在个数不相同的黑色节点" << endl;return false;}return true;}if (root->_col == BLACK)blackNum++;if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}return _IsBalance(root->_left, blackNum, refNum)&& _IsBalance(root->_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}private:Node* _root = nullptr;
};
set.h#pragma once#include "RBTree.h"namespace ggg
{template<class K>class set{struct SetKeyOfT //写一个仿函数{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator; //const是为了不能修改Ktypedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();}iterator find(const K& key){return _t.Find(key);}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void PrintSet(const set<int>& s){for (auto e : s){cout << e << endl;}}void test_set(){set<int> s;s.insert(1);s.insert(7);s.insert(4);s.insert(0);s.insert(9);PrintSet(s);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << endl;++it;}set<int> copy = s;for (auto e : copy){cout << e << " ";}cout << endl;}
}

map.h#pragma once#include "RBTree.h"
#include <string>namespace ggg
{template<class K, class V>class map{struct MapKeyOfT //写一个仿函数{const K& operator()(const pair<K, V>& key){return key.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator; //const是为了传参让pair中的K不能修改typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator 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<K, V>& kv){return _t.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));return ret.first->second;}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};void test_map(){map<int,int> m;m.insert({ 3, 3 });m.insert({ 7, 7 });m.insert({ 0, 0 });m.insert({ 6, 6 });for (auto& e : m){cout << e.first << ":" << e.second << endl;}}void test_map2(){string arr[] = { "ggg1", "ggg2", "ggg2", "ggg2", "ggg3" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

http://www.ppmy.cn/embedded/138073.html

相关文章

C#入门 020 事件（类型成员）

C#入门 020 事件（类型成员）

初步了解事件 定义:单词Event&#xff0c;译为“事件” 《牛津词典》中的解释是“a thing that happens, especially something important通顺的解释就是“能够发生的什么事情” 角色:使对象或类具备通知能力的成员 事件(event)是一种使对象或类能够提供通知的成员对象O拥有…
阅读更多...
(蓝桥杯C/C++)——动态规划(DP)

(蓝桥杯C/C++)——动态规划(DP)

目录 一、线性DP 1.DP(动态规划)简介 2.动态规划的分析步骤 3.例题讲解 二、二维DP 1.二维DP简介 2.选数异或 三、最长上升子序列LIS 1.LIS简介 2.例题讲解 四、最长公共子序列LCS 1.最长公共子序列 2.最长公共子序列 2.求出具体子序列 一、线性DP 1.DP(动态规划)…
阅读更多...
动态规划-背包问题——1049.最后一块石头的重量II

动态规划-背包问题——1049.最后一块石头的重量II

1.题目解析 题目来源 1049.最后一块石头的重量II——力扣 测试用例 2.算法原理 首先需要将该问题转化为0-1背包问题后再做分析 1.状态表示 根据数学中的知识我们知道将一个数字分为两个子数后求这两个子数的最小差值&#xff0c;那么就要求这两个子数尽可能接近于原数字的一…
阅读更多...
【RabbitMQ】09-取消超时订单

【RabbitMQ】09-取消超时订单

生产者完成创建订单和扣减库存之后&#xff0c;发送消息到延迟队列。 // 3.清理购物车商品cartClient.deleteCartItemByIds(itemIds);// cartService.removeByItemIds(itemIds);// 4.扣减库存try {itemClient.deductStock(detailDTOS);//itemService.deductStock(detailDTOS);…
阅读更多...
解决Jenkins使用 Git 参数插件拉取 commit 列表缓慢问题

解决Jenkins使用 Git 参数插件拉取 commit 列表缓慢问题

Jenkins使用 Git 参数插件拉取 commit 列表缓慢问题 项目问题问题描述解决方案具体实现 项目问题 在 Jenkins 中使用 Git 参数插件 进行参数化构建&#xff0c;具有多方面的重要性和好处。这不仅提高了构建的灵活性和透明度&#xff0c;还能大大提升开发和运维效率。以下是使用…
阅读更多...
thinkphp route 配置 示例

thinkphp route 配置 示例

在 ThinkPHP 中&#xff0c;路由配置允许你将 URL 请求映射到指定的控制器和方法。路由配置文件一般位于 application/route.php 中&#xff0c;下面是一些常见的路由配置示例。 1. 基本路由配置 最基本的路由配置方式是将 URL 路径映射到指定的控制器方法。 use think\faca…
阅读更多...
前端开发迈向全栈之路：规划与技能

前端开发迈向全栈之路：规划与技能

一、前端开发与全栈开发的差异 前端开发主要负责构建和实现网页、Web 应用程序和移动应用的用户界面。其工作重点在于网页设计和布局&#xff0c;使用 HTML 和 CSS 技术定义页面的结构、样式和布局&#xff0c;同时运用前端框架和库如 React、Angular 或 Vue.js 等构建交互式和…
阅读更多...
0x00基础算法 -- 0x05 排序

0x00基础算法 -- 0x05 排序

1、离散化 排序算法的第一个应用&#xff1a;离散化。 “离散化”就是把无穷大&#xff08;无限&#xff09;的集合中的若干个&#xff08;有限&#xff09;元素映射为有限集合以便于统计的方法。 例如&#xff1a;问题的范围定义在整数集合&#xff0c;但是只涉及其中m个有限的…
阅读更多...
最新文章

Copyright @ 2022~2023