企业官网建设流程全解析

中山网络公司网站建设,网站开发答辩ppt,阿里巴巴商标注册官网,利用赞赏码做网站收款关注我#xff0c;学习c不迷路: 个人主页#xff1a;爱装代码的小瓶子 专栏如下#xff1a; c学习Linux学习 后续会更新更多有趣的小知识#xff0c;关注我带你遨游知识世界 期待你的关注。 文章目录1. 改造红黑树#xff1a;适应泛型1.1 模板参数的变化1.2 核心魔法学习c不迷路:个人主页爱装代码的小瓶子专栏如下c学习Linux学习后续会更新更多有趣的小知识关注我带你遨游知识世界期待你的关注。文章目录1. 改造红黑树适应泛型1.1 模板参数的变化1.2 核心魔法KeyOfT2. 完善后的红黑树代码 (RBTree.h)3. 封装实现 MySet4. 封装实现 MyMap5. 测试代码总结这篇博客将带你像 STL 源码一样用同一棵红黑树底座同时衍生出MyMap和MySet。前言在上一篇文章中我们已经手搓了一棵高性能的红黑树RBTree。但是如果我们看 STL 的源码会发现std::map和std::set底层竟然用的是同一个红黑树模板既然 Set 存的是Key而 Map 存的是pairK, V它们是如何共用同一套代码的呢今天哆啦A梦就带大家钻进源码的“任意门”揭秘其中的泛型编程技巧——KeyOfT仿函数。1. 改造红黑树适应泛型要让红黑树既能存int(Set)又能存pair(Map)我们需要对红黑树的模板参数进行改造。1.1 模板参数的变化原来的定义// 只能针对特定类型不够灵活templateclassK,classVclassRBTree{...};改造后的定义// K: 键值类型用于查找、比较// T: 节点中实际存储的数据类型Set是KMap是pairK,V// KeyOfT: 仿函数用于从 T 中提取出 KtemplateclassK,classT,classKeyOfTclassRBTree{...};1.2 核心魔法KeyOfT这是封装的精髓。因为节点里存的是T红黑树在比较大小时需要用K。如果是SetT就是K直接返回。如果是MapT是pair我们需要取出first。我们在红黑树内部不再直接比较data而是这样写KeyOfT kot;// 实例化仿函数if(kot(data)kot(cur-_data)){...}2. 完善后的红黑树代码 (RBTree.h)这是基于我们之前修复过 Bug修复了迭代器和 Find 逻辑的最终版本。为了节省篇幅只展示核心修改部分。#pragmaonce#includeiostream#includevector#includeassert.husingnamespacestd;enumColor{RED,BLACK};templateclassTstructRBTreeNode{RBTreeNodeT*_left;RBTreeNodeT*_right;RBTreeNodeT*_parent;T _data;// T 可能是 Key也可能是 pairK,VColor _col;RBTreeNode(constTdata):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}};// 迭代器实现复用之前的修复版templateclassT,classRef,classPtrstruct__RBTreeIterator{typedefRBTreeNodeTNode;typedef__RBTreeIteratorT,Ref,PtrSelf;Node*_node;Node*_root;__RBTreeIterator(Node*node,Node*root):_node(node),_root(root){}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}// ... operator 和 operator-- 的代码与之前修复版一致 ...// 重点Map 的 Value 允许修改Key 不允许Set 都不允许。// 这通过传递 const T 或 T 来控制。};// 红黑树主体templateclassK,classT,classKeyOfTclassRBTree{typedefRBTreeNodeTNode;public:typedef__RBTreeIteratorT,T,T*iterator;typedef__RBTreeIteratorT,constT,constT*const_iterator;// 插入逻辑改造pairiterator,boolInsert(constTdata){if(_rootnullptr){_rootnewNode(data);_root-_colBLACK;returnmake_pair(iterator(_root,_root),true);}KeyOfT kot;// 核心提取 Key 的工具人Node*parentnullptr;Node*cur_root;while(cur){// 所有的比较都通过 kot 提取 key 后进行if(kot(data)kot(cur-_data)){parentcur;curcur-_left;}elseif(kot(data)kot(cur-_data)){parentcur;curcur-_right;}else{returnmake_pair(iterator(cur,_root),false);}}// ... 剩下的插入节点、变色、旋转逻辑保持不变 ...// ... 注意 new Node(data) ...returnmake_pair(iterator(newnode,_root),true);}// 查找逻辑改造iteratorFind(constKkey){KeyOfT kot;Node*cur_root;while(cur){if(keykot(cur-_data))curcur-_left;elseif(keykot(cur-_data))curcur-_right;elsereturniterator(cur,_root);}returnend();}iteratorbegin(){Node*cur_root;while(curcur-_left)curcur-_left;returniterator(cur,_root);}iteratorend(){returniterator(nullptr,_root);}private:Node*_rootnullptr;};3. 封装实现 MySetSet 的特点是存储的是 Key。迭代器不可修改底层是const_iterator。#includeRBTree.hnamespacebit{templateclassKclassset{// 1. 定义仿函数怎么从 K 中取 K直接返回自己即可structSetKeyOfT{constKoperator()(constKkey){returnkey;}};public:// 2. 实例化红黑树// K: 查找类型// K: 存储类型// SetKeyOfT: 提取方式typedeftypenameRBTreeK,K,SetKeyOfT::const_iterator iterator;typedeftypenameRBTreeK,K,SetKeyOfT::const_iterator const_iterator;pairiterator,boolinsert(constKkey){// Set 的普通迭代器本质也是 const 迭代器防止修改 Key 破坏树结构autoret_t.Insert(key);returnpairiterator,bool(ret.first,ret.second);}iteratorbegin()const{return_t.begin();}iteratorend()const{return_t.end();}private:RBTreeK,K,SetKeyOfT_t;};}4. 封装实现 MyMapMap 的特点是存储的是pairconst K, V。支持operator[]。迭代器可以修改 Value但不能修改 Key。#includeRBTree.hnamespacebit{templateclassK,classVclassmap{// 1. 定义仿函数怎么从 pair 中取 K返回 firststructMapKeyOfT{constKoperator()(constpairK,Vkv){returnkv.first;}};public:// 2. 实例化红黑树// 存储类型 T 是 pairconst K, Vconst K 保证了 Key 不会被迭代器修改typedeftypenameRBTreeK,pairconstK,V,MapKeyOfT::iterator iterator;pairiterator,boolinsert(constpairK,Vkv){return_t.Insert(kv);}// 3. 实现核心功能方括号访问// 逻辑插入 key。如果存在返回对应 iterator如果不存在插入默认值并返回 iterator。Voperator[](constKkey){pairiterator,boolretinsert(make_pair(key,V()));// ret.first 是迭代器- 解引用拿到 pair.second 拿到 Valuereturnret.first-second;}iteratorbegin(){return_t.begin();}iteratorend(){return_t.end();}private:RBTreeK,pairconstK,V,MapKeyOfT_t;};}5. 测试代码让我们来验证一下大雄我们的代码是否健壮voidTestMap(){bit::mapstring,stringdict;dict.insert(make_pair(sort,排序));dict.insert(make_pair(string,字符串));// 测试 operator[]dict[apple]苹果;// 插入 修改dict[sort]排序(新);// 修改for(autokv:dict){coutkv.first:kv.secondendl;}}voidTestSet(){bit::setints;s.insert(3);s.insert(1);s.insert(2);// *s.begin() 10; // 报错Set 迭代器不可修改符合预期for(autoe:s){coute ;}coutendl;}总结通过引入KeyOfT仿函数我们成功地将红黑树从“专用于某一种类型”变成了“通用的容器底座”。Set告诉红黑树“我存的是int比较的时候直接用它。”Map告诉红黑树“我存的是pair比较的时候请用first。”这就是 C STL 极致复用的智慧希望这篇博客能帮你像哆啦A梦一样从百宝袋里掏出完美的红黑树觉得写得不错的话记得一键三连哦