C++【一棵红黑树封装 set 和 map】-阿里云开发者社区

🌇前言

红黑树的基本情况我们已经在上一篇文章中学习过了，本文主要研究的是红黑树的实际应用：封装实现 set 和 map，看看如何通过一棵红黑树满足两个不同的数据结构；在正式封装之前，先要对之前的红黑树进行完善，增加必要功能

🏙️正文

1、红黑树的完善

1.1、修改默认成员函数

红黑树 中的每个节点都可能开辟独立的内存空间，因此在涉及拷贝、赋值等操作时，默认生成的成员函数已经无法满足需求了 --> 会导致两个指针指向同一块空间，然后造成重复析构问题

所以我们需要对其中的 默认成员函数 进行改造，手动添加符合要求的 默认成员函数

1.1.1、默认构造

写出默认构造函数是为了后面的 拷贝构造 做准备，因为祖师爷规定：只要我们写了构造函数（比如拷贝构造），就需要提供一个不需要传递参数的默认构造函数，否则编译会报错

假设只写了 拷贝构造 函数，编译时会报错：

所以需要提供一个 默认构造函数

//因为写了拷贝构造，所以需要有默认构造
RBTree()
  :_root(nullptr)
{}

注意：默认构造函数的要求是：不需要传递参数的构造函数，所以全缺省的拷贝构造函数也行，但最好还是额外提供一个无参版本

1.1.2、析构 —> 遍历释放

红黑树 中的节点可能涉及 动态内存申请，而编译器生成的 析构函数 无法满足 红黑树 的需求：释放其中的每个节点，所以我们需要编写 析构函数，释放其中的每个节点，确保不会出现 内存泄漏 问题

释放思路： 借助后序遍历 -> 左右根的思想，遍历到每一个不为空的节点，然后释放即可

因为需要 递归释放，所以推荐将释放流程封装为单独的函数，方便进行递归，析构函数 直接调用即可

//析构
  ~RBTree()
  {
    _destroy(_root);
  }
protected:
  void _destroy(Node*& root)
  {
    if (root == nullptr)
      return;
    //后序遍历
    _destroy(root->_left);
    _destroy(root->_right);
    //销毁节点
    free(root);
    root = nullptr;
  }

细节：_destroy 中参数使用引用，可以在不同栈帧中置空同一个指针变量

1.1.3、拷贝构造 —> 深拷贝

编译器生成的 拷贝构造 是 浅拷贝，当 红黑树 中的节点涉及动态内存申请时，程序运行必然会崩溃（多个指针指向同一块空间，导致重复析构）

比如下图中的场景，就是使用了 编译器生成的拷贝构造函数（浅拷贝）

void RBTreeTest1()
{
  RBTree<int, string> rb1;
  rb1.Insert(make_pair(1, "a"));
  RBTree<int, string> rb2(rb1); //rb2 拷贝构造 rb1
}

此时就需要手动实现 拷贝构造（深拷贝） 了

深拷贝思路：照着被拷贝红黑树，逐个节点申请空间，并进行链接即可

类似于 根据中序、后序重构二叉树的思想

//拷贝构造
  RBTree(const RBTree<K, V>& tree)
    :_root(nullptr)
  {
    //深拷贝 ---> 遍历构造每个节点
    _root = _copy(tree._root);
  }
protected:
  Node* _copy(const Node* root)
  {
    if (root == nullptr)
      return nullptr;
    //构造新节点
    Node* new_node = new Node(root);
    //递归链接左右子树
    new_node->_left = _copy(root->_left);
    new_node->_right = _copy(root->_right);
    //注意父亲链的链接
    if (new_node->_left != nullptr)
      new_node->_left->_parent = new_node;
    if (new_node->_right != nullptr)
      new_node->_right->_parent = new_node;
    return new_node;
  }
• 29

借助 后序遍历 的思想重构好每个节点后，返给父亲进行链接，当整棵树都重构完成后，返回 根节点

注意：

拷贝构造函数中的参数需要使用引用，避免无穷递归问题
因为是三叉链结构，需要注意父指针的链接，判断不为空后直接链接即可

1.1.4、赋值重载

编译器生成的 赋值重载 函数也是 浅拷贝，实现 赋值重载 就比较简单了，有以下两种办法：

像拷贝构造一样，递归创建每一个节点
现代写法：直接与临时变量交换根节点

现代写法很简单，也更安全（只要拷贝构造没问题，那么现代写法也没问题），下面就是现代写法：

