【C++】—— 从零开始封装 Map 与 Set：实现与优化

人生的态度是，抱最大的希望，尽最大的努力，做最坏的打算。

—— 柏拉图 《理想国》

目录

1、理论基石——深度剖析 BSTree、AVLTree 与 RBTree 的概念区别

2、迭代器机制——RBTree 迭代器的架构与工程实现

3、高级容器设计——Map 与 Set 的模块化封装

3.1 泛型支持增强——RBTree 模板参数设计优化

3.2 Set 容器构建——面向集合操作的优化设计

 3.3 Map 容器构建——高效键值存储的封装实现

Thanks谢谢阅读！！！

1、理论基石——深度剖析 BSTree、AVLTree 与 RBTree 的概念区别

为了实现 Map 和 Set 的封装，我们首先进行了充分的知识储备，确保理解底层数据结构的原理与实现。

二叉搜索树及其变种

为了深入理解 Map 和 Set 的底层原理，我们从二叉搜索树 (BST)入手。二叉搜索树在二叉树的基础上加入了以下重要特性：

• 若左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若右子树不为空，则右子树上所有节点的值都大于根节点的值；
• 左右子树也必须分别满足二叉搜索树的性质。

这种结构在大多数情况下可以有效支持快速查找，但在某些极端情况下（例如单侧树形结构），搜索效率会退化为 O(n)。因此，我们引入了更为高效的平衡二叉搜索树，其中 AVL树 和 红黑树 (RBTree) 是两种经典的变种，它们通过不同的方式提高了性能与稳定性。

平衡二叉搜索树：AVL 树与红黑树

AVL 树 和 红黑树 都是在保持二叉搜索树基本性质的基础上，通过旋转与重新平衡操作，确保树的高度维持在一个相对平衡的状态，从而保证了操作的时间复杂度始终为 O(log n)。它们的出现大大提升了二叉搜索树在实际应用中的性能与可靠性。

• AVL 树 增加了以下特性：

  • 它的左右子树必须都是 AVL 树；
  • 左右子树高度差（平衡因子）不能超过 1（即平衡因子为 -1、0 或 1）；
  • 如果平衡因子超出范围，树将进行旋转操作，包括右单旋、左单旋、左右双旋、右左双旋等。

• 红黑树 则在其基础上引入了以下特点：

  • 每个节点必须是红色或黑色；
  • 根节点必须是黑色；
  • 红色节点的子节点必须是黑色；
  • 从任何节点到其所有后代叶子节点的路径上，必须有相同数量的黑色节点；
  • 叶子节点（空节点）必须是黑色。

虽然红黑树在旋转操作的频率上低于 AVL 树，但它通过较少的旋转保持树的接近平衡状态，能够确保良好的性能。

Map 与 Set 的底层实现

由于 Map 和 Set 大多用于高效检索，我们选择使用 红黑树 来实现它们的底层结构。红黑树能够在保证相对平衡的同时，确保操作时间复杂度为 O(log n)，非常适合用于处理大量的键值对数据。

封装前的迭代器实现

在封装 Map 和 Set 之前，我们需要先实现一个关键的组件：迭代器。迭代器是遍历容器内元素的核心工具，它提供了访问和操作元素的方式，并为我们后续的封装工作奠定了基础。

2、迭代器机制——RBTree 迭代器的架构与工程实现

迭代器是容器中非常重要的组成部分，它使得我们可以方便地遍历数据。在 红黑树 的实现中，增加迭代器支持不仅仅是为了提供遍历的便利，更是为了使得红黑树能够符合现代 C++ 泛型编程的要求，遵循 STL 中对迭代器的严格规范。

首先，考虑到迭代器的设计，我们需要解决几个关键问题：

迭代器框架的搭建

在确定了迭代器的需求后，接下来我们可以着手搭建迭代器框架。该框架需要支持以下功能：

• 构造与销毁：支持红黑树迭代器的构造与析构。
• 指针访问：提供对当前节点的访问能力，通常通过解引用操作符 * 和成员访问操作符 -> 来实现。
• 前进与后退：通过 ++ 和 — 操作符来支持迭代器的前进与后退，确保其符合树的中序遍历规则。
• 比较操作：支持 == 和 != 比较操作，判断两个迭代器是否指向同一节点。

// 迭代器
// T 表示数据类型 Ref为引用 Ptr为指针
template<class T,class Ptr,class Ref>
struct RBTreeIterator
{
//为了方便调用，我们重命名一下
typedef RBTreeNode<T> Node;
typedef _RBTreeIterator<T, Ref, Ptr> Self;

//内部是节点指针
Node* _node;
_RBTreeIterator(Node* node)
:_node(node)
{}

//两种指向方式
Ref operator*()
{
return _node->_data;
}
Ptr operator&()
{
return &_node->_data;
}

bool operator!= (const Self& s)
{
return _node != s._node;
}
bool operator== (const Self& s)
{
return _node == s._node;
}

};

