【C++】map和set的封装（上）-阿里云开发者社区

1. 在STL中的map与set

在STL中，map和set都是使用的红黑树

map与set在STL中实现是一样的

对于value_type，map的第二个模板参数是pair，而set的第二个模板参数是key

这样写是为了map和set使用同一颗红黑树去复用map和set

set < K > -> rb_tree<K,K>

map<K,V> - > rb_tree<K,pair<const K,V>>

第一个模板参数拿到单独K的类型，使用Find erase接口函数的参数是K

第二个模板参数决定了树的节点是 K 类型 or K V类型

2. 修改自己实现的红黑树

在上一篇文章中，实现了红黑树的插入等接口功能，

但是只能对于K V使用，修改模板参数使K或者 K V 都能调用

点击查看: 自己实现的红黑树

修改结构定义

原本自己实现的红黑树模板为 template<class K,class V>

第一个参数代表 key ，第二个参数代表 value

把第二个参数改为 T 即 template<class K,class T>

按照STL的写法，使用第二个模板参数决定树的节点

原本的kv包含K V ，但是由于要调用map 和set，所以不知道到底传过来的是什么

所以使用模板类型的 data 代替

在结构定义时，为了让map与set都能调用同一颗红黑树，所以把模板参数改为T

当set要调用时，T变为<K,K>

当map要调用时，T变为<K,pair<const K,V>>

红黑树的insert中如何取到key

在insert中由于不知道data代表的是 pair还是K ，所以不能够取first

pair 虽然能够比较，但是不符合预期，所以要自己实现一个仿函数

我们要把key取出来，但是在红黑树中并不知道调用的是 set 还是map，无法知道T代表什么

但是在使用set或者map内部是知道的,所以分别在map和set内部各自创建一个内部类，其中都写一个operator()

在函数模板中添加一个参数，即可找到对应map/set的key值

在红黑树内部，使用类实例化一个对象kot，通过kot去调用map/set 中相同的operator() ，取出对应的key值

迭代器

set/map的迭代器是红黑树内部的迭代器

第二个模板参数Ref 第三个模板参数Ptr都是为了迭代器与const迭代器传参时有不同的参数存在，

从而区分普通迭代器与const迭代器

在list的模拟实现中有详细解释关于参数Ref 与Ptr 以及operator != -> * 的基本相似的使用

点击查看: 迭代器详细解释

operator++

若当前右子树不为空，则下一个节点为右树的最左节点即蓝色节点

6的右子树为空，并且6作为1的右子树，需要继续往上寻找

将parent作为新的cur节点，把爷爷节点作为parent节点

6作为1的右子树，说明1已经遍历完了，所以把1及1的左右子树看作一个整体，1整体是8的左子树，

所以下一个节点返回8

若右子树为空，并且孩子作为父节点的左子树，则直接把父节点返回即可

operator - -

左子树若不为空，则寻找左子树的最右节点

cur为当前节点，若cur的左子树为空，并且作为parent的右子树，则直接返回

parent节点

begin

begin返回的是开头的数据即中序遍历的第一个即最左节点

end

end返回最后一个数据的下一个即nullptr

typename 问题

加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型

在set.h中，寻找到红黑树的迭代器，通过该迭代器调用对应的begin和end ，来实现set的begin和end

map 中 operator[]的实现

将insert的返回值设置成迭代器加布尔值

若插入成功，返回新插入节点的迭代器

若插入失败，返回已经有的节点的迭代器

在map中，通过设置好的insert返回值来达到[]的作用

operwator [] 详细的解析，点击查看迭代器部分 : map和set的使用

解决自己实现的迭代器的key值可以被修改问题

自己实现的迭代器的key值可以被修改，但是在STL实际上是不能被修改的

在STL中，普通迭代器和const迭代器都是const迭代器

在set中同样做出相同的修改，即可解决问题

begin调用的是红黑树的普通迭代器，但是return返回的const迭代器

，所以正常运行时会报错

自己去实现一个普通迭代器类型，当类模板实例化为iterator时，则红框为拷贝构造

当类模板实例化为const_iterator时，通过发生隐式类型转换，使用普通迭代器构造const迭代器

3. 完整代码

RBTree.h