//赋值重载
RBTree<K, V>& operator=(RBTree<K, V> tmp)
{
  //直接交换根节点即可
  std::swap(_root, tmp._root);
  return *this;
}

tmp 是 临时变量，传递参数时，会自动进行一次拷贝构造函数的调用，生成临时对象，并且此时是深拷贝

临时变量 的资源不利用就浪费了，所以可以直接把它的 根节点 偷过来，间接完成了 红黑树 的赋值，原 红黑树 中的节点在函数运行后、临时变量 销毁时进行逐一释放（自动调用 析构函数）

注意：现代写法中的参数不能使用引用，否则会导致被赋值的红黑树节点丢失

1.2、新增迭代器

红黑树 中也有 迭代器，因为是链式结构，所以在进行 迭代器 设计时，需要单独设计一个 迭代器类，就像 list 一样

1.2.1、整体设计

将 红黑树 的节点再一次封装，构建一个单独的 迭代器 类

因为此时节点的模板参数有 K 和 V，所以 迭代器类 中也需要这两个参数

至于 迭代器类 设计时的精髓：不同类型的迭代器传递不同的参数 这里就不再展开叙述，简单来说，额外增加 Ref 和 Ptr 的目的是为了让 普通迭代器 和 const迭代器 能使用同一个 迭代器类

迭代器类中的多参数默认设计思想详见《C++ STL学习之【list的模拟实现】》

迭代器类 的大体框架如下：

//迭代器类
template<class K, class V, class Ref, class Ptr>
class __RBTreeIterator
{
  typedef RBTreeNode<K, V> Node;  //节点
  typedef __RBTreeIterator<K, V, Ref, Ptr> Self;  //迭代器
public:
  __RBTreeIterator()
    :_node(nullptr)
  {}
  //将节点构造为迭代器对象
  __RBTreeIterator(Node* root)
    :_node(root)
  {}
private:
  Node* _node;
};

其中的 Ref、Ptr 具体是什么类型，取决于调用方传递了什么

1.2.2、移动操作

迭代器 最重要的操作莫过于移动，红黑树 的迭代器是一个 双向迭代器，只支持 ++ 和 -- 操作

树形结构的容器在进行遍历时，默认按 中序遍历 的顺序进行迭代器移动，因为这样遍历 二叉搜索树 后，结果为有序

清楚遍历路径后，就可以设计具体操作了

正向移动 operator++() 与 operator++(int)

正向移动思路：

判断当前节点的右子树是否存在，如果存在，则移动至右子树中的最左节点
如果不存在，则移动至当前路径中孩子节点为左孩子的父亲节点
如果父亲为空，则下一个节点就是空

//前置++
Self operator++()
{
  //左根右
  //思路：如果右子树存在，访问右子树的最左节点；如果右子树不存在，访问父亲
  //注意：避免 _node 为空
  if (_node != nullptr && _node->_right != nullptr)
  {
    //访问右子树的最左节点
    Node* cur = _node->_right;
    while (cur->_left != nullptr)
      cur = cur->_left;
    _node = cur;
  }
  else if(_node != nullptr)
  {
    //访问父亲节点（cur 须位于父亲的左边）
    Node*  cur = _node;
    Node* parent = _node->_parent;
    while (parent && parent->_left != cur)
    {
      cur = parent;
      parent = cur->_parent;
    }
    _node = parent;
  }
  return *this;
}
//后置++
Self operator++(int)
{
  Self tmp = *this;
  ++(*this);
  return tmp;
}

为什么右子树不为空时，要访问 右子树的最左节点？

因为此时是正向移动，路径为 左根右，如果右边路径存在，就要从它的最左节点开始访问

为什么右子树为空时，要访问当前路径中 孩子节点为左孩子的父亲节点？

因为孩子节点为右孩子的父亲节点已经被访问过了

在这两种情况的组合之下，就可以完成 迭代器的正向移动

反向移动 operator--() 与 operator--(int)

反向移动很简单，就是与正向相反即可

反向移动思路：

判断当前节点的左子树是否存在，如果存在，则移动至左子树中的最右节点
如果不存在，则移动至当前路径中孩子节点为右孩子的父亲节点
如果父亲为空，则下一个节点就是空

