map与set的模拟，咕咕咕!

1.map和set的模拟实现#pragma once #include iostream #include utility // 用于pair #include cstddef // 用于nullptr_t using namespace std; // 红黑树节点颜色 enum Color { RED, BLACK }; // 红黑树节点模板 template class T struct RBTreeNode { RBTreeNodeT* _left; // 左孩子 RBTreeNodeT* _right; // 右孩子 RBTreeNodeT* _parent; // 父节点 T _data; // 节点存储的数据 Color _color; // 节点颜色 // 构造函数 RBTreeNode(const T data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _color(RED) // 新节点默认红色减少红黑树调整次数 {} }; // 红黑树迭代器模板 template class T, class Ref, class Ptr struct RBTreeIterator { typedef RBTreeNodeT Node; typedef RBTreeIteratorT, Ref, Ptr Self; Node* _node; // 指向红黑树节点的指针 // 构造函数 RBTreeIterator(Node* node) : _node(node) {} // 解引用返回节点数据的引用 Ref operator*() { return _node-_data; } // 箭头运算符返回节点数据的指针 Ptr operator-() { return _node-_data; } // 前置找中序遍历的下一个节点 Self operator() { if (_node-_right) { // 有右子树找右子树的最左节点 Node* subLeft _node-_right; while (subLeft-_left) { subLeft subLeft-_left; } _node subLeft; } else { // 无右子树向上找第一个是父节点左孩子的节点 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_right) { cur parent; parent parent-_parent; } _node parent; // 循环结束时parent就是目标节点或nullptr对应end() } return *this; } // 前置--找中序遍历的前一个节点可选set/map基础功能可暂不实现 Self operator--() { if (_node-_left) { // 有左子树找左子树的最右节点 Node* subRight _node-_left; while (subRight-_right) { subRight subRight-_right; } _node subRight; } else { // 无左子树向上找第一个是父节点右孩子的节点 Node* cur _node; Node* parent cur-_parent; while (parent cur parent-_left) { cur parent; parent parent-_parent; } _node parent; } return *this; } // 相等运算符 bool operator(const Self other) const { return _node other._node; } // 不等运算符 bool operator!(const Self other) const { return _node ! other._node; } }; // 红黑树核心模板 // K: 键类型 T: 存储的实际数据类型 KeyOfT: 从T中提取K的仿函数 template class K, class T, class KeyOfT class RBTree { public: typedef RBTreeNodeT Node; typedef RBTreeIteratorT, T, T* Iterator; typedef RBTreeIteratorT, const T, const T* ConstIterator; // 构造函数初始化空树哨兵节点优化简化end()和边界处理 RBTree() { _nil new Node(T()); // 哨兵节点颜色黑左右父均指向自己 _nil-_color BLACK; _nil-_left _nil; _nil-_right _nil; _nil-_parent _nil; _root _nil; // 根节点初始指向哨兵 } // 插入节点核心 pairIterator, bool Insert(const T data) { KeyOfT kot; // 1. 查找插入位置红黑树是二叉搜索树先按BST规则找位置 Node* parent _nil; Node* cur _root; while (cur ! _nil) { parent cur; if (kot(cur-_data) kot(data)) { // 插入值更大走右子树 cur cur-_right; } else if (kot(cur-_data) kot(data)) { // 插入值更小走左子树 cur cur-_left; } else { // 键已存在插入失败set/map不允许重复键 return { Iterator(cur), false }; } } // 2. 创建新节点并挂载 Node* newNode new Node(data); newNode-_parent parent; newNode-_left _nil; newNode-_right _nil; if (parent _nil) { // 空树新节点是根 _root newNode; } else if (kot(parent-_data) kot(data)) { // 挂载到父节点右 parent-_right newNode; } else { // 挂载到父节点左 parent-_left newNode; } // 3. 调整红黑树修复红黑树性质 AdjustAfterInsert(newNode); // 4. 确保根节点是黑色 _root-_color BLACK; return { Iterator(newNode), true }; } // 查找节点 Iterator Find(const K key) { KeyOfT kot; Node* cur _root; while (cur ! _nil) { if (kot(cur-_data) key) { cur cur-_right; } else if (kot(cur-_data) key) { cur cur-_left; } else { return Iterator(cur); // 找到返回迭代器 } } return End(); // 没找到返回end() } // 迭代器begin中序遍历第一个节点即最左节点 Iterator Begin() { Node* cur _root; while (cur-_left ! _nil) { // 找最左节点 cur cur-_left; } return Iterator(cur); } // 迭代器end哨兵节点中序遍历最后一个节点的下一个位置 Iterator End() { return Iterator(_nil); } // const版本迭代器适配const对象 ConstIterator Begin() const { Node* cur _root; while (cur-_left ! _nil) { cur cur-_left; } return ConstIterator(cur); } ConstIterator End() const { return ConstIterator(_nil); } private: Node* _root; // 红黑树根节点 Node* _nil; // 哨兵节点简化边界处理 // 插入后调整红黑树核心逻辑 void AdjustAfterInsert(Node* newNode) { KeyOfT kot; Node* cur newNode; Node* parent cur-_parent; // 父节点是红色才需要调整父黑则无需调整 while (parent-_color RED) { Node* grandParent parent-_parent; // 祖父节点必存在因为根是黑父红则祖父非空 if (parent grandParent-_left) { // 父是祖父的左孩子 Node* uncle grandParent-_right; // 叔叔节点祖父的右孩子 // 情况1叔叔是红色 → 染色即可父、叔变黑祖父变红继续向上检查 if (uncle-_color RED) { parent-_color BLACK; uncle-_color BLACK; grandParent-_color RED; // 继续向上调整 cur grandParent; parent cur-_parent; } else { // 叔叔是黑色或nilnil是黑→ 需要旋转 // 情况2cur是parent的右孩子 → 先左旋parent转为情况3 if (cur parent-_right) { RotateLeft(parent); swap(cur, parent); // 旋转后cur和parent位置互换统一处理情况3 } // 情况3cur是parent的左孩子 → 右旋祖父再染色 RotateRight(grandParent); parent-_color BLACK; grandParent-_color RED; break; // 调整完成退出循环 } } else { // 父是祖父的右孩子镜像逻辑 Node* uncle grandParent-_left; if (uncle-_color RED) { // 情况1叔叔红 parent-_color BLACK; uncle-_color BLACK; grandParent-_color RED; cur grandParent; parent cur-_parent; } else { // 叔叔黑 if (cur parent-_left) { // 情况2cur是parent左孩子 → 右旋parent RotateRight(parent); swap(cur, parent); } // 情况3cur是parent右孩子 → 左旋祖父染色 RotateLeft(grandParent); parent-_color BLACK; grandParent-_color RED; break; } } } } // 左旋红黑树旋转操作 void RotateLeft(Node* parent) { Node* subRight parent-_right; Node* subRightLeft subRight-_left; // 1. 处理subRight的左孩子 parent-_right subRightLeft; if (subRightLeft ! _nil) { subRightLeft-_parent parent; } // 2. 处理subRight与祖父的关系 Node* grandParent parent-_parent; subRight-_parent grandParent; if (grandParent _nil) { // parent是根 _root subRight; } else if (parent grandParent-_left) { // parent是祖父左孩子 grandParent-_left subRight; } else { // parent是祖父右孩子 grandParent-_right subRight; } // 3. 处理parent与subRight的关系 subRight-_left parent; parent-_parent subRight; } // 右旋红黑树旋转操作 void RotateRight(Node* parent) { Node* subLeft parent-_left; Node* subLeftRight subLeft-_right; // 1. 处理subLeft的右孩子 parent-_left subLeftRight; if (subLeftRight ! _nil) { subLeftRight-_parent parent; } // 2. 处理subLeft与祖父的关系 Node* grandParent parent-_parent; subLeft-_parent grandParent; if (grandParent _nil) { // parent是根 _root subLeft; } else if (parent grandParent-_right) { // parent是祖父右孩子 grandParent-_right subLeft; } else { // parent是祖父左孩子 grandParent-_left subLeft; } // 3. 处理parent与subLeft的关系 subLeft-_right parent; parent-_parent subLeft; } }; // Set 实现 namespace gugu { template class K class set { // 从K中提取K的仿函数set的存储数据就是K本身 struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator; typedef typename RBTreeK, 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迭代器, 是否插入成功 pairiterator, bool insert(const K key) { return _t.Insert(key); } // 查找 iterator find(const K key) { return _t.Find(key); } private: RBTreeK, const K, SetKeyOfT _t; }; // Map 实现 template class K, class V class map { // 从pairK,V中提取K的仿函数map的存储数据是pair struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator; typedef typename RBTreeK, pairconst 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(); } // 插入 pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } // 查找 iterator find(const K key) { return _t.Find(key); } // []运算符插入/访问元素 V operator[](const K key) { auto [it, flag] _t.Insert({ key, V() }); // C17结构化绑定 return it-second; } private: RBTreeK, pairconst K, V, MapKeyOfT _t; }; }2.使用改进的红黑树模拟实现map#pragma once #include RBtree.h // 引入你已实现的红黑树头文件 #include utility // 用于 pair #include cstddef // 用于 size_t namespace gugu { templateclass K, class V class map { // 存储的数值类型键值对注意后续插入时需转为 const K typedef pairK, V ValueType; // 从 ValueType 中提取 Key 的仿函数供红黑树比较使用 struct KeyOfValue { const K operator()(const ValueType data) const { return data.first; } }; // 红黑树类型定义修正语法错误typedef 在前typename 在后 typedef RBTreeValueType, KeyOfValue RBTreeType; typedef typename RBTreeType::iterator iterator; // 迭代器类型 public: // 构造函数默认初始化红黑树 map() : t() {} // 迭代器接口 // begin指向红黑树最左节点最小键 iterator begin() { return t.begin(); } // end指向红黑树尾后迭代器空节点 iterator end() { return t.end(); } // 容量接口 // 判断是否为空 bool empty() const { return t.empty(); } // 获取元素个数 size_t size() const { return t.size(); } // 访问接口 // 重载[]核心功能插/查/改一体 V operator[](const K key) { // 构造待插入的键值对值为默认构造 ValueType kv(key, V()); // 插入红黑树返回 迭代器 是否插入成功 pairiterator, bool ret t.insert(kv); // 返回值的引用无论是否插入成功都指向对应key的值 return ret.first-second; } // 修改接口 // 插入键值对 pairiterator, bool insert(const ValueType data) { // 注意若红黑树要求键不可修改需将 K 转为 const K // 适配ValueType 转为 pairconst K, V如果你的红黑树存储const键 // ValueType insert_data make_pair(const_castconst K(data.first), data.second); return t.insert(data); } // 清空所有元素 void clear() { t.clear(); } // 查找指定键 iterator find(const K key) { // 构造临时键值对仅用于提取key红黑树内部通过KeyOfValue取key比较 ValueType tmp(key, V()); return t.find(tmp); } private: RBTreeType t; // 红黑树成员对象 }; }3.使用改进的红黑树模拟实现set#pragma once #include RBTree.h // 引入红黑树头文件 #include utility // 用于 pair #include cstddef // 用于 size_t // 自定义命名空间替换为自己的唯一名称如 my_set_container / bit_123 等 namespace gugu { templateclass K class set { // set 的存储类型直接是键 K无值 typedef K ValueType; // 从 ValueType即 K中提取键的仿函数 struct KeyOfValue { const K operator()(const ValueType data) const { // set 的存储数据就是键本身直接返回即可 return data; } }; // 修正语法错误typedef 在前typename 用于限定依赖类型 typedef RBTreeValueType, KeyOfValue RBTreeType; typedef typename RBTreeType::iterator iterator; public: // 构造函数默认初始化红黑树 set() : t() {} // 迭代器接口 // begin指向红黑树最左节点最小键 iterator begin() { return t.begin(); } // end指向红黑树尾后迭代器空节点对应中序遍历最后一个元素的下一个位置 iterator end() { return t.end(); } // 容量接口 // 判断 set 是否为空委托给红黑树的 empty 接口 bool empty() const { return t.empty(); } // 获取 set 中元素个数委托给红黑树的 size 接口 size_t size() const { return t.size(); } // 修改接口 // 插入元素返回 pair迭代器, bool迭代器指向插入/已存在的元素bool 表示是否插入成功 pairiterator, bool insert(const ValueType data) { // 直接委托给红黑树的 insert红黑树会保证键的唯一性 return t.insert(data); } // 清空 set 中所有元素 void clear() { t.clear(); } // 查找指定键找到返回对应迭代器未找到返回 end() iterator find(const K key) { // 红黑树的 find 接口需接收 ValueType即 K直接传入 key 即可 return t.find(key); } private: // 红黑树成员对象set 的所有逻辑都基于红黑树实现 RBTreeType t; }; }