一. 整体框架梳理

所谓低层被高层封装就是低层类要作为高层类的成员变量。比如红黑树和迭代器，它们的成员变量都是一个树的节点；而map和set类的成员变量是同一颗红黑树，它们的接口都是通过直接或间接调用红黑树的接口实现的。

二. 节点类

节点类是一个类模板，模板参数ValueType就是节点存储的数据的类型。成员变量包括指向父亲、左右孩子的指针，节点的颜色和节点存储的数据。成员函数就只有一个构造函数，传入一个ValueType的数据来构造一个节点。

// 枚举定义颜色
enum COLOR
{
  RED,
  BLACK
};
// 节点的定义
template<class ValueType>
struct RBTreeNode
{
  // 构造函数，颜色默认给为红色
  RBTreeNode(const ValueType& data)
    :_color(RED)
    ,_data(data)
    ,_parent(nullptr)
    ,_left(nullptr)
    ,_right(nullptr)
  {}
  COLOR _color;
  ValueType _data;
  RBTreeNode<ValueType>* _parent;                                                                                     
  RBTreeNode<ValueType>* _left;
  RBTreeNode<ValueType>* _right;
};

三. 迭代器

1. 迭代器的基本框架

底层封装一个树节点的指针_node，所以构造函数是传入一个树节点的指针让_node指向它。

template<class ValueType, class Ref, class Ptr>
class RBTreeItetator
{
    typedef RBTreeNode<ValueType> Node;
    typedef RBTreeItetator<ValueType, Ref, Ptr> self;
  public:
    RBTreeItetator(Node* node)
      :_node(node)
    {}
  private:
    Node* _node;
};

为了实现const迭代器，模板参数除了节点的数据类型外还引入了数据类型的引用（Reference）和数据类型的指针（Pointer）。在迭代器重载解引用和箭头运算符时，不论外面传入的模板参数是什么，都返回Ref和Ptr，可以看到这两个模板参数的引入使得代码更加灵活，这是模板优点的体现，也是泛型编程思想的一个体现。

2. operator++ 和 operator- -

先看自增，我们想要这个迭代器指向下一个节点，根据中序遍历的规则可以得到下面结论：

如果右不为空，中序的下一个就是右子树的最左节点。

如果右为空，表示当前节点所在的子树已经遍历完成，下一个节点为沿着路径往上孩子是它的左的那个祖先。

自减操作的话，就是找前一个节点，和自增的思路相反，不再赘述。它们的实现如下：

// 前置自增操作
self& operator++()    
{    
  if(_node->_right)    
  {    
    Node* subRL=_node->_right;    
    while(subRL->_left)                                                                                                     
    {    
      subRL=subRL->_left;    
    }    
    _node=subRL;    
  }    
  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* subLR=_node->_left;
    while(subLR->_right)
    {
      subLR=subLR->_right;
    }
    _node=subLR;
  }
  else 
  {
    Node* cur=_node;
    Node* parent=cur->_parent;
    while(parent && cur==parent->_left)
    {
      cur=parent;
      parent=parent->_parent;
    }                                                                                                                       
    _node=parent;
  }
  return *this;
}

3. operator* 和 operator->

解引用就是返回节点中存储的数据的引用，箭头返回节点中存储数据的指针。

Ref operator*()
{
  return _node->_data;
}
Ptr operator->()
{
  return &_node->_data;
}

编译器对箭头操作符的特殊处理

所谓迭代器就是模拟像指针一样的东西，我们希望通过解引用迭代器来直接获取所存储的数据对象本身，我们上面的实现确实做到了；我们也希望通过箭头操作符操作迭代器直接访问存储数据内的成员，在使用箭头操作符时会遇到一些问题。

4. operator== 和 operator!=

比较两个迭代器是否相等，就是比较底层的成员变量即节点对象是否相等。

bool operator==(const self& it)
{
  return _node == it._node;
}
bool operator!=(const self& it)
{
  return _node != it._node;
}

5. 迭代器完整代码