//前置--
Self operator--()
{
  //右根左
  //思路：如果左子树存在，访问左子树的最右节点；如果左子树不存在，访问父亲
  //注意：避免 _node 为空
  if (_node != nullptr && _node->_left != nullptr)
  {
    //访问左子树的最右节点
    Node* cur = _node->_left;
    while (cur->_right != nullptr)
      cur = cur->_right;
    _node = cur;
  }
  else if(_node != nullptr)
  {
    //访问父亲节点（cur 必须置于父亲的右边）
    Node* cur = _node;
    Node* parent = _node->_parent;
    while (parent && parent->_right != cur)
    {
      cur = parent;
      parent = cur->_parent;
    }
    _node = parent;
  }
  return *this;
}
//后置--
Self operator--(int)
{
  Self tmp = *this;
  --(*this);
  return tmp;
}

至于为何要这两种不同的情况进行移动，上面的 正向移动 已经解释过了

以上就是红黑树中迭代器移动操作的相关实现

注意：在访问父亲节点前，需要先判断父亲是否为 nullptr，避免野指针

1.2.3、数据访问

数据访问 有两种方式：

直接解引用获取节点中的 _kv
获取节点中的 _kv 地址

具体实现如下：

//解引用
Ref operator*()
{
  return _node->_kv;
}
//成员访问
Ptr operator->()
{
  return &(operator*());  //复用
}

普通迭代器 创建对象时，传递的参数如下：

__RBTreeIterator<K, V, std::pair<K, V>&, std::pair<K, V>*>

此时的 Ref、Ptr 就是普通的类型，允许发生修改行为

而 const 迭代器 创建对象时，传递的参数如下：

__RBTreeIterator<K, V, const std::pair<K, V>&, const std::pair<K, V>*>

Ref、Ptr 是 const 对象，即不允许发生修改行为

这样一来，就能只通过一个 迭代器类，满足两个性质不同的 迭代器，这就是 泛型编程 思想的魅力

1.2.4、逻辑判断

在进行 迭代器 的 逻辑判断 时，可以直接两个 红黑树 节点是否为同一个