迭代器的访问 ++ 和 —

++ 中序遍历的顺序是先遍历左边再遍历当前节点最后是右子树。

Self& operator++()
{
//首先，能访问到当前节点说明左子树的都已经访问过啦 左 根 右 中序
//所以就要分类讨论
//如果右边有子树,就要去寻找右子树的最左节点
if (_node->_right)
{
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
//如果右边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行++
//找到祖先节点(注意祖先节点右边可能还没遍历)
//此时也要进行分类讨论
else
{
Node* cur = _node;
Node* parent = _node->_parent;
// 如果 _node == parent->_right
//说明parent的节点已经访问过了 需要向上遍历 找到没有访问的 可能一直向上 导致 parent 空 所以判断一下
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

适度结合图像分析，还是要遵循左根右的核心思维决定下一个节点的位置

— 倒中序遍历 右 根 左 逻辑取反即可 

Self& operator–()
{
if (_node == nullptr) // end()
{
// –end()，特殊处理，走到中序最后⼀个结点，整棵树的最右结点
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
//首先，能访问到当前节点说明右子树的都已经访问过啦 右 根 左 倒中序
//所以就要分类讨论
//如果左边有子树,就要去寻找左子树的最右节点
else if (_node->_left)
{
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
//如果左边没有子树了，说明该节点以下的子树都已遍历完，那么就要向上进行–
//找到祖先节点(注意祖先节左边可能还没遍历)
//此时也要进行分类讨论
else
{
Node* cur = _node;
Node* parent = _node->_parent;
// 如果 _node == parent->_left
//说明parent的节点已经访问过了 需要向上遍历 找到没有访问的 可能一直向上 导致 parent 空 所以判断一下
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

这里特殊情况是因为 我们设置的容器迭代器 end（） 为空指针 （STTL库是加了个哨兵位节点）不可以再访问了所以特殊处理一下

3、高级容器设计——Map 与 Set 的模块化封装

3.1 泛型支持增强——RBTree 模板参数设计优化

我们先来看之前写的红黑树的节点代码：

// 节点结构体
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;

pair<K, V> _kv;
color _col;
RBTreeNode(pair<K, V> kv)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_kv(kv)
{}

};

在实现 Map 和 Set 的封装时，我们发现，当前的设计使得每个红黑树的节点都存储了一个固定的数据类型 pair<K, V>。这种做法虽然对 Map 的实现来说非常直接，但当我们尝试为 Set 封装时，问题就显现出来了：Set 中的节点只需要存储键 K，而不是键值对 pair<K, V>。这意味着如果我们照这种方式实现 Set，我们就不得不重复编写一份类似的红黑树代码来处理不同的数据结构。这样不仅增加了代码的冗余，也让代码的维护变得不够优雅。

为了更好地封装 Map 和 Set，我们可以借鉴 STL 源码中的设计理念。STL 中通过 模板编程 和 类型特化 的方式，使得同一个数据结构能够支持不同类型的容器，而不需要重复编写代码。这种设计不仅提高了代码的复用性，还使得容器能够灵活地处理不同的数据类型。

STL 的设计思路

在 STL 中，Map 和 Set 都是通过底层红黑树（或其他平衡树）来实现的，但它们有不同的结构和需求：

• Map 是一个键值对容器，节点存储 pair<K, V>；
• Set 是一个只存储键的容器，节点只需要存储 K。

然而，尽管它们的数据存储结构不同，STL 并没有为 Map 和 Set 分别写两份完全不同的红黑树代码。相反，STL 通过巧妙的模板设计，使得同一个红黑树实现能够根据需求灵活存储键值对或者仅存储键。

可以看出，STL 源码中的设计巧妙地利用了模板编程，成功地实现了 Map 和 Set 的统一封装，避免了代码冗余。

STL设计思路解析

首先，最底层的红黑树节点结构体只使用了一个模板参数 Value，该参数决定了节点中存储的数据类型。上层的红黑树根据提供的 Value 类型来选择具体的数据存储结构。这样，红黑树的底层实现不需要区分 Map 和 Set，而是通过模板参数 Value 来灵活适应不同需求。

红黑树的关键模板参数

在红黑树的实现中，存在三个关键的模板参数：

统一封装：如何实现 Map 与 Set 的共享底层红黑树

通过巧妙的模板设计，红黑树底层实现可以根据不同的需求使用不同的数据结构来存储：

• 对于 Map，底层红黑树将 Key 和 pair<K, V> 作为模板参数传入。Key 用于查找操作，而 Value 则是 pair<K, V>，即包含键和值的结构。 
• map:就传给红黑树<K , pair<K,V> …>
• 对于 Set，红黑树只需要 Key 作为模板参数，因为 Set 只关心存储键 K，无需存储值，但是这里红黑树的前两个模板参数都需要传K。
• set: 就传给红黑树<K , K …>

通过这种方式，尽管 Map 和 Set 的模板参数不同（分别是 pair<K, V> 和 K），它们却可以共用同一份底层红黑树代码。这种设计不仅避免了代码重复，也提高了代码的可维护性和灵活性。

//——————————————-
//—————- 红黑树实现 —————–
//——————————————-
//——– 适配map 与 set 的进阶版本 ———–
//——————————————-

enum color
{
Black,
Red
};
// 节点结构体
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;

T _data;
color _col;
RBTreeNode(T data)
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_data(data),
_col(Red)
{}

};

//适配map与set 的版本
// 迭代器
template<class T , class Ref , class Ptr>
struct _RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef _RBTreeIterator<T, Ref, Ptr> Self;

Node* _node;
_RBTreeIterator(Node* node)
:_node(node)
{}

Ref operator*()
{
return _node->_data;
}
Ptr operator&()
{
return &_node->_data;
}
bool operator!= (const Self& s)
{
return _node != s._node;
}
//迭代器的++ 中序遍历的顺序
Self& operator++()
{
}
Self& operator–()
{
}
};

//K 为键值 T 为储存的结构 map则为pair set则为key KeyOfValue 是取出Key的方式
template<class K, class T , class KeyOfValue>
class RBTree
{
public:
typedef _RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeNode<T> Node;

Iterator begin()
{

}
Iterator end()
{

}
//右单旋
void RotateR(Node* parent)
{
}
//左右双旋
void RotateLR(Node* parent)
{
}
//右左双旋
void RotateRL(Node* parent)
{
}

//插入函数
pair<Iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
//return pair<Iterator, bool>(Iterator(_root,_root),true);
return { Iterator(_root,_root), true };
}
Node* cur = _root;
Node* parent = nullptr;
//查找逻辑 cur 到对应的位置去
// KeyOfT 取第一个数据比较
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return { Iterator(cur,_root), false};
}
}
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED; //新插入非空节点 为红色
// 连接 prev 与 cur
if (kot(parent->_data) > kot(data))
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;

// 父亲是红色 出现了连续红节点 需要处理 可能多次处理 while向上更新
while (parent && parent->_col == RED) //可能为空
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
// g
// p u
Node* uncle = grandfather->_right;
// 叔叔不为空 且红色
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//往上更新
cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_left == cur) //右单旋+变色
{// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //双旋处理
{
// g
// p u
// c
RotateLR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔不为空 且红色
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑 爷爷变红 变色 解决连续红色节点并且保证 路径黑节点数量不变
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;

//往上更新
cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_right == cur) //左单旋+变色
{// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //双旋处理
{
// g
// u p
//c
RotateRL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return { Iterator(newnode,_root), true};
}

Iterator find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return Iterator(cur,_root);
}
}
return End();
}