// 迭代器    
template<class ValueType, class Ref, class Ptr>    
class RBTreeItetator    
{    
    typedef RBTreeNode<ValueType> Node;    
    typedef RBTreeItetator<ValueType, Ref, Ptr> self;    
  public:                                                                                                                       
    RBTreeItetator(Node* node)    
      :_node(node)    
    {}    
    self& operator++()    
    {    
      if(_node->_right)    
      {    
        Node* subRL=_node->_right;    
        while(subRL->_left)    
        {    
          subRL=subRL->_left;    
        }    
        _node=subRL;    
      }    
      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* subLR=_node->_left;
        while(subLR->_right)
        {                                                                                                                       
          subLR=subLR->_right;
        }
        _node=subLR;
      }
      else 
    {
        Node* cur=_node;
        Node* parent=cur->_parent;
        while(parent && cur==parent->_left)
        {
          cur=parent;
          parent=parent->_parent;
        }
        _node=parent;
      }
      return *this;
    }
    Ref operator*()
    {
      return _node->_data;
    }
    Ptr operator->()                                                                                                            
    {
      return &_node->_data;
    }
    bool operator==(const self& it)
    {
      return _node == it._node;
    }
    bool operator!=(const self& it)
    {
      return _node != it._node;
    }
  private:
    Node* _node;                                                                                                                
};

四. 红黑树

1. 红黑树基本框架

成员变量有两个：记录该树节点个数的_size和该树的根_root。

// 树的定义                                                                                                                     
template<class Key, class ValueType, class KeyOfValue>    
class RBTree     
{    
    typedef RBTreeNode<ValueType> Node;    
  public:    
    typedef RBTreeItetator<ValueType, ValueType&, ValueType*> Iterator;    
    typedef RBTreeItetator<ValueType, const ValueType&, const ValueType*> const_Iterator;    
    RBTree()    
      :_size(0)    
      ,_root(nullptr)    
    {} 
  private:
    size_t _size;
    Node* _root;
};

关于typedef的几点说明

我们对节点类重定义为Node，后面会经常用到为了方便写才重定义的，权限为private因为我们只在类内部使用。另外我们还对迭代器进行了重定义，包括const迭代器和非const迭代器，为了可读性和写起来便捷才重定义，权限为public因为有从外部读取的需要：

如何用一棵红黑树同时实现map和set？

通过对模板参数的巧妙设计可以实现。第一个模板参数Key是节点排序和比较的唯一标识，如果是set的话key就是它自己本身存储的数据，如果是map的话key就是键值对的第一个值。第二个模板参数是map和set存储的数据，map的话是pair键值对，set的话是key。

关于Insert中插入数据的比较方式

此时红黑树的第三个参数就起作用了，它是一个仿函数，map、set各自实现一个并传递给一同颗红黑树。KeyOfValue，顾名思义就是获取ValueType中的Key，即存储数据作为比较的唯一表示。虽然map和set的对KeyOfValue实现不同，但可以完美地匹配它们自己的ValuType，当插入时统一调用这个仿函数来获取Key进行比较，这又是一种泛型编程的体现。

第一个模板参数的作用？

第二个模板参数和第三个模板参数我们都在Insert()中实用到了，传入的第一个模板参数Key有什么用呢？在Find()中就会用到第一个模板参数，我们调用Find()时传入的实参类型就是Key。

2. begin()和end()

红黑树的成员变量是整棵树的根节点，begin()要返回第一个节点的迭代器，根据中序遍历的规则往前找就是去找左子树的最左节点；end()的话就返回一个空的迭代器。最后普通对象返回普通迭代器，const对象返回const迭代器，至于对象是普通的还是const的由在我们在创建map或set对象时它们的属性来决定，因为map和set底层封装红黑树，它们的对象如果是const的话，封装的红黑树也是const的，对应返回const迭代器。