//判断相等
bool operator==(const Self& it) const
{
  return _node == it._node;
}
bool operator!=(const Self& it) const
{
  return !((*this) == it);  //复用

注意：是迭代器和迭代器比较，所以参数是 Self 即迭代器对象

1.2.5、迭代器测试

有了这些模块后，我们的 红黑树 类中就可以引入 迭代器 的相关操作了

//新增迭代器
typedef __RBTreeIterator<K, V, std::pair<K, V>&, std::pair<K, V>*> iterator;
typedef __RBTreeIterator<K, V, const std::pair<K, V>&, const std::pair<K, V>*> const_iterator;
iterator begin()
{
  //起始位置是最左节点
  Node* cur = _root;
  while (cur && cur->_left != nullptr)
    cur = cur->_left;
  return iterator(cur);
}
iterator end()
{
  return nullptr;
}
const_iterator begin() const
{
  //起始位置是最左节点
  Node* cur = _root;
  while (cur && cur->_left != nullptr)
    cur = cur->_left;
  return const_iterator(cur);
}
const_iterator end() const
{
  return nullptr;
}

先来简单玩玩这个 迭代器

void RBTreeTest2()
{
  vector<pair<int, string>> vp{ make_pair(1,"a"),make_pair(2,"b"),make_pair(3,"c"),make_pair(4,"d"),make_pair(5,"e") };
  RBTree<int, string> rb;
  for (auto& e : vp)
    rb.Insert(e);
  const RBTree<int, string> crb(rb);
  cout << "普通对象: " << endl;
  RBTree<int, string>::iterator it = rb.begin();
  while (it != rb.end())
  {
    //两种访问方式都行，但推荐第二种，更方便
    cout << (*it).first << " | " << it->second << endl;
    ++it;
  }
  cout << "const 对象: " << endl;
  RBTree<int, string>::const_iterator cit = crb.begin();
  while (cit != crb.end())
  {
    cout << cit->first << " | " << (*cit).second << endl;
    cit++;  //后置++ 也可以用
  }
}

此时基于迭代器的范围 for 也可以正常使用

注意：const 迭代器是为 const 对象提供的，所以可以选择重载 begin() 与 end()，也可以选择重新编写 cbegin() 和 cend()，二者除了函数名外，其他都是一样的

1.3、反向迭代器的设计

红黑树 的反向迭代器比较难搞，因为 反向迭代器类 中为了追求极致对称，rbegin() 是最后一个节点的下一个节点，即 红黑树中最右节点的下一个节点

由于 三叉链 结构的特殊性，我们实现的 红黑树 中没有指向 最右节点 的节点，既然没有，那就创造一个，这正是 SGI 版 STL 中 红黑树 的实现方法，它的根节点 _root 的父亲不是空，而是搞了一个 header 节点，让根节点指向它，它的左右指针分别指向 最左节点、最右节点

新增了这个节点后，之前的逻辑都要发生改变，比如 end() 不再是空，而是 header；涉及最左/最右节点的插入后，都要更新 header 的指向，这种方法在进行迭代器操作时比较友好，其他场景下就比较麻烦了，需要额外维护一个节点

如果按库中的 红黑树定义，rbegin() 就是 header 这个节点，因为它指向 最右节点

为了避免破坏前面的操作，我们可以额外新增一个成员：header 指向最右节点，在调用 rbegin() 时对其进行更新并返回即可，属于一个比较中庸的解决方案，默认构造、拷贝构造、赋值、析构记得对这个节点进行处理

额外新增一个节点，不会影响其他节点，也不会影响前面的逻辑

private:
  Node* _root = nullptr;
  Node* _header = nullptr;  //指向最右节点
• 1
• 2
• 3

涉及构造、初始化等操作时，需要带上 _header

反向迭代器的设计如下：

#include "reverse_iterator.hpp"
typedef __reverse_iterator<iterator, std::pair<K, V>&, std::pair<K, V>*> reverse_iterator;  //反向迭代器
typedef __reverse_iterator<const_iterator, const std::pair<K, V>&, const std::pair<K, V>*> const_reverse_iterator;
//反向迭代器
reverse_iterator rbegin()
{
  //返回指向最右节点的节点
  Node* cur = _root;
  while (cur && cur->_right != nullptr)
    cur = cur->_right;
  _header->_left = cur;
  return reverse_iterator(_header);
}
reverse_iterator rend()
{
  //返回最后一个节点的上一个节点，即最左节点
  Node* cur = _root;
  while (cur && cur->_left != nullptr)
    cur = cur->_left;
  return reverse_iterator(cur);
}
const_reverse_iterator rbegin() const
{
  //返回指向最右节点的节点
  Node* cur = _root;
  while (cur && cur->_right != nullptr)
    cur = cur->_right;
  _header->_left = cur;
  return const_reverse_iterator(_header);
}
const_reverse_iterator rend() const
{
  //返回最后一个节点的上一个节点，即最左节点
  Node* cur = _root;
  while (cur && cur->_left != nullptr)
    cur = cur->_left;
  return const_reverse_iterator(cur);
}

为什么一定要搞一个 辅助节点指向最右节点？

因为反向迭代器类比较奇怪 rbegin() 表示的是最后一个节点的下一个节点，所以为了与之适配，只能新增一个辅助节点

关于反向迭代器类的实现详见《C++ STL学习之【反向迭代器】》

其实库中解决方案是最优的，但这种方案会影响到前面的很多代码逻辑，于是我们选择了较为折中的方案

可以简单测试一下反向迭代器：

至此 红黑树 算是完善了，比较麻烦的是 迭代器 的实现，需要对 ++ 和 -- 进行分析，借助辅助节点 _header，最后也是成功利用 反向迭代器适配器 适配出了 红黑树的反向迭代器

注意：是 _header 的 _left 链接最右节点，因为反向迭代器中的 ++ 相当于 --，下一个节点是左子树的最右节点，就是整个红黑树中的最右节点

2、封装实现

下面可以正式步入本文的主题：用一棵红黑树封装实现 set 和 map

红黑树的封装实现会涉及部分代码改动

为了进行区分，红黑树的完善代码名为 RBTree - 副本.hpp 存放在 Gitee 仓库中

2.1、解决 k 与 k/v 的参数冲突

在同时封装 set 和 map 时，面临第一个问题：两者参数不匹配

set 只需要 key
map 则需要 key 和 value

这就意味着一棵 红黑树 无法满足不同需求，难道真无法满足吗？

答案当然是 可以的

参考库中的解决方案：管你是 k 还是 k/v，我都看作 value_type，获取 key 值时再另想其他方法解决

注：re_tree 的参数3是获取 key 的方式（后续介绍），参数4是比较方式，参数5是空间配置器

能否省略 参数1 key_type ？

对于 set 来说，可以，因为冗余了
但对于 map 来说，不行，因为 map 中的函数参数类型为 key_type，省略后就无法确定参数类型了，比如 Find、Erase 中都需要 key_type 这个类型

这一波是 set 为 map 做出了牺牲，迁就了 map

红黑树 改造第一步：接口调整

注：库中的 value_type 太长了，这里改为 T，既能表示 k，也能表示 k/v；原红黑树节点中的 _kv 改成了 _data

红黑树 从之前的 K V 变成了现在的 K T，这样一来，凡是之前涉及 K V 的地方都要改，比如：节点类和迭代器

//红黑树的节点类
template<class T>
struct RBTreeNode
{
  RBTreeNode(T data = T())
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
    , _col(RED) //默认新节点为红色，有几率被调整
  {}
  //拷贝构造
  RBTreeNode(const T*& node)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(node->_data)
    , _col(node->_col)  //默认新节点为红色，有几率被调整
  {
    //拷贝节点中的信息
  }
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  T _data;
  Color _col;
};
//迭代器类
template<class T, class Ref, class Ptr>
class __RBTreeIterator
{
  typedef RBTreeNode<T> Node; //节点
  typedef __RBTreeIterator<T, Ref, Ptr> Self; //迭代器
  //……
};
//红黑树类
template<class K, class T>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  //……
  //新增迭代器
  typedef __RBTreeIterator<T, T&, T*> iterator;
  typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
  typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;  //反向迭代器
  typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
  //……
};

