map和set的封装-阿里云开发者社区

一、前言

在标准库中map和set的底层结构是使用红黑树来实现的。但是，map是key，value类型的容器，set是key类型的容器，那我们是不是要分别写一个 kv类型的红黑树和key类型的红黑树去分别封装呢？还是说可以使用同一棵树去实现呢？

下面我们从标准库源码去看一看它是怎么封装的。

二、标准源码分析

我们直接上源码

从上面的源码中，我们看出：

1、set 和 map 的红黑树结构都有两个模板参数：key_type 和 value_type。

2、set 的红黑树结构的 key_type 和 value_type的本质都是key。

3、map 的红黑树结构的 key_type 和 value_type 分别是 key 和 pair。

* 而红黑树结点所存数据类型是由模板参数 value 来控制的。即通过vlaue 我们可以知道红黑树存储的是key类型的set，还是pair类型的map。

即一棵泛型结构的红黑树，通过不同实例化参数，实现出了map和set。

三、泛型红黑树

1、结点

为了实现结点的泛型，我们可以直接使用一个模板参数T，这样T既可以是key类型，也可以是pair<key, value>的类型。至于它存储的数据到底是哪种类型，我们可以在set和map的封装中通过去传参数来确定。

enum Colour
{
  RED,
  BLACK
};
template<class T>
struct RBTreeNode
{
  RBTreeNode<T>* _left;
  RBTreeNode<T>* _right;
  RBTreeNode<T>* _parent;
  //pair<K, V> _kv;
  T _data;
  Colour _col;
  RBTreeNode(const T& data, Colour col = RED)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _data(data)
    , _col(col)
  {}
};

2、红黑树框架

对于T模板参数可能是键值Key，也可能是由Key和Value共同构成的键值对。

template<class K, class T>
struct RBTree
{
    typedef RBTreeNode<T> Node;
private:
    Node* _root = nullptr;
}

3、set框架

如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key。

template<class K>
class set
{
  private:
    RBTree<K,K> _t;
};

4、map框架

如果是map容器，传入底层红黑树的模板参数就是Key和Key和value的键值对。

class map
{
private:
    RBTree<K, pair<K,V>> _t;
};

四、仿函数

红黑树变成泛型后就出现了一个问题：插入的时候data的大小如何去进行比较呢？我们并不知道是什么类型，是key，还是pair的比较，而我们刚开始kv结构就直接用kv.first去比较了。但是现在我们并不能确定它到底是哪种类型。对于set是Key，可以比较，对于map是pair，那我们要取其中的first来比较。

那么这里，我们就需要一个仿函数来帮助我们解决这个问题了。所以正确的红黑树框架如下：

template<class K, class T, class KeyOfT>
struct RBTree
{
  typedef RBTreeNode<T> Node;
private:
  Node* _root = nullptr;
};

其中第三个模板参数就是我们要自己实现的一个仿函数。

template<class K>
class set
{
  struct SetKeyOfT
  {
    const K& operator()(const K& key)
    {
      return key;
    }
  };
public:
private:
  RBTree<K, K, SetKeyOfT> _t;
};

template<class K, class V>
class map
{
  struct MapKeyOfT
  {
    const K& operator()(const pair<K,V>& kv)
    {
      return kv.first;
    }
    };
public：
private:
  RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

因此我们红黑树的插入的查找部分就可以使用仿函数来实现。

KeyOfT kot;
      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);
    Node* newnode = cur;
    if (kot(parent->_data) > kot(data))
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;

五、迭代器

迭代器的定义：

template<class T, class Ref, class Ptr>
struct __RBIterator
{
  typedef RBTreeNode<T> Node;
  typedef __RBIterator<T, Ref, Ptr> RBIterator;
  Node* _node;
  __RBIterator(const Node*& node)
    :_node(node)
  {}
}

解引用操作，返回对应结点数据的引用

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

成员访问操作符，返回结点数据的引用

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

等于和不等于

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

++的重载

1、右子树不为空，++就是找右子树中序第一个（最左节点）

2、右子树为空，++找孩子是父亲左的那个祖先。