Iterator Begin()    
{    
  Node* subL=_root;    
  while(subL && subL->_left)    
  {    
    subL=subL->_left;    
  }    
  return Iterator(subL);    
}    
const_Iterator Begin() const    
{    
  Node* subL=_root;    
  while(subL && subL->_left)    
  {    
    subL=subL->_left;    
  }    
  return const_Iterator(subL);   
  }
Iterator End()
{
  return Iterator(nullptr);
}
const_Iterator End() const
{
  return const_Iterator(nullptr);
}

3. empty()和size()

红黑树除了根节点外还有一个记录当前节点数的成员变量_size。

empty()的话就是判断_size是否等于0。

size()的话直接返回_size的值就行。

size_t Size() const 
{
  return _size;
}
bool Empty() const 
{
  return _size == 0;
}

4. Insert 和 Find

这些都是红黑树的基本操作，没有什么太多特别的和与其他类相关联的东西，相关代码放到下面的完整代码里。一定要说的话就是他们的返回值：

Insert返回一个pair键值对，它的first为节点的迭代器，second为布尔值。如果插入成功first为新插入节点的迭代器，second为true；如果插入失败（要插入的Key已经存在），此时pair的first为那个已经存在的节点的迭代器，second为false。
Find返回一个迭代器，如果找到了返回该节点的迭代器，找不到返回空迭代器，即end()

5. 红黑树完整代码