除此之外仍有许多需要修改的地方，这里就不一一展示

红黑树 的接口经过这样一改之后，set 和 map 就可以传递各自的参数了

Set.hpp

#pragma once
#include <iostream>
#include "RBTree.hpp"
using Yohifo::RBTree;
namespace Yohifo
{
  template<class K>
  class set
  {
    typedef RBTree<K, K> Tree;
  private:
    Tree _t;  //这是一棵红黑树树
  };
}

Map.hpp

#pragma once
#include <iostream>
#include "RBTree.hpp"
using Yohifo::RBTree;
namespace Yohifo
{
  template<class K, class V>
  class map
  {
    typedef RBTree<K, std::pair<const K, V>> Tree;
  private:
    Tree _t;  //这也是一棵红黑树
  };
}

注意：map 中 pair 的第一个参数 K 需要使用 const 修饰，因为这是不可被修改的

接下来就很简单了，直接使用 红黑树 中的接口即可（此处给 红黑树 新增了一个 Find 函数，代码如下）

bool Find(const K& key) const
{
  if (_root == nullptr)
    return false;
  Node* cur = _root;
  while (cur)
  {
    if (cur->_data.first < key)
      cur = cur->_right;
    else if (cur->_data.second > key)
      cur = cur->_left;
    else
      return true;
  }
  return false;
}

可以看到，Find() 的参数类型为 K

此时面临着一个尴尬的问题：当 T 为 key 时，_data 不是 pair，自然没有 first 和 second，程序也就无法跑起来

Insert() 也是如此，凡是涉及获取 key 的地方都有这个问题，因为此时的 _data 是不确定的，对于这种不确定的类型，一般使用 仿函数 解决

2.2、解决不同类型的 key 获取问题

现在可以看看库中 rb_tree 的参数3了，它是一个 函数对象，可以传递 仿函数，主要是用来从不同的 T 中获取 key 值

set 中的 key 值就是 key，而 map 中的 key 值是 pair<K, V> 中的 first

所以 红黑树 的接口继续改进，新增 KeyOfT 这个模板参数

注：此时只需要在红黑树类中新增

