改造红黑树--＞ 模拟封装set和map

////// 欢迎来到 aramae 的博客愿 Bug 远离好运常伴 //////博主的Gitee地址阿拉美 (aramae) - Gitee.com时代不会辜负长期主义者愿每一个努力的人都能达到理想的彼岸。​一、整体架构在红黑树RBTree之上封装set和map通过KeyOfT策略注入让同一棵红黑树同时支持两种容器。二、核心设计思想策略注入底层红黑树RBTree有三个模板参数templateclass K, class T, class KeyOfT struct RBTree;参数含义K键的类型T存储的数据类型KeyOfT从 T 中提取 K 的策略不同容器注入不同的策略容器T的类型KeyOfT行为setKK直接返回 key 本身mapK,Vpairconst K, V返回kv.first三、set 封装详解3.1 完整代码templateclass K class set { // ① 策略类告诉红黑树 T 就是 K struct SetKeyOfT { const K operator()(const K key) { return key; } }; public: // ② 迭代器类型全部是 const_iterator typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator; typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator; // ③ 迭代器接口全部 const 版本 const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } // ④ insert返回值需要类型转换 pairiterator, bool insert(const K key) { pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key); return pairiterator, bool(ret.first, ret.second); } private: // ⑤ 底层红黑树实例 RBTreeK, K, SetKeyOfT _t; };3.2 关键设计点① 底层红黑树实例化RBTreeK, K, SetKeyOfT _t; // ↑ ↑ ↑ // K K └── 策略类直接返回 key // | └──────── T K存的就是键本身 // └─────────── K 键的类型对于setintK intT intKeyOfToperator()(int key) { return key; }② 迭代器全部是 const_iteratortypedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator; typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;为什么要这样设计因为 set 的元素就是 KeyKey 绝对不能改假设允许修改 Keysetint s {1, 2, 3}; auto it s.begin(); *it 10; // 如果允许红黑树的有序结构就被破坏了红黑树依赖 Key 的大小关系来维持有序结构。修改 Key 会破坏排序导致树的完整性被破坏。所以即使你用的是普通迭代器也不能修改元素。干脆把两者定义为同一个类型const_iterator。③ insert 返回值的类型转换重点pairiterator, bool insert(const K key) { // 底层返回pairRBTree::iterator, bool pairtypename RBTreeK, K, SetKeyOfT::iterator, bool ret _t.Insert(key); // 上层需要pairset::iterator, bool其中 iterator 是 const_iterator return pairiterator, bool(ret.first, ret.second); }为什么需要手动转换底层返回pairiterator, bool iterator 是普通迭代器 上层需要pairconst_iterator, bool 虽然 iterator 可以隐式转成 const_iterator 但 pairiterator, bool 不会自动变成 pairconst_iterator, bool。 所以需要手动构造。为什么RBTree::iterator能转成set::iterator即 const_iterator因为在__TreeIterator中定义了转换构造typedef __TreeIteratorT, T*, T Iterator; // 普通迭代器 → const 迭代器的隐式转换构造 __TreeIterator(const Iterator it) : _node(it._node) {}四、map 封装详解4.1 完整代码templateclass K, class V class map { // ① 策略类从 pair 中提取 Key struct MapKeyOfT { const K operator()(const pairK, V kv) { return kv.first; } }; public: // ② 迭代器类型普通 const typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator; // ③ 迭代器接口非 const const 版本 iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } // ④ insert直接透传 pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); } // ⑤ operator[]核心功能 V operator[](const K key) { pairiterator, bool ret insert(make_pair(key, V())); return ret.first-second; } private: // ⑥ 底层红黑树实例 RBTreeK, pairconst K, V, MapKeyOfT _t; };4.2 关键设计点① 底层红黑树实例化RBTreeK, pairconst K, V, MapKeyOfT _t; // ↑ ↑ ↑ // K pair └── 策略类取 kv.first // | └──────────────── T pairconst K, V // └─────────────────── K 键的类型对于mapstring, intK stringT pairconst string, intKeyOfToperator()(pairconst string, int kv) { return kv.first; }pairconst K, V中的 const 是核心保护机制mapstring, int mp; auto it mp.begin(); it-first new_key; // ❌ 编译错误first 是 const 的 it-second 100; // ✅ 可以修改 value② 迭代器类型typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator; typedef typename RBTreeK, pairconst K, V, MapKeyOfT::const_iterator const_iterator;与 set 的对比setmap普通迭代器 const_iterator✅ 可修改second能否修改 Key❌❌first 是 const能否修改 Value❌无 Value✅③ insert直接透传pairiterator, bool insert(const pairK, V kv) { return _t.Insert(kv); }为什么 set 需要转换而 map 不需要底层返回上层需要是否一致setpairiterator, boolpairconst_iterator, bool❌ 需要转换mappairiterator, boolpairiterator, bool✅ 直接透传④ operator[]核心功能V operator[](const K key) { pairiterator, bool ret insert(make_pair(key, V())); return ret.first-second; }执行流程mapstring, int mp; mp[apple] 5;Step 1: make_pair(apple, int()) → 构造 {apple, 0} Step 2: insert({apple, 0}) → 插入新元素返回 {iterator, true} Step 3: ret.first-second → 返回 0 的引用 Step 4: 5 → 赋值为 5如果 Key 已存在mp[apple] 10;Step 1: make_pair(apple, int()) → 构造 {apple, 0} Step 2: insert({apple, 0}) → Key 已存在返回 {iterator, false} Step 3: ret.first-second → 返回已有元素 value 的引用值为 5 Step 4: 10 → 赋值为 10五、set 和 map 的对比总结对比项setKmapK, V存储类型TKpairconst K, VKeyOfT策略直接返回key返回kv.first普通迭代器const_iterator可修改second能否修改 Key❌❌能否修改 Value❌无 Value✅operator[]❌✅insert返回pairconst_iterator, boolpairiterator, boolinsert实现需要类型转换直接透传结语感谢相遇/// 高山仰止景行行止。虽不能至心向往之 ///