当前位置: 首页 > news >正文

【C++红黑树应用】模拟实现STL中的map与set

目录

  • 🚀 前言
  • 一: 🔥 红黑树的修改
  • 二: 🔥 红黑树的迭代器
  • 三: 🔥 perator++() 与 operator--()
  • 四: 🔥 红黑树相关接口的改造
    • ✨ 4.1 Find 函数的改造
    • ✨ 4.2 Insert 函数的改造
  • 五:🔥 Set 和 map的模拟实现
    • ✨ 5.1 Set的基本设计
    • ✨ 5.2 Map的基本设计
  • 六:📖 红黑树改造的完整代码及总结

🚀 前言

红黑树类的实现参考上一篇文章:【C++高阶数据结构】红黑树:全面剖析与深度学习
之前我们已经学习了如何手搓一棵红黑树,现在让我们来对红黑树进行改造,并且封装成map和set.

我们通过观察其stl源码切入进行仿写:
在这里插入图片描述
我们发现无论是map还是set都复用的一个红黑树,模板参数都是k,v模型通过源码我们可以发现:set -> rb_tree<k, k> | | map<k, v> -> rb_tree<k, pair<const k, v>>。所以节点中存什么内容是由v决定的,不是k决定的。将红黑树写成泛型,所以我们必须将之前写的红黑树的模板进行修改!

一: 🔥 红黑树的修改

【改造前】


template<class K, class T>
class RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:RBTree() :_root(nullptr) {}  // 构造函数bool Insert(const T& data);  // 插入节点// ...
private:Node* _root;
};

红黑树的插入节点接口中要先通过比较节点中数据的大小来查找适合插入的位置,但是红黑树并不知道数据 data 到底是 key 还是 pair。如果数据 data 是 key,那么直接取 key 来作比较;如果数据 data 是 pair,则需要取 first 来作比较。

  • 所以我们就得使用仿函数进行操作,我们创建keyoft仿函数取出T对象中的key即可

在这里插入图片描述
【改造后】

红黑树的定义

  • K:键值key的类型。
  • T:数据的类型,如果是 map,则为 pair<const K, V>;如果是 set,则为 K。
  • KeyOfT:通过 T 的类型来获取 key 值的一个仿函数类。
template<class K, class T, class KeyOfT>
class RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:RBTree() :_root(nullptr) {}  // 构造函数bool Insert(const T& data);  // 插入节点(接口返回值目前是bool,后续要改为pair)// ...
private:Node* _root;
};

二: 🔥 红黑树的迭代器

迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代
器,需要考虑以前问题:begin()与end()

STL明确规定,begin()与end()代表的是一段前闭后开的区间,而对红黑树进行中序遍历后,
可以得到一个有序的序列。

SGI-STL源码中,红黑树有一个哨兵位的头节点,begin() 是放在红黑树中最小节点(即最左侧节点)的位置,end() 是放在 end() 放在头结点的位置。

本文所采取的方式并没有使用头节点,而是通过其他方法实现,使用空指针代表end()


template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node; // 红黑树节点
public:typedef _RBTreeIterator<T, T&, T*> iterator; // 迭代器iterator begin() // begin(): 指向红黑树的最左节点的迭代器{Node* left = _root;while (left && left->_left){left = left->_left;}return iterator(left);// 注意:单参数的构造函数支持隐式类型转换,节点会被构造成迭代器// 所以也可以这样写:return left;}iterator end() // end(): 指向nullptr的迭代器{return iterator(nullptr);}
private:Node* _root = nullptr;
};

三: 🔥 perator++() 与 operator–()

  1. operator++()
  • 右不为空,右子树的最左节点
  • 右为空,沿着到根的路径找孩子是父亲左的那个祖先
  1. operator–()
  • 左不为空,左子树的最右节点
  • 左为空,沿着到根的路径找孩子是父亲右的那个祖先

template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){// 右不为空,右子树最左节点就是中序下一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr)            // end()情况特殊处理{// end()--  走到最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 右不为空,右子树最左节点就是中序下一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}
};
}

四: 🔥 红黑树相关接口的改造

✨ 4.1 Find 函数的改造

查找成功,返回查找到的那个节点的迭代器,查找失败,就返回 nullptr。

Iterator Find(const K& key)
{KeyOfT kot;              // 仿函数类的对象Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur, _root);}}return End();
}

✨ 4.2 Insert 函数的改造

注意:map 里的 operator[] 需要依赖 Insert 的返回值