//红黑树类
template<class K, class T, class KeyOfT>
class RBTree
{
  //……

分别针对这两种不同的情况设计仿函数：

Set.hpp

template<class K>
class set
{
  //仿函数：获取 key 值
  struct SetKeyOfT
  {
    const K& operator()(const K& key) const
    {
      return key;
    }
  };
  typedef RBTree<K, K, SetKeyOfT> Tree;
private:
  Tree _t;  //这是一棵红黑树树
};

Map.hpp

template<class K, class V>
class map
{
  //仿函数：获取 key 值
  struct MapKeyOfT
  {
    const K& operator()(const std::pair<K, V>& kv) const
    {
      return kv.first;
    }
  };
  typedef RBTree<K, std::pair<K, V>, MapKeyOfT> Tree;
private:
  Tree _t;  //这也是一棵红黑树
};

这一波依然是 set 为了 map 做出了牺牲~

至于 rb_tree 中参数3，也是一个仿函数，主要是用来规定 pair 中的比较方式的

当我们得到不同的 key 值获取方式后，就可以更改红黑树中相应的代码了

比如：查找、插入

bool Find(const K& key) const
{
  KeyOfT kot; //创建一个对象，用来获取 key 值
  if (_root == nullptr)
    return false;
  Node* cur = _root;
  while (cur)
  {
    //operator()(data) 运算符重载，根据不同的对象，使用不同的获取方式
    if (kot(cur->_data) < key)
      cur = cur->_right;
    else if (kot(cur->_data) > key)
      cur = cur->_left;
    else
      return true;
  }
  return false;
}
bool Insert(const T& data)
{
  KeyOfT kot;
  if (_root == nullptr)
  {
    _root = new Node(data);
    _root->_col = BLACK;  //根节点一定是黑色
    return true;
  }
  //寻找合适位置
  Node* parent = nullptr;
  Node* cur = _root;
  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 false;
    }
  }
  //插入节点
  cur = new Node(data);
  if (kot(parent->_data) < kot(data))
    parent->_right = cur;
  else
    parent->_left = cur;
  cur->_parent = parent;
  //判断是否需要 染色、旋转
  //……
}

现在代码可以跑起来了，先简单填充一下 set 和 map 中的基本操作

Set.hpp

public:
  bool Find(const K& key)
  {
    return _t.Find(key);
  }
  bool Insert(const K& key)
  {
    return _t.Insert(key);

Map.hpp

public:
  bool Find(const K& key)
  {
    return _t.Find(key);
  }
  bool Insert(const std::pair<K, V>& kv)
  {
    return _t.Insert(kv);
  }

测试自己封装的 set 和 map

void SetAndMapTest1()
{
  set<int> s;
  map<int, int> m;
  s.Insert(1);
  s.Insert(2);
  s.Insert(3);
  s.Insert(4);
  s.Insert(5);
  m.Insert(make_pair(1, 1));
  m.Insert(make_pair(2, 2));
  m.Insert(make_pair(3, 3));
  m.Insert(make_pair(4, 4));
  m.Insert(make_pair(5, 5));
  for (int i = 3; i < 8; i++)
  {
    cout << "set Find " << i << " -> " << s.Find(i) << endl;
    cout << "map Find " << i << " -> " << m.Find(i) << endl;
    cout << "=====================================" << endl;
  }
}

查找和插入没有问题（其实只要底层结构足够稳定，像这种表面封装是不太容易出问题的）

继续完善

set 新增迭代器、判空、求大小、计数
map 也是一样，新增 set 中新增的功能

注：关于默认成员函数，编译器生成的足够用了，因为此时的 _t 是一个自定义类型，涉及拷贝、赋值等问题时，会去调用红黑树中相应的函数，所以我们不需要实现

还是那句话：底层的数据结构足够强大，封装的时候就不需要操太多心

对于 set 和 map 都需要的函数，可以在 红黑树 中统一实现，两者分别调用即可

RBTree.hpp

bool Empty() const
{
  return _root == nullptr;
}
size_t Size() const
{
  //将底层容器遍历一遍即可
  size_t cnt = 0;
  for (auto& e : *this)
    cnt++;
  return cnt;
}
size_t Count(const K& key) const
{
  KeyOfT kot;
  //统计 key 的数量
  size_t cnt = 0;
  for (auto& e : *this)
  {
    //此时的 e 就是 key
    if (kot(e) == key)
      cnt++;
  }
  return cnt;
}

Set.hpp

注：typename 的作用是告诉编译器这是一个类型

//迭代器
typedef typename Tree::iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_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(); }
reverse_iterator rbegin() { return _t.rbegin(); }
reverse_iterator rend() { return _t.rend(); }
const_reverse_iterator rbegin() const { return _t.rbegin(); }
const_reverse_iterator rend() const { return _t.rend(); }
bool Empty() const
{
  return _t.Empty();
}
size_t Size() const
{
  return _t.Size();
}
size_t Count(const K& key) const
{
  return _t.Count(key);
}

Map.hpp

//迭代器
typedef typename Tree::iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_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(); }
reverse_iterator rbegin() { return _t.rbegin(); }
reverse_iterator rend() { return _t.rend(); }
const_reverse_iterator rbegin() const { return _t.rbegin(); }
const_reverse_iterator rend() const { return _t.rend(); }
bool Empty() const
{
  return _t.Empty();
}
size_t Size() const
{
  return _t.Size();
}
size_t Count(const K& key) const
{
  return _t.Count(key);
}

