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的封装

一、前言

二、标准源码分析

三、泛型红黑树

1、结点

2、红黑树框架

3、set框架

4、map框架

四、仿函数

五、迭代器

六、红黑树代码

七、set的封装

八、map的封装

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

map和set的封装

一、前言

二、标准源码分析

三、泛型红黑树

1、结点

2、红黑树框架

3、set框架

4、map框架

四、仿函数

五、迭代器

六、红黑树代码

七、set的封装

八、map的封装

热门文章

最新文章

相关课程

相关电子书

相关实验场景