#pragma once
#include<iostream>
#include<cassert> 
using namespace std;
enum colour
{
  RED,//红色 默认为0
  BLACK,//黑色 默认为1
};
template<class T>
struct  RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  T _data;//当前节点值 
  colour _col;//表示颜色
  RBTreeNode(const T& data)
    :_left(nullptr),
    _right(nullptr),
    _parent(nullptr),
    _data(data),
    _col(RED)
  {
  }
};
//迭代器
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)
  {
  }
  //_RBTreeIterator<T,T&,T*> 为普通迭代器
  //这样就可使普通迭代器构造const迭代器 完成隐式类型转换
  _RBTreeIterator(const _RBTreeIterator<T,T&,T*> &it)
    :_node(it._node)
  {
  }
  Ref operator*()
  {
    return _node->_data;
  }
  Ptr operator->()
  {
    return  &_node->_data;
  }
  bool operator!=(const self& s)
  {
    return _node != s._node;
  }
  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;
    }
    return *this;
  }
  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;
  }
};
//仿函数
template<class K, class T, class keyOfT>
class RBTree
{
  typedef RBTreeNode<T>  Node;
public:
  ~RBTree()//析构
  {
    _Destroy(_root);
    _root = nullptr;
  }
public:
  typedef _RBTreeIterator<T, T&, T*> iterator;
  typedef _RBTreeIterator<T, const T&, const T*> const_iterator;
  iterator begin()//开头的数据
  {
    Node* cur = _root;
    //寻找最左节点
    while(cur&&cur->_left)
    {
      cur = cur->_left;
    }
    return iterator(cur);
  }
  iterator end()//最后一个数据的下一个
  {
    return iterator(nullptr);
  }
  const_iterator begin()const //开头的数据
  {
    Node* cur = _root;
    //寻找最左节点
    while (cur && cur->_left)
    {
      cur = cur->_left;
    }
    return const_iterator(cur);
  }
  const_iterator end()const//最后一个数据的下一个
  {
    return const_iterator(nullptr);
  }
  Node* Find(const K & key)//查找
  {
    Node* cur = _root;
    keyOfT kot;
    while (cur)
    {
      //kot(cur->_data) 取出当前的key值 
      //_data 有可能为 K 或者 pair类型
      if (kot(cur->_data) > key)
      {
        cur = cur->_left;
      }
      else if (kot(cur->_data) < key)
      {
        cur = cur->_right;
      }
      else
      {
        return cur;
      }
    }
    return nullptr;
  }
  pair<iterator,bool> insert(const T& data)
  {
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK;//若刚插入一个节点，则该节点颜色是黑色
      return make_pair(iterator(_root),true);
    }
    keyOfT kot;
    Node* parent = nullptr;//用于记录cur的前一个节点
    Node* cur = _root;
    while (cur)
    {
      //若插入的值比当前树的值小 插入左边
      //kot(cur->_data) 找到对应的key值
      if (kot(cur->_data) >kot(data))
      {
        parent = cur;
        cur = cur->_left;
      }
      //若插入的值比当前树的值大 插入右边
      else if (kot(cur->_data)< kot(data))
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        //若插入的值，在树中有相同的值 ，则插入失败
        return make_pair(iterator(cur), true);
      }
    }
    cur = new Node(data);
    Node* newnode = cur;
    //再次判断parent当前节点值与插入值大小
    if (kot(parent->_data) > kot(data))
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    //cur的上一个节点即为 刚才的记录cur前一个节点的parent
    cur->_parent = parent;
    //当父节点不为NULL并且父节点为红色
    while (parent != nullptr && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;//爷爷节点
      //若父节点为爷爷节点的左子树，则unlce为爷爷节点的右子树
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
        //       g
        //    p     u
        // c
        //情况1:u存在并且为红，直接变色即可，并继续往上处理
        if (uncle && uncle->_col == RED)
          //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        //情况2+3:u不存在或者u存在且为黑，旋转+变色
        else
        {
          //情况2
          //g p c 作为一条直线 所以为单旋
          //    g
          //  p   u
          //c 
          if (cur == parent->_left)
          {
            //右旋转
            RotateR(grandfather);
            //最终p作为最终的根 为黑  g为红 
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          //情况3
          //g p c 作为一条折线 所以为双旋
          //    g
           //   p   u
           //     c 
          else
          {
            //左单旋
            RotateL(parent);
            //右单旋
            RotateR(grandfather);
            //最终cur作为最终的根 为黑  g为红 
            cur->_col = BLACK;
            grandfather->_col = RED;
            //父节点继续保持红色
            parent->_col = RED;
          }
          break;
        }
      }
      else//grandfather->_right == parent
        若父节点为爷爷节点的右子树，则unlce为爷爷节点的左子树
      {
        //   g
        // u   p
        //       c
        Node* uncle = grandfather->_left;
        //情况1:u存在并且为红，直接变色即可，并继续往上处理
        if (uncle && uncle->_col == RED)
          //若uncle节点为红色，将parent与uncle都置为黑色，爷爷节点置为红色
        {
          parent->_col = BLACK;
          uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上调整
          cur = grandfather;
          parent = cur->_parent;
        }
        //情况2+3:u不存在或者u存在且为黑，旋转+变色
        else
        {
          //情况2
          //g p c 作为一条直线 所以为单旋
          //    g
          //  u   p
          //        c  
          if (cur == parent->_right)
          {
            //左旋转 
            RotateL(grandfather);
            //最终p作为最终的根 为黑  g为红 
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          //情况3
          //g p c 作为一条折线 所以为双旋
          //   g
           //  u   p
           //    c 
          else
          {
            //右单旋
            RotateR(parent);
            //左单旋
            RotateL(grandfather);
            //最终cur作为最终的根 为黑  g为红 
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    //为了避免grandfather节点正好为根时，会被更新成红色的情况
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
  void inorder()//中序遍历
  {
    _inorder(_root);
    cout << endl;
  }
  //判断一颗二叉树是否为红黑树
  bool isbalance()
  {
    //检查根是否为黑
    if (_root && _root->_col == RED)
    {
      cout << "根节点颜色是红色" << endl;
      return false;
    }
    //连续的红色节点
    return _check(_root, 0);
  }
private:
  void _Destroy(Node*root)//销毁
  {
    if (root == nullptr)
    {
      return;
    }
     //后序遍历
    _Destroy(root->_left);
    _Destroy(root->_right);
    delete root;
  }
  bool _check(Node* root, int blacknum)
  {
    if (root == nullptr)
    {
      //为空时，blacknum代表一条路径的黑色节点个数
      cout << blacknum << " ";
      return true;
    }
    //blacknum代表黑色节点的个数
    if (root->_col == BLACK)
    {
      blacknum++;
    }
    //若当前节点为红 父节点也为红
    if (root->_col == RED
      && root->_parent
      && root->_parent->_col == RED)
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
    //遍历整棵树
    return  _check(root->_left, blacknum) && _check(root->_right, blacknum);
  }
  void _inorder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _inorder(root->_left);
    cout << root->_kv.first << " ";
    _inorder(root->_right);
  }
  void RotateL(Node* parent)//左单旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL != nullptr)
    {
      subRL->_parent = parent;
    }
    Node* ppnode = parent->_parent;//记录parent的前一个节点
    subR->_left = parent;
    parent->_parent = subR;
    if (ppnode == nullptr)//说明parent是根即代表整棵树
    {
      _root = subR;//subR作为新的根
      _root->_parent = nullptr;//subR的父节点指向原来的parent,所以要置nullptr
    }
    else//说明旋转的是一部分，所以要跟ppnode相连接
    {
      if (ppnode->_left == parent)//若连接在左子树上
      {
        ppnode->_left = subR;
      }
      else//若连接在右子树上
      {
        ppnode->_right = subR;
      }
      subR->_parent = ppnode;//将subR父节点置为ppnode
    }
  }
  void RotateR(Node* parent)//右单旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR != nullptr)
    {
      subLR->_parent = parent;
    }
    Node* ppnode = parent->_parent;//记录parent的父节点
    subL->_right = parent;
    parent->_parent = subL;
    if (ppnode == nullptr)//若旋转整棵树
    {
      _root = subL;
      _root->_parent = nullptr;
    }
    else//若旋转整棵树的部分子树
    {
      if (ppnode->_left == parent)
      {
        ppnode->_left = subL;
      }
      else
      {
        ppnode->_right = subL;
      }
      subL->_parent = ppnode;//使subL的父节点为ppnode
    }
  }
private:
  Node* _root = nullptr;
};

map.h

#pragma once
#include"RBTree.h"
namespace yzq
{
  template<class K, class V>
  class map
  {
    struct mapkeyOfT
    {
      const K& operator()(const pair<const K,V> & kv)
      {
        return kv.first;
      }
    };
  public:
    //加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型
    typedef typename RBTree<K, pair<const K,V>, mapkeyOfT>::iterator  iterator;
    iterator begin()//复用红黑树的begin
    {
      return _t.begin();
    }
    iterator end()//复用红黑树的end
    {
      return _t.end();
    }
  public:
    pair<iterator,bool> insert(const pair<const K, V>& kv)
    {
      //调用红黑树中的insert
      return _t.insert(kv);
    }
    V& operator[](const K&key)
    {
      pair<iterator,bool>ret=_t.insert(make_pair(key, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<const K, V>,mapkeyOfT> _t;
  };
  void test_map()
  {
    map<int, int> v;
    v.insert(make_pair(1, 1));
    v.insert(make_pair(2, 2));
    v.insert(make_pair(3, 3));
    map<int, int>::iterator it = v.begin();
    while (it != v.end())
    {
       cout << it->first << ":"<<it->second<<endl;
        ++it;
    }
  }
}

set.h

#pragma once
#pragma once
#include"RBTree.h"
namespace yzq
{
  template<class K>
  class set
  {
    struct setkeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
    //加入typename 是因为编译器无法识别RBTree<K, K,setkeyOfT>是静态变量还是类型
    typedef typename RBTree<K, K,setkeyOfT>::const_iterator  iterator;
    typedef typename RBTree<K, K, setkeyOfT>::const_iterator  const_iterator;
    iterator begin()//复用红黑树的begin
    {
      return _t.begin();
    }
    iterator end()//复用红黑树的end
    {
      return _t.end();
    }
  public:
    pair<iterator,bool> insert(const K& key)
    {
      return _t.insert(key);
    }
  private:
    RBTree<K, K, setkeyOfT> _t;
  };
  void test_set()
  {
    set<int> v;
    v.insert(1);
    v.insert(5);
    v.insert(2);
    v.insert(8);
    set<int>::iterator it = v.begin();
    while (it != v.end())
    {
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
}

【C++】map和set的封装（上）