网站开发售后服务承诺网站空间怎么进

网站开发售后服务承诺,网站空间怎么进,工程建设公司发展规划,焞煌网站怎么做是思成呀#xff1a;个人主页 个人专栏《C知识总结》《MySQL 零基础入门到实战》 前言#xff1a; C STL 中的 map 和 set 是典型的关联式容器#xff0c;二者均基于红黑树实现#xff0c;核心差异仅在于存储的数据类型#xff08;set 存储单个键值、map 存储键值对…是思成呀个人主页个人专栏《C知识总结》《MySQL 零基础入门到实战》前言C STL 中的map和set是典型的关联式容器二者均基于红黑树实现核心差异仅在于存储的数据类型set存储单个键值、map存储键值对。本文聚焦于如何通过泛型编程和仿函数技术基于红黑树底层结构封装出符合 STL 风格的map和set重点体现代码复用和类型适配的设计思想。目录一、先理清核心关联map/set 与红黑树的绑定逻辑1.1 红黑树的泛型设计核心适配层1.2 set 与红黑树的关联极简适配1.3 map 与红黑树的关联键值对适配1.4 核心关联总结二、迭代器的核心实现基于红黑树的中序遍历2.1 迭代器的基础结构封装红黑树节点2.2 迭代器 实现找中序后继节点核心难点场景 1当前节点有右子树场景 2当前节点无右子树示例理解2.3 迭代器 -- 实现找中序前驱节点对称逻辑2.4 红黑树的 begin/end 接口迭代器的边界三、迭代器的使用map/set 遍历的底层逻辑3.1 set 遍历迭代器返回键值3.2 map 遍历迭代器返回键值对四、核心总结4.1 map/set 共用红黑树的核心4.2 迭代器的核心逻辑五、拓展const 迭代器补充结尾一、先理清核心关联map/set 与红黑树的绑定逻辑map 和 set 并非重新实现红黑树而是通过模板参数 仿函数复用同一套红黑树代码仅在 “存储数据类型” 和 “键值提取方式” 上做差异化适配。1.1 红黑树的泛型设计核心适配层红黑树通过三个模板参数实现对 map/set 的通用支持这是关联的基础templateclass K, class T, class KOfTK键类型如 mapint,V 的 intsetstring 的 stringT节点存储的实际数据类型map 存 pairK,Vset 存 KKOfT仿函数用于从 T 中提取键 K解决比较逻辑统一问题// 红黑树模板定义适配 map/set 的核心 templateclass K, class T, class KOfT class RBTree { // 迭代器类型对外暴露供 map/set 复用 typedef __TreeIteratorT iterator; private: RBTreeNodeT* _root nullptr; // 红黑树根节点 };1.2 set 与红黑树的关联极简适配set 仅存储键值无值关联因此存储类型T K节点直接存键仿函数SetKeyOfT直接返回键本身无需提取迭代器直接复用红黑树的iterator解引用返回键值。核心代码templateclass K class set { // 仿函数从 TK 中提取键直接返回自身 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: // 复用红黑树的迭代器typename 声明嵌套类型模板解析必须 typedef typename RBTreeK, K, SetKeyOfT::iterator iterator; // 容器迭代器接口直接调用红黑树的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } private: // set 持有的红黑树对象TK用 SetKeyOfT 提取键 RBTreeK, K, SetKeyOfT _t; };1.3 map 与红黑树的关联键值对适配map 存储键值对pairK,V因此存储类型T pairK,V节点存键值对仿函数MapKeyOfT从pair中提取first键用于比较迭代器复用红黑树的iterator解引用返回pairK,V支持-first/second访问。核心代码templateclass K, class V class map { // 仿函数从 TpairK,V 中提取键pair.first struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: // 复用红黑树的迭代器 typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator; // 容器迭代器接口调用红黑树的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } private: // map 持有的红黑树对象TpairK,V用 MapKeyOfT 提取键 RBTreeK, pairK, V, MapKeyOfT _t; };1.4 核心关联总结维度set 与红黑树的关联map 与红黑树的关联存储类型 TT K直接存键T pairK,V存键值对键提取逻辑仿函数直接返回 T即 K仿函数返回 T.firstpair 的键迭代器复用红黑树 iteratorTK红黑树 iteratorTpairK,V核心依赖红黑树的中序遍历保证键有序红黑树的中序遍历保证键有序二、迭代器的核心实现基于红黑树的中序遍历map/set 的迭代器本质是红黑树节点指针的封装其核心能力是通过重载/--实现 “中序遍历”红黑树中序遍历结果为有序序列这是 map/set 有序性的根源。2.1 迭代器的基础结构封装红黑树节点迭代器类的核心是持有红黑树节点指针并重载基础运算符解引用、箭头、比较为遍历提供基础能力// 红黑树节点结构迭代器的操作对象 templateclass T struct RBTreeNode { RBTreeNodeT* _left; RBTreeNodeT* _right; RBTreeNodeT* _parent; T _data; // 存储的数据set: Kmap: pairK,V Colour _col; RBTreeNode(const T data) : _data(data), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr) {} }; // 迭代器核心类封装节点指针实现遍历逻辑 templateclass T struct __TreeIterator { typedef RBTreeNodeT Node; typedef __TreeIteratorT Self; Node* _node; // 核心指向红黑树的节点 // 构造函数接收节点指针初始化 __TreeIterator(Node* node) : _node(node) {} // 1. 解引用运算符返回节点存储的数据 // set返回 Kmap返回 pairK,V T operator*() { return _node-_data; } // 2. 箭头运算符支持 map 迭代器 it-first/it-second // 编译器优化it- 等价于 (*it). 实际返回 (_node-_data) T* operator-() { return (_node-_data); } // 3. 比较运算符判断迭代器是否指向同一节点end() 是 nullptr bool operator!(const Self s) const { return _node ! s._node; } bool operator(const Self s) const { return _node s._node; } // 4. /-- 运算符核心逻辑下文重点讲解 Self operator(); Self operator--(); };2.2 迭代器 实现找中序后继节点核心难点map/set 迭代器的对应红黑树的中序遍历后继节点保证遍历结果有序分两种场景处理场景 1当前节点有右子树后继节点是 “右子树的最左节点”右子树中最小的节点Self operator() { if (_node-_right) { // 场景1有右子树找右子树最左节点 Node* subLeft _node-_right; while (subLeft-_left) { // 一直向左找直到无左孩子 subLeft subLeft-_left; } _node subLeft; } else { // 场景2无右子树向上找祖先节点 Node* cur _node; Node* parent _node-_parent; // 循环条件当前节点是父节点的右孩子说明还没找到后继 while (parent cur parent-_right) { cur parent; // 向上移动 parent parent-_parent; } // 退出循环parent 是后继或 parentnullptr即 end() _node parent; } return *this; }场景 2当前节点无右子树需沿父节点向上查找直到找到第一个 “当前节点是其左孩子” 的祖先节点该祖先节点即为后继若一直找到根节点仍未满足则到达end()_node nullptr。示例理解红黑树结构5(root) - 3 - 15 - 7 - 9迭代器指向1: 无右子树, 向上找, 3是1的父节点且1是3的左孩子 → 后继是3;迭代器指向3: 有右子树 (空? 假设3右子树为空), 向上找, 5是3的父节点且3是5的左孩子 → 后继是5;迭代器指向5: 有右子树找右子树7的最左节点 → 7的左子树为空因此后继是7;迭代器指向9: 无右子树, 向上找, 7是9的父节点且9是7的右孩子 → 继续向上, 5是7的父节点且7是5的右孩子 → 继续向上, parentnullptr → 后继是end()。2.3 迭代器 -- 实现找中序前驱节点对称逻辑--对应红黑树的中序遍历前驱节点逻辑与对称Self operator--() { if (_node-_left) { // 场景1有左子树找左子树最右节点 Node* subRight _node-_left; while (subRight-_right) { // 一直向右找直到无右孩子 subRight subRight-_right; } _node subRight; } else { // 场景2无左子树向上找祖先节点 Node* cur _node; Node* parent _node-_parent; // 循环条件当前节点是父节点的左孩子未找到前驱 while (parent cur parent-_left) { cur parent; parent parent-_parent; } // 退出循环parent 是前驱或 parentnullptr即 begin() 之前 _node parent; } return *this; }2.4 红黑树的 begin/end 接口迭代器的边界红黑树为 map/set 提供统一的迭代器边界与T类型无关templateclass K, class T, class KOfT class RBTree { public: typedef __TreeIteratorT iterator; // begin()红黑树中序遍历的第一个节点最左节点 iterator begin() { Node* cur _root; while (cur cur-_left) { // 一直向左找直到无左孩子 cur cur-_left; } return iterator(cur); } // end()遍历的终止位置空指针不指向任何有效节点 iterator end() { return iterator(nullptr); } };map/set 直接复用这两个接口// set 的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } // map 的 begin/end iterator begin() { return _t.begin(); } iterator end() { return _t.end(); }三、迭代器的使用map/set 遍历的底层逻辑3.1 set 遍历迭代器返回键值void test_set() { sicheng::setint s; s.Insert(5); s.Insert(3); s.Insert(7); s.Insert(1); // 迭代器遍历底层是红黑树的中序遍历 sicheng::setint::iterator it s.begin(); while (it ! s.end()) { cout *it ; // 输出1 3 5 7有序 it; // 调用 __TreeIterator::operator() } }*it调用operator*()返回红黑树节点的_data即 int 键值it找到下一个中序节点保证遍历有序。3.2 map 遍历迭代器返回键值对void test_map() { sicheng::mapint, string m; m.Insert({1, one}); m.Insert({3, three}); m.Insert({2, two}); // 迭代器遍历 sicheng::mapint, string::iterator it m.begin(); while (it ! m.end()) { // it-first等价于 (*it).first返回 pair 的键 // it-second返回 pair 的值 cout it-first : it-second ; // 输出1:one 2:two 3:three it; } }it-first底层是operator-()返回pairK,V*编译器优化为(*it).first遍历有序性依赖红黑树的中序遍历按键升序排列。四、核心总结4.1 map/set 共用红黑树的核心共性封装红黑树封装 “基于键的有序存储、平衡调整、中序遍历” 等共性逻辑与存储的具体数据类型解耦差异抽象通过模板参数T适配存储类型键 / 键值对通过仿函数KOfT统一键提取规则无冗余复用无需为 map/set 分别实现红黑树仅需适配模板参数极大减少代码冗余。4.2 迭代器的核心逻辑本质封装红黑树节点指针遍历逻辑与存储类型T无关仅通过解引用 / 箭头运算符适配不同返回值/-- 核心找中序后继 / 前驱节点分 “有子树” 和 “无自树” 两种场景依赖红黑树的三叉链结构边界begin()是红黑树最左节点end()是空指针遍历终止差异化set 迭代器解引用返回键map 迭代器解引用返回键值对底层仅因红黑树节点的T类型不同。五、拓展const 迭代器补充实际开发中map/set 还需提供const_iterator只读迭代器核心是修改operator*()和operator-()的返回值为 consttemplateclass T struct __TreeConstIterator { typedef RBTreeNodeT Node; typedef __TreeConstIteratorT Self; Node* _node; __TreeConstIterator(Node* node) : _node(node) {} // const 迭代器解引用返回 const T const T operator*() { return _node-_data; } // const 迭代器箭头返回 const T* const T* operator-() { return (_node-_data); } // /-- 逻辑与非 const 版本完全一致 Self operator() { /* 同前 */ } Self operator--() { /* 同前 */ } };map/set 中新增const_iterator类型即可复用// set 的 const 迭代器 typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator; const_iterator cbegin() const { return _t.cbegin(); } const_iterator cend() const { return _t.cend(); } // map 的 const 迭代器同理结尾 我是思成若这篇内容帮你理清了 map/set 与红黑树的关联逻辑 【关注】跟我一起拆解 C 底层原理从容器到数据结构吃透每一个核心知识点❤️ 【点赞】让技术干货被更多人看见让抽象的底层逻辑变得易懂⭐ 【收藏】把迭代器实现、泛型复用的思路存好面试 / 实战时随时查阅 【评论】分享你学习红黑树时踩过的坑或想深挖的技术点一起交流进步️ 【投票】告诉我你最想拆解的下一个知识点比如红黑树删除哈希表技术学习没有捷径但找对思路能少走弯路愿我们都能把复杂的底层逻辑拆解成可落地的知识碎片一步步构建自己的技术体系结语红黑树以 “颜色规则 旋转操作” 实现自平衡既保留了二叉搜索树中序遍历的有序性又解决了单支树退化的性能问题。而 map/set 基于泛型和仿函数的复用设计更是 C 抽象思维的经典体现 —— 将共性逻辑封装差异点参数化让一套底层结构适配多种上层场景。理解这一设计思路不仅能吃透 map/set更能掌握泛型编程的核心精髓。