企业官网建设流程全解析

////// 欢迎来到 aramae 的博客，愿 Bug 远离，好运常伴！ //////

博主的Gitee地址：阿拉美 (aramae) - Gitee.com

​

一、整体架构

在红黑树（RBTree）之上封装set和map，通过KeyOfT策略注入，让同一棵红黑树同时支持两种容器。

二、核心设计思想：策略注入

底层红黑树RBTree有三个模板参数：

template<class K, class T, class KeyOfT> struct RBTree;

不同容器注入不同的策略：

三、set 封装详解

3.1 完整代码

template<class K> class set { // ① 策略类：告诉红黑树 "T 就是 K" struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: // ② 迭代器类型：全部是 const_iterator！ typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator; // ③ 迭代器接口（全部 const 版本） const_iterator begin() const { return _t.begin(); } const_iterator end() const { return _t.end(); } // ④ insert：返回值需要类型转换 pair<iterator, bool> insert(const K& key) { pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); return pair<iterator, bool>(ret.first, ret.second); } private: // ⑤ 底层红黑树实例 RBTree<K, K, SetKeyOfT> _t; };

3.2 关键设计点

① 底层红黑树实例化

RBTree<K, K, SetKeyOfT> _t; // ↑ ↑ ↑ // K K └── 策略类：直接返回 key // | └──────── T = K（存的就是键本身） // └─────────── K = 键的类型

对于set<int>：

• K = int

• T = int

• KeyOfT：operator()(int key) { return key; }

② 迭代器全部是 const_iterator

typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

为什么要这样设计？

因为 set 的元素就是 Key，Key 绝对不能改！

假设允许修改 Key：

set<int> s = {1, 2, 3}; auto it = s.begin(); *it = 10; // 如果允许，红黑树的有序结构就被破坏了！

红黑树依赖 Key 的大小关系来维持有序结构。修改 Key 会破坏排序，导致树的完整性被破坏。

所以即使你用的是"普通迭代器"，也不能修改元素。干脆把两者定义为同一个类型（const_iterator）。

③ insert 返回值的类型转换（重点）

pair<iterator, bool> insert(const K& key) { // 底层返回：pair<RBTree::iterator, bool> pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); // 上层需要：pair<set::iterator, bool>（其中 iterator 是 const_iterator） return pair<iterator, bool>(ret.first, ret.second); }

为什么需要手动转换？

底层返回：pair<iterator, bool> （iterator 是普通迭代器） 上层需要：pair<const_iterator, bool> 虽然 iterator 可以隐式转成 const_iterator， 但 pair<iterator, bool> 不会自动变成 pair<const_iterator, bool>。 所以需要手动构造。

为什么RBTree::iterator能转成set::iterator（即 const_iterator）？

因为在__TreeIterator中定义了转换构造：

typedef __TreeIterator<T, T*, T&> Iterator; // 普通迭代器 → const 迭代器的隐式转换构造 __TreeIterator(const Iterator& it) : _node(it._node) {}

四、map 封装详解

4.1 完整代码

template<class K, class V> class map { // ① 策略类：从 pair 中提取 Key struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: // ② 迭代器类型（普通 + const） typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; typedef typename RBTree<K, pair<const 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：直接透传 pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); } // ⑤ operator[]（核心功能） 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; };

4.2 关键设计点

① 底层红黑树实例化

RBTree<K, pair<const K, V>, MapKeyOfT> _t; // ↑ ↑ ↑ // K pair └── 策略类：取 kv.first // | └──────────────── T = pair<const K, V> // └─────────────────── K = 键的类型

对于map<string, int>：

• K = string

• T = pair<const string, int>

• KeyOfT：operator()(pair<const string, int>& kv) { return kv.first; }

pair<const K, V>中的 const 是核心保护机制！

map<string, int> mp; auto it = mp.begin(); it->first = "new_key"; // ❌ 编译错误！first 是 const 的 it->second = 100; // ✅ 可以修改 value

② 迭代器类型

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

与 set 的对比：

③ insert：直接透传

pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); }

为什么 set 需要转换而 map 不需要？

④ operator[]（核心功能）

V& operator[](const K& key) { pair<iterator, bool> ret = insert(make_pair(key, V())); return ret.first->second; }

执行流程：

map<string, 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 的对比总结

结语：感谢相遇

/// 高山仰止，景行行止。虽不能至，心向往之 ///