// 红黑树的定义
template<class Key, class ValueType, class KeyOfValue>
class RBTree 
{
    typedef RBTreeNode<ValueType> Node;
  public:
    typedef RBTreeItetator<ValueType, ValueType&, ValueType*> Iterator;
    typedef RBTreeItetator<ValueType, const ValueType&, const ValueType*> const_Iterator;
    RBTree()
      :_size(0)
      ,_root(nullptr)
    {}
    Iterator Begin()
    {
      Node* subL=_root;
      while(subL && subL->_left)
      {
        subL=subL->_left;
      }
      return Iterator(subL);
    }
    const_Iterator Begin() const
    {
      Node* subL=_root;
      while(subL && subL->_left)
      {
        subL=subL->_left;
      }
      return const_Iterator(subL);
    }
    Iterator End()
    {
      return Iterator(nullptr);
    }
    const_Iterator End() const
    {
      return const_Iterator(nullptr);
    }
    size_t Size() const 
    {
      return _size;
    }
    bool Empty() const 
    {
      return _size == 0;
    }
    // 插入一个节点
    pair<Iterator, bool> Insert(const ValueType& data)
    {
      // 第一步：按搜索树规则插入一个节点
      // 1、空树的话插入节点作为根节点
      // 2、不空的话，按搜索树规则找到插入的位置，然后插入
      if(!_root)
      {
        _root=new Node(data);
        _root->_color=BLACK;
        ++_size;
        return make_pair(Iterator(_root), true);
      }
      // 寻找插入的位置
      KeyOfValue kov;
      Node* parent=nullptr;
      Node* cur=_root;
      while(cur)
      {
        parent=cur;
        if(kov(cur->_data) == kov(data))
        {
          return make_pair(Iterator(cur), false);
        }
        else if(kov(cur->_data) < kov(data))
        {
          cur=cur->_right;
        }
        else if(kov(cur->_data) > kov(data))
        {
          cur=cur->_left;
        }
      }
      // 找到后插入
      Node* newNode=new Node(data);
      newNode->_parent=parent;
      if(kov(parent->_data) > kov(data))
      {
        parent->_left=newNode;
      }
      else if(kov(parent->_data) < kov(data)) 
      {
        parent->_right=newNode;
      }
      // 第二步：调整节点的颜色
      // 1、如果父亲颜色为黑就不用调整
      // 2、如果父亲节点颜色为红，调整方式由叔叔决定
      //    a、叔叔存在且为红 --> 把叔叔和父亲的颜色调整为黑，爷爷颜色调整为红，然后继续往上调整
      //    b、叔叔不存在或存在且为黑 --> 看爷爷、父亲、和cur的相对位置来决定用什么旋转，旋转后调整父亲和爷爷的颜色
      cur=newNode;
      while(parent &&  parent->_color == RED)
      {
        // 既然进来了这个循环内部，说明父亲一定是红色，那么一定有爷爷且爷爷颜色为黑
        Node* grandfather = parent->_parent;
        // 确定叔叔的位置
        if(grandfather->_left == parent)
        {
          Node* uncle=grandfather->_right;
          if(uncle && uncle->_color == RED)// 叔叔存在且为红
          {
            parent->_color=uncle->_color=BLACK;
            grandfather->_color=RED;
            cur=grandfather;
            parent=cur->_parent;
          }
          else // 叔叔不存在或者存在且为黑
          {
            if(cur == parent->_right)
            {
              RotateL(parent);
              std::swap(parent,cur);
            }
            RotateR(grandfather);
            parent->_color=BLACK;
            grandfather->_color=RED;
            break;
          }
        }
        else if(grandfather->_right == parent)
        {
          Node* uncle=grandfather->_left;
          if(uncle && uncle->_color==RED)// 叔叔存在且为红
          {
            uncle->_color=parent->_color=BLACK;
            grandfather->_color=RED;
            cur=grandfather;
            parent=cur->_parent;
          }
          else // 叔叔不存在或存在且为黑
          {
            if(cur == parent->_left)
            {
              RotateR(parent);
              std::swap(parent,cur);
            }
            RotateL(grandfather);
            parent->_color=BLACK;
            grandfather->_color=RED;
            break;
          }
        }
      }
      _root->_color=BLACK;
      ++_size;
      return make_pair(Iterator(newNode), true); 
    }
    KeyOfValue kov;
   Iterator Find(const Key& k)
   {
     Node* cur=_root;
     while(cur)
     {
       if(kov(cur->_data) > k)
       {
         cur=cur->_left;
       }
       else if(kov(cur->_data) < k)
       {
         cur=cur->_right;
       }
       else 
       {
         return Iterator(cur);
       }
     }
     return Iterator(nullptr);
   }
   const_Iterator Find(const Key& k) const
   {
     Node* cur=_root;
     while(cur)
     {
       if(kov(cur->_data) > k)
       {
         cur=cur->_left;
       }
       else if(kov(cur->_data) < k)
       {
         cur=cur->_right;
       }
       else 
       {
         return const_Iterator(cur);
       }
     }
     return const_Iterator(nullptr);
    }
 private:
    // 左单旋
    void RotateL(Node* parent)
    {
      Node* subR=parent->_right;
      Node* subRL=subR->_left;
      parent->_right=subRL;
      if(subRL != nullptr)
      {
        subRL->_parent=parent;
      }
      subR->_left=parent;
      Node* pparent=parent->_parent;
      parent->_parent=subR;
      if(pparent == nullptr)
      {
        _root=subR;
        subR->_parent=nullptr;
      }
      else 
      {
        subR->_parent=pparent;
        if(pparent->_left == parent)
        {
          pparent->_left=subR;
        }
        else if(pparent->_right == parent)
        {
          pparent->_right=subR;
        }
      }
    }
    // 右单旋
    void RotateR(Node* parent)
    {
      Node* subL=parent->_left;
      Node* subLR=subL->_right;
      parent->_left=subLR;
      if(subLR != nullptr)
      {
        subLR->_parent=parent;
      }
      subL->_right=parent;
      Node* pparent=parent->_parent;
      parent->_parent=subL;
      if(pparent == nullptr)
      {
        _root=subL;
        subL->_parent=nullptr;
      }
      else 
      {
        subL->_parent=pparent;
        if(pparent->_left == parent)
        {
          pparent->_left=subL;
        }
        else if(pparent->_right == parent) 
        {
          pparent->_right=subL;
        }
      }
    }
    size_t _size;
    Node* _root;
};

五. map和set

1. map、set的基本框架

它们两个的成员变量都是一颗红黑树，并且都自己实现仿函数KeyOfValue。不同点在于模板参数不同，map因为存储键值对所以有两个模板参数；set只有一个模板参数Key。