可以简单测试一波

注意：在红黑树中，凡是涉及 key 获取的地方，都要通过 KeyOfT 的方式进行获取，因为 _data 的类型不确定

2.3、解决 set 迭代器的非法操作

此时的代码仍然存在问题：set 中只有 key，key 是不能修改的，但此时 set 中的 key 可以被修改！

void SetAndMapTest3()
{
  vector<int> arr = { 8,6,3,2,1 };
  set<int> s;
  for (auto e : arr)
    s.Insert(e);
  cout << "修改前: ";
  for (auto& e : s)
  {
    cout << e << " ";
    e = 1;
  }
  cout << endl;
  cout << "修改后: ";
  for (auto& e : s)
    cout << e << " ";
  cout << endl;
}

此时居然能将 set 中的 key 进行修改！？这是非常不合理的

库中给出的解决方案：对于 set 来说，无论是否为 const 迭代器，都使用红黑树中的 const 迭代器进行适配

也就是说，锁死了 set 中迭代器的修改权限，此时自然无法修改 key 值

此时迭代器类中的 Ref 和 Ptr 都是 const 版本

Set.hpp

//迭代器
typedef typename Tree::const_iterator iterator;
typedef typename Tree::const_iterator const_iterator;
typedef typename Tree::const_reverse_iterator reverse_iterator;
typedef typename Tree::const_reverse_iterator const_reverse_iterator;

修改完成，VS 启动，代码，运行

结果：出现了一个编译错误

注意：先要把修改相关的代码屏蔽，否则会导致这个错误无法出现

出现错误的原因

在 set 中，普通对象调用 begin() 或 end() 时，返回的是普通迭代器，但此时的 iterator 是 const 迭代器，这就涉及一个类型转换问题了，其中的 Ref、Ptr 类型不匹配！

解决方案：在红黑树迭代器类中新增一个特殊的构造函数

当类模板实例化为普通迭代器时，就是一个普通的拷贝构造函数
当类模板实例化为 const 迭代器时，则是一个特殊的构造函数 -> 将普通的迭代器对象 -> 构造为 const 迭代器

typedef __RBTreeIterator<T, T&, T*> iterator; //普通迭代器
//特殊的构造函数
__RBTreeIterator(const iterator& it)
  :_node(it._node)  //构造 或 拷贝构造
{}

如何做到的？

当创建 set（普通对象）中的普通迭代器时，因为此时是普通对象，所以红黑树底层会返回一个普通迭代器，但对于 set 来说，无论是否为 const 对象，它要返回的都是 const 迭代器，于是它会把红黑树返回的普通迭代器 -> 借助特殊的构造函数 -> 构造为 const 迭代器
如果 set 是 const 对象，那么红黑树返回的就是 const 迭代器，都不用进行类型转换了

这种写法对于 map 是否有影响？

没有影响，对于 map 来说，普通对象对应的就是普通迭代器，不存在普通迭代器转为 const 迭代器这种情况

新增这个特殊的构造函数后，能正常编译，将 e = 1 这条赋值语句取消注释，再编译，可以发现出现了预料中的报错信息：不能给常量对象赋值

注意：set 中的普通对象对应的也是 const 迭代器，但底层红黑树仍然是普通对象，返回的普通迭代器无法转换为 set 中的 const 迭代器，需要通过特殊构造函数解决；不能单纯的通过 const 修饰迭代器暴力解决问题，因为这样会出现 const const 的问题

2.4、调整函数返回值

set 和 map 中部分函数的返回值比较特殊，不是单纯的 bool

比如 Find() 返回的是 迭代器，查找成功返回所在位置的迭代器，失败返回最后一个位置的迭代器

Insert 插入时，成功返回《新节点所在位置迭代器与 true》构成的 pair，失败则返回《冗余节点所在位置的迭代器与 false》构成的 pair

将 红黑树 中的对应函数进行改造

RBTree.hpp