Self& operator++()
  {
    if (_node->_right)
    {
      Node* left = _node->_right;
      while (left->_left)
      {
        left = left->_left;
      }
      _node = left;
    }
    else
    {
      Node* parent = _node->_parent;
      Node* cur = _node;
      while (parent && cur == parent->_right)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }

--的重载

对于–，如果是根，–就是左子树，找到左子树最大的那一个（最右节点）

1、如果节点的左子树不为空，--找左子树最右的节点。

2、如果节点的左子树为空，--找祖先（孩子是父亲的右的祖先）。

Self& operator--()
  {
    if (_node->_left)
    {
      Node* max = _node->_left;
      while (max->_right)
      {
        max = max->_right;
      }
      _node = max;
    }
    else
    {
      Node* cur = _node;
      Node* parent = cur->_parent;
      while (parent&&cur==parent->_left)
      {
        cur = cur->_parent;
        parent = parent->_parent;
      }
      _node = parent;
    }
    return *this;
  }

有了上面的迭代器模板，我们就可以实现红黑树的迭代器了

template<class K, class T,class KeyOfT>
class RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef __RBTreeIterator<T> iterator;
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
}；

六、红黑树代码

template<class K, class T, class KeyOfT>
struct RBTree
{
  typedef RBTreeNode<T> Node;
public:
  typedef _RBIterator<T, T&, T*> iterator;
  typedef _RBIterator<T, const T&, const T*> const_iterator;
  iterator begin()
  {
    Node* left = _root;
    while (left && left->_left)
    {
      left = left->_left;
    }
    return iterator(left);
  }
  iterator end()
  {
    return iterator(nullptr);
  }
  pair<iterator, bool> insert(const T& data)
  {
    KeyOfT kot;
    if (_root == nullptr)
    {
      _root = new Node(data);
      _root->_col = BLACK;
      return 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 make_pair(iterator(cur), false);
      }
    }
    cur = new Node(data);
    Node* newnode = cur;
    if (kot(parent->_data) > kot(data))
    {
      parent->_left = cur;
    }
    else
    {
      parent->_right = cur;
    }
    cur->_parent = parent;
    while (parent && parent->_col == RED)
    {
      Node* grandfather = parent->_parent;
      assert(grandfather);
      assert(grandfather->_col == BLACK);
      if (parent == grandfather->_left)
      {
        Node* uncle = grandfather->_right;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        // uncle 不存在 + 存在且为黑
        else
        {
          if (cur == parent->_left)
          {
            RotateR(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
        if (uncle && uncle->_col == RED)
        {
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          //继续往上处理
          cur = grandfather;
          parent = cur->_parent;
        }
        else
        {
          if (cur == parent->_right)
          {
            RotateL(grandfather);
            parent->_col = BLACK;
            grandfather->_col = RED;
          }
          else
          {
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK;
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
  }
private:
  void RotateL(Node* parent) //左单旋
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* pparent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    if (parent == _root)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subR;
      else
        pparent->_right = subR;
      subR->_parent = pparent;
    }
  }
  void RotateR(Node* parent) //右单旋
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* pparent = parent->_parent;
    parent->_parent = subL;
    subL->_right = parent;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    if (parent == _root)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (pparent->_left == parent)
        pparent->_left = subL;
      else
        pparent->_right = subL;
      subL->_parent = pparent;
    }
  }
private:
  Node* _root = nullptr;
};

七、set的封装

#pragma once
#include"RBTree.h"
namespace zdl
{
  template<class K>
  class set
  {
    struct SetKeyOfT
    {
      const K& operator()(const K& key)
      {
        return key;
      }
    };
  public:
        //typename:没有实例化的模板，区分不了是静态变量还是类型，typename告诉编译器是类型
    typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
    iterator begin()
    {
      _t.begin();
    }
    iterator end()
    {
      _t.end();
    }
    pair<iterator, bool> insert(const K& key)
    {
      return _t.insert(key);
    }
  private:
    RBTree<K, K, SetKeyOfT> _t;
  };
}

八、map的封装

#pragma once
#include"RBTree.h"
namespace zdl
{
  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<K, V>, MapKeyOfT>::iterator iterator;
    iterator begin()
    {
      _t.begin();
    }
    iterator end()
    {
      _t.end();
    }
    pair<iterator, bool> insert(const pair<K, V>& kv)
    {
      return _t.insert(kv);
    }
    V& operator[](const K& key)const
    {
      pair<iterator, bool> ret = insert(make_pair(K, V()));
      return ret.first->second;
    }
  private:
    RBTree<K, pair<K, V>, MapKeyOfT> _t;
  };
}

map和set的封装