// map的基本框架
template<class K, class V>    
class MyMap    
{    
    typedef pair<K, V> ValueType;    
    struct KeyOfValue     
    {    
      const K& operator()(const ValueType& v)    
      {    
        return v.first;    
      }    
    }    
  private:    
    RBTree<K, ValueType, KeyOfValue> _t;    
};  
// set的基本框架
template<class K>                                                                                                             
class MySet          
{                    
    typedef K ValueType;      
    struct KeyOfValue      
    {                  
      const K& operator()(const ValueType& k)      
      {                                        
        return k;      
      }            
    };    
  private:             
    RBTree<K, ValueType, KeyOfValue> _t;    
 };

2. map、set和红黑树之间的关系

map、set都有的接口包括begin()、end()、empty()、size()、Find、Insert等等，看到上面这些接口有没有觉得很熟悉？没错，这些都是上面红黑树已经实现了的接口，map和set因为底层是红黑树所以可以直接调用这些接口，至于有多直接，从它们两个的完整代码里可见一斑。

map和set相当于红黑树的的一件衣服，对内把红黑树装饰和保护了起来，对外使得使用者操作红黑树更加方便、容易理解。

3. map、set完整代码

map

这里要注意一下 [ ] 这个操作符的重载，这是map独有的，底层通过封装Insert实现。方括号内我们传入Key，如果存在的话返回Value的引用；如果不存在，则新插入这个节点，它的Value为对应类型的一个匿名对象，调用其默认构造函数。即该操作符的功能是无论如何都返回给你对应key的value。

template<class K, class V>
class MyMap
{
    typedef pair<K, V> ValueType;
    struct KeyOfValue 
    {
      const K& operator()(const ValueType& v)
      {
        return v.first;
      }
    };
  public:
    typedef typename RBTree<K, ValueType, KeyOfValue>::Iterator Iterator;
    typedef typename RBTree<K, ValueType, KeyOfValue>::const_Iterator const_Iterator;
    pair<Iterator, bool> Insert(const ValueType& v)
    {
      return _t.Insert(v);
    }
    Iterator Begin()
    {
      return _t.Begin();
    }
    const_Iterator Begin() const
    {
      return _t.Begin();
    }
    Iterator End()
    {
      return  _t.End();
    }
    const_Iterator End() const
    {
      return  _t.End();
    }
    size_t Size() const
    {
      return _t.Size();
    }
    bool Empty() const
    {
      return  _t.Empty();
    }
    Iterator Find(const K& k)
    {
      return _t.Find(k); 
    }
    const_Iterator Find(const K& k) const
    {
      return _t.Find(k); 
    }
    V& operator[](const K& k)
    {
      pair<Iterator, bool> ret=_t.Insert(make_pair(k, V()));
      return ret.first->second; 
    }
  private:
    RBTree<K, ValueType, KeyOfValue> _t;
};

set

template<class K>
class MySet
{
  typedef K ValueType;
  struct KeyOfValue
  {
    const K& operator()(const ValueType& k)
    {
      return k;
    }
  };
  public:
    typedef typename RBTree<K, ValueType, KeyOfValue>::Iterator Iterator;
    typedef typename RBTree<K, ValueType, KeyOfValue>::const_Iterator const_Iterator;
    pair<Iterator, bool> Insert(const ValueType& k)
    {
       return _t.Insert(k);
    }
    Iterator Begin()
    {
      return _t.Begin();
    }
    const_Iterator Begin() const
    {
      return _t.Begin();
    }
    Iterator End()  
    {
      return _t.End();
    }
    const_Iterator End() const 
    {
      return _t.End();
    }
    bool Empty() const 
    {
      return _t.Empty();
    }
    size_t Size() const 
    {
      return _t.Size();
    }
    Iterator Find(const K& k)
    {
      return _t.Find(k);
    }
    const_Iterator Find(const K& k) const
    {
      return _t.Find(k);
    }
  private:
    RBTree<K, ValueType, KeyOfValue> _t;
};

【C++】map、set模拟实现