pair<Iterator, bool> Insert(const T& data)
{if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root, _root), true);}KeyOfT kot;        // 仿函数// 找到插入位置Node* cur = _root, * parent = nullptr;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, _root), false);}}cur = new Node(data);Node* newnode = cur;//	新增节点 颜色优先选择红色cur->_col = RED;if (kot(data) > kot(parent->_data)) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在,cur就是根了,出去后把根处理成黑的// 2、parent存在,且为黑// 3、parent存在,且为红,继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理(来连续的红节点, 关键看叔叔){Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  p   u//    c// 双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}else {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);
}

五:🔥 Set 和 map的模拟实现

✨ 5.1 Set的基本设计

set的底层为红黑树,因此只需在set内部封装一棵红黑树,即可将该容器实现出来。

为了解决 set 中 key 值不能修改的问题,在传给 RBTree 的第二个模板参数前加 const 即可。

#pragma once#include"RBTree.h"namespace bit
{template<class K>class set{   // 取出 keyofvalue 的仿函数类struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;typedef 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();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}iterator find(const K& key){return _t.Find(key);}private:RBTree<K, const K, SetKeyOfT> _t;};void Print(const set<int>& s){set<int>::const_iterator it = s.end();while (it != s.begin()){--it;//*it += 2;cout << *it << " ";}cout << endl;}void test_set(){bit::set<int> s;int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << ' ';}set<int>::iterator it = s.end();while (it != s.begin()){--it;cout << *it << " ";}cout << '\n';}
}

✨ 5.2 Map的基本设计

#pragma once#include"RBTree.h"namespace bit
{template<class K, class V>class map{// 取出 keyofvalue 的仿函数类struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;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);}iterator find(const K& key){return _t.Find(key);}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(){map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边,剩余";dict["insert"] = "插入";dict["string"];map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first,可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;}}

六:📖 红黑树改造的完整代码及总结

#pragma once#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include <assert.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){}
};template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;Node* _root;RBTreeIterator(Node* node, Node* root):_node(node),_root(root){}Self& operator++(){if (_node->_right){// 右不为空,右子树最左节点就是中序下一个Node* leftMost = _node->_right;while (leftMost->_left){leftMost = leftMost->_left;}_node = leftMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator--(){if (_node == nullptr)            // end()情况特殊处理{// end()--  走到最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){// 右不为空,右子树最左节点就是中序下一个Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!= (const Self& s){return _node != s._node;}
};// T可以是key 也可以是map 三个参数中第一个key是给find和 erase的   pair和第二个key是给insert的
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*> ConstIterator;Iterator Begin(){Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator Begin() const{Node* leftMost = _root;while (leftMost && leftMost->_left){leftMost = leftMost->_left;}return ConstIterator(leftMost, _root);}ConstIterator End() const{return ConstIterator(nullptr, _root);}RBTree() = default;RBTree(const RBTree<K, T, KeyOfT>& t){_root = Copy(t._root);}RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t){swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root = nullptr;}pair<Iterator, bool> Insert(const T& data){if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(Iterator(_root, _root), true);}KeyOfT kot;        // 仿函数// 找到插入位置Node* cur = _root, * parent = nullptr;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, _root), false);}}cur = new Node(data);Node* newnode = cur;//	新增节点 颜色优先选择红色cur->_col = RED;if (kot(data) > kot(parent->_data)) parent->_right = cur;else parent->_left = cur;cur->_parent = parent;// 1、parent不存在,cur就是根了,出去后把根处理成黑的// 2、parent存在,且为黑// 3、parent存在,且为红,继续循环处理// 变色了之后持续网上处理while (parent && parent->_col == RED)          // 父亲颜色是红色就需要继续处理(来连续的红节点, 关键看叔叔){Node* grandfather = parent->_parent;if (parent == grandfather->_left)               // 父亲在爷爷的左边 右边就是对称的{Node* uncle = grandfather->_right;//    g//  p   uif (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  p   u// c// 单旋if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  p   u//    c// 双旋RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}else {//    g//  u   pNode* uncle = grandfather->_left;if (uncle && uncle->_col == RED)     // 如果叔叔存在且为红色{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = grandfather->_parent;}else {                               // 叔叔存在且为黑或者不存在  那么旋转+变色//    g//  u   p//        c// 单旋if (cur == parent->_right){RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else {//    g//  u   p//    c// 双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;                           // 局部根节点是黑色那么就可以退出了}}}_root->_col = BLACK;return make_pair(Iterator(newnode, _root), true);}Iterator Find(const K& key){KeyOfT kot;Node* cur = _root;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return Iterator(cur, _root);}}return End();}Node* Copy(Node * root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_kv);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destroy(Node * root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}// 检查是否是红黑树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 Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << '\n';return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}void RotateL(Node * parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;Node* parent_parent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent_parent == nullptr){_root = subR;subR->_parent = nullptr;}else {if (parent == parent_parent->_left) parent_parent->_left = subR;else parent_parent->_right = subR;subR->_parent = parent_parent;}}void RotateR(Node * parent){Node* subL = parent->_left;Node* subLR = parent->_left->_right;parent->_left = subLR;if (subLR) subLR->_parent = parent;Node* parent_parent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (parent_parent == nullptr){_root = subL;subL->_parent = nullptr;}else {if (parent == parent_parent->_left){parent_parent->_left = subL;}else {parent_parent->_right = subL;}subL->_parent = parent_parent;}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << '\n';_InOrder(root->_right);}Node* _root = nullptr;};//void TestRBTree1()
//{
//	RBTree<int, int> t;
//	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//	// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
//	for (auto e : a)
//	{
//
//		t.Insert({ e, e });
//	}
//
//	t.InOrder();
//	cout << t.IsBalance() << endl;
//}

以上就是红黑树的改造及封装map和set全部内容,需要我们好好掌握,觉得这篇博客对你有帮助的,可以点赞收藏关注支持一波~😉
在这里插入图片描述

相关文章:

【C++红黑树应用】模拟实现STL中的map与set

目录 &#x1f680; 前言一&#xff1a; &#x1f525; 红黑树的修改二&#xff1a; &#x1f525; 红黑树的迭代器 三&#xff1a; &#x1f525; perator() 与 operator--() 四&#xff1a; &#x1f525; 红黑树相关接口的改造✨ 4.1 Find 函数的改造✨ 4.2 Insert 函数的改…...

前端实习手计(5):班味十足?!

自我感觉没有班味&#xff01;&#xff01;&#xff01;每天还是快快乐乐上班哇&#xff0c;是愉快的一周~这周没有太多活咯&#xff0c;基本就是修修改改改代码学习。真的感觉自己写的代码就是乱七八糟&#xff0c;只要能跑起来有效果就行&#xff08;我不是合格的处女座哈哈哈…...

Duix AI 太上瘾,让我熬夜体验的AI女友

✨点击这里✨&#xff1a;&#x1f680;原文链接&#xff1a;&#xff08;更好排版、视频播放、社群交流、最新AI开源项目、AI工具分享都在这个公众号&#xff01;&#xff09; Duix AI 太上瘾&#xff0c;让我熬夜体验的AI女友 开启 Duix AI 女友的奇妙之旅_ Hi&#xff0c;这…...

php判断某个目录下是否存在文件

/*** 判断字符串是否以什么结尾* param String $haystack 字符串* param String $needle 结尾* return Boolean*/ function endWith($haystack, $needle) {$length strlen($needle);if ($length 0) {return true;}return (substr($haystack, -$length) $needle); } /***…...

重塑互联网生态:探索Web 3.0、大数据与隐私保护的新篇章

引言&#xff1a;互联网的新纪元 随着互联网技术的日新月异&#xff0c;我们正迈入一个全新的时代&#xff0c;其中Web 3.0、大数据以及隐私保护成为塑造未来互联网生态的三大核心力量。它们不仅改变了我们与互联网交互的方式&#xff0c;更深刻地影响着社会的方方面面。 Web…...

HR模块中PA信息类型的相关函数

目录 1、新增、删除&#xff0c;修改&#xff1a;HR_INFOTYPE_OPERATION新增&#xff1a;INS删除&#xff1a;DEL修改&#xff1a;MOD 2、读取PA信息类型&#xff1a;HR_READ_INFOTYPE3、入职&#xff0c;生成新工号用&#xff1a;HR_PAD_HIRE_EMPLOYEE4、加锁&#xff1a;BAPI…...

c# 日期类型变量默认值

DateTime类型是比较常用的变量类型&#xff0c;但是以前处理都比较业余&#xff0c;下面总结2中常用方式 这次把它总结下&#xff1a; DateTime t1 default(DateTime); DateTime t2 DateTime.MinValue; 这样t1&#xff0c;t2 的值都是 {0001/1/1 0:00:00} PS: 由于DateTi…...

设计模式实战:任务调度系统的设计与实现

问题描述 设计一个任务调度系统,支持任务的创建、调度、执行和状态管理。系统需要确保任务的执行过程可以被灵活调度,并且支持任务状态的跟踪和通知功能。 设计分析 命令模式 命令模式用于将请求封装成对象,从而使我们可以用不同的请求、队列或日志来参数化其他对象。任…...

代码中的特殊注释

代码中特殊注释——TODO、FIXME、XXX、HACK_fix me todo hack-CSDN博客 代码中特殊注释——TODO、FIXME、XXX、HACK TODO&#xff1a;英语翻译为待办事项&#xff0c;备忘录。如果代码中有该标识&#xff0c;说明在标识处有功能代码待编写&#xff0c;待实现的功能在说明中会…...

ubuntu20.04.6 安装Skywalking 10.0.1

1.前置准备 1.1. **jdk17&#xff08;Skywalking10 jdk22不兼容&#xff0c;用17版本即可&#xff09;**安装&#xff1a; https://blog.csdn.net/CsethCRM/article/details/140768670 1.2. elasticsearch安装&#xff1a; https://blog.csdn.net/CsethCRM/article/details…...

C++:map和set

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起学习《C&#xff1a;map和set》&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 &#xff01; 如果本篇文章对你有帮助&#xff0c;还请各位点点赞&#xff01;&#xff01;…...

深入理解二叉搜索树:定义、操作及平衡二叉树

引言 二叉搜索树&#xff08;Binary Search Tree&#xff0c;BST&#xff09;是一种特殊的二叉树结构&#xff0c;每个节点的左子树节点值小于根节点值&#xff0c;而右子树节点值大于根节点值。二叉搜索树在计算机科学中有着广泛的应用&#xff0c;尤其在动态查找表和优先队列…...

vue3组件通信(二)

组件通信 一.$attrs(祖>孙间接&#xff09;二、$refs()父>子&#xff0c; $parent()子>父三.provide&#xff0c;inject(祖>孙直接&#xff09;四.pinia五.slot1.默认插槽2.具名插槽3.作用域插槽 一.$attrs(祖>孙间接&#xff09; $attrs用于实现当前组件的父组…...

关键词查找【Boyer-Moore 算法】

1、【Boyer-Moore 算法】 【算法】哪种算法有分数复杂度&#xff1f;- BoyerMoore字符串匹配_哔哩哔哩_bilibili BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较&#xff0c;而…...

【前端手写代码】手写Object.create

思路&#xff1a;将传入的对象作为原型 // 思路&#xff1a;将传入的对象作为原型 function create(obj) {function F() { }F.prototype objreturn new F() }...

速通JS模块化规范

目录 1模块化概述 1.1什么是模块化&#xff1f; 1.2为什么需要模块化&#xff1f; 2有哪些模块化规范&#xff1f; 3导入与导出的概念 4CommonJS 规范 4.1初步体验 4.2导出数据 4.3导入数据 4.4扩展理解 4.5浏览器端运行 5ES6 模块化规范 5.1初步体验 5.2Node 中运…...

HamonyOS性能优化工具和方法

性能优化&#xff0c;如何做到更快的启动、更流畅的使用&#xff0c;概括图如下 ArkTS高性能编程&#xff1a; 1. ArkTS规则&#xff1a;有利于方舟编译运行时进行编译优化 2. 使用AOT(Ahead Of Time)模式对应用进行编译优化&#xff1a;方舟编译运行时通过采用PGO(Profile-Gui…...

前端实现边下载文件边上传

问题记录原因&#xff1a; 因为需要实现网络文件的上传&#xff0c;结果是由前端实现&#xff0c;方式是一边下载&#xff0c;一遍上传文件&#xff0c;小文件直接上传&#xff0c;大文件进行切片&#xff0c;切片大小和下载大小有关&#xff0c;特此记录。 1.实现方案 fetc…...

滑线变阻器的优缺点是什么?

滑线变阻器是常见的电子元件&#xff0c;主要用于调节电路中的电阻值&#xff0c;从而达到改变电流、电压的目的。它的主要优点是结构简单、操作方便、成本低&#xff0c;因此在各种电子设备中都有广泛的应用。然而&#xff0c;滑线变阻器也存在一些缺点&#xff0c;主要表现在…...

K8s大模型算力调度策略的深度解析

随着大数据和人工智能技术的飞速发展&#xff0c;Kubernetes&#xff08;简称K8s&#xff09;作为容器编排的领军者&#xff0c;在支撑大规模模型训练和推理方面扮演着越来越重要的角色。在大模型算力的调度过程中&#xff0c;如何高效、合理地分配和管理资源成为了一个亟待解决…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...