private:
void _IsBalance(Node* root , int num)
{
}
bool Check(Node* root, int blackNum, const int refNum)
{
}

void _InOrder(Node* cur)
{
}
RBTreeNode<T>* _root = nullptr;
};

注意比较方式统一改成类似kot(_data) < kot(node.data)的样子哦！！！因为map与set的取出key的方式不同！！！

3.2 Set 容器构建——面向集合操作的优化设计

Set 封装的实现

对于 Set 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

namespace xc
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K&key)
{
return key;
}
};

public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, 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<iterator,bool> insert(const K&key)
{
return _t.insert(key);
}

iterator find(const K& key)
{
return _t.find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
}

 3.3 Map 容器构建——高效键值存储的封装实现

在完成了红黑树的改进后，接下来的步骤就相对简单了。我们只需要在上层实现 Map 和 Set 的具体封装，调用底层红黑树的接口并传入相应的模板参数即可。

Map 封装的实现

对于 Map 封装，关键是要根据红黑树的底层实现要求提供相应的模板参数和仿函数。

namespace xc
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};

public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const 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();
}

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

iterator find(const K& key)
{
return _t.find(key);
}

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

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

这样map 封装好了，测试一下！！！

void test_map()
{
xc::map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];

xc::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// 不能修改first，可以修改second
//it->first += 'x';
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;

for (auto &kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}

int main()
{
test_map();
return 0;
}

可以看到我们实现了 map 的关键重载函数 [ ] 

map和set从零建立起来不仅需要二叉搜索树的知识还需要AVL树和红黑树的使用！！！甚至还需要对于模版的更深理解！！！

Thanks谢谢阅读！！！