iterator Find(const K& key) const
{
  KeyOfT kot; //创建一个对象，用来获取 key 值
  if (_root == nullptr)
    return iterator(nullptr);
  Node* cur = _root;
  while (cur)
  {
    //operator()(data) 运算符重载，根据不同的对象，使用不同的获取方式
    if (kot(cur->_data) < key)
      cur = cur->_right;
    else if (kot(cur->_data) > key)
      cur = cur->_left;
    else
      return iterator(cur);
  }
  return iterator(nullptr);
}
std::pair<iterator, bool> Insert(const T& data)
{
  KeyOfT kot;
  if (_root == nullptr)
  {
    _root = new Node(data);
    _root->_col = BLACK;  //根节点一定是黑色
    return std::make_pair(iterator(_root), true);
  }
  //寻找合适位置
  Node* parent = nullptr;
  Node* cur = _root;
  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 std::make_pair(iterator(cur), true);
    }
  }
  //插入节点
  //……
  //判断是否需要 染色、旋转
  //……
  return std::make_pair(iterator(new_node), true);
}

set 与 map 中做出相应调整即可

Set.hpp

iterator Find(const K& key) const
{
  return _t.Find(key);
}
std::pair<iterator, bool> Insert(const K& key)
{
  return _t.Insert(key);
}

Map.hpp

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

可以通过代码测试一下

清楚了 Insert 的返回值之后，就可以轻而易举的理解下图了

2.5、map 新增 operator[]

map 比 set 多一个 operator[] ，主要作用是用来 访问 value

并且 operator[] 还是一个多功能函数，兼顾 插入、修改、插入+修改、查找

具体实现如下：

Map.hpp

V& operator[](const K& key)
{
  //首先插入
  auto ret = Insert(std::make_pair(key, V()));
  //插入成功：获取新迭代器
  //插入失败：返回已存在节点迭代器
  auto it = ret.first;  //获取迭代器
  return it->second;  //返回 value
}

可以测试一下：

至此，用一颗 红黑树 完成 set 和 map 的封装就算完成了

3、性能测试

将自己封装的 set 与库中的 set 进行一波性能对比（Release 模式下）

#include <set>
void SetAndMapTest6()
{
  Yohifo::set<int> mySet;
  std::set<int> stdSet;
  srand((size_t)time(NULL));
  int mySetTime = 0;
  int stdSetTime = 0;
  clock_t begin, end;
  int sum = 0;
  int n = 5000000;
  for (int i = 0; i < n; i++)
  {
    int val = rand() % n + i;
    begin = end = 0;
    begin = clock();
    auto ret1 = mySet.Insert(val);
    end = clock();
    mySetTime += (end - begin);
    begin = end = 0;
    begin = clock();
    auto ret2 = stdSet.insert(val);
    end = clock();
    stdSetTime += (end - begin);
    if (ret1.second && ret2.second)
      sum++;  //成功插入的数据量
  }
  cout << "成功插入 " << sum << " 个数据" << endl;
  cout << "mySet 耗时: " << mySetTime << " ms" << endl;
  cout << "stdSet 耗时: " << stdSetTime << " ms" << endl;
}

成功插入 300w+ 数据，结果与库中的 set 性能差不多，证明我们这棵红黑树还是很强的

4、完整源码

关于本次完善的红黑树、封装实现 set 和 map 的相关代码在下面这个 Gitee 仓库中

《封装set和map博客》

🌆总结

以上就是本次关于 C++【一棵红黑树封装 set 和 map】的全部内容了，在本文中，我们首先将红黑树进行了完善，解决了一些深拷贝问题，新增了迭代器，同时还用反向迭代器适配器适配出了反向迭代器，当红黑树完善后，我们用同一棵红黑树同时封装实现了 set 和 map，其中涉及大量泛型编程思想，值得仔细推敲

相关文章推荐
C++ 进阶知识
C++【红黑树】
C++【AVL树】
C++【set 和 map 学习及使用】
C++【二叉搜索树】
C++【多态】
C++【继承】
STL 之泛型思想
C++【模板进阶】
C++【模板初阶】

C++【一棵红黑树封装 set 和 map】

🌇前言

🏙️正文

1、红黑树的完善

1.1、修改默认成员函数

1.1.1、默认构造

1.1.2、析构 —> 遍历释放

1.1.3、拷贝构造 —> 深拷贝

1.1.4、赋值重载

1.2、新增迭代器

1.2.1、整体设计

1.2.2、移动操作

1.2.3、数据访问

1.2.4、逻辑判断

1.2.5、迭代器测试

1.3、反向迭代器的设计

2、封装实现

2.1、解决 k 与 k/v 的参数冲突

2.2、解决不同类型的 key 获取问题

2.3、解决 set 迭代器的非法操作

2.4、调整函数返回值

2.5、map 新增 operator[]

3、性能测试

4、完整源码

🌆总结

热门文章

最新文章

相关课程

相关电子书