C++——map和set

前言：这篇文章将继续分享C++的两大新容器——map和set。

• 我们前边所分享的vector、list等容器，它们的底层是顺序表，链表等序列式容器，它们的作用是单纯的存储数据，数据与数据之间几乎毫无关联。
• 而接下来要分享的map和set，则是以搜索二叉树为底层的关联式容器，不仅仅可以存储数据，还可以用于快速查找数据，存储的数据与数据之间通常有很强的关联性。
• map和set的底层为搜索二叉树（红黑树）。

  ---

  目录

  一.map和set理解

  1.set

   2.map 

  二.map和set实现

  1.基本框架

  2.迭代器

  3.map重载[]

   总结

  ---

  一.map和set理解

  1.set

  set从简单的角度理解，就是一颗二叉搜索树，每个节点存放一个元素，并且不允许有相同元素的节点出现，被要求的是，节点的值不能被修改，但可以增加或删除。

  ---

   2.map 

  而map则是在set的基础上，将存储数据更替为键值对pair，其中K一般是不能更改的，而V是能够更改的。

  ---

  二.map和set实现

  由于map和set的底层都是红黑树，所以这里我们分享一种map和set共用一份红黑树代码的实现方式。

  ---

  1.基本框架

  首先我们要知道，map和set存储的数据类型是有区别的，前者为pair键值对，后者为单一的数据类型K，所以对于红黑树的数据类型，我们需要做出更改：

  templatestruct RBTreeNode{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}};

  能够看出，我们直接将数据类型改为模版T，用来替换pair和K，数据直接用data代替。 

  当进行插入操作时，我们又会面临一些问题：

  • 如果是set，当进行比较操作时直接比较K，无妨。
  • 但是如果是map，比较时则会比较pair，虽然pair类型可以进行比较，但是其底层的比较方式却与我们想要的结果不同。

    为了让map也进行key的比较，我们引入仿函数，通过仿函数，来获取到map中pair的key：

    struct MapKeyOfT{const K& operator(const pair& kv){return kv.first;}};struct SetKeyOfT{const K& operator(const K& key){return key;}};

    为了帮助map完成操作，set也同样需要一个仿函数。

    由于仿函数需要创建对象使用，所以我们还需引入新的模版KeyOfT：

    templateclass RBTree{typedef RBTreeNode Node;public://插入bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;//根给黑色return true;}KeyOfT kot;Node* parent = nullptr;Node* cur = _root;while (cur){if (kot(cur->data) _right;}else if (kot(cur->data) > kot(data)){parent = cur;cur = cur->_left;}else{return false;}}

    那么为什么我们这里还要保留模版参数K呢？？

    这是因为当使用find函数和erase等函数时，无论是map还是set，我们只需要传入K即可。

     进行数据比较时，只需调用仿函数，即可完成key的比较。

    到此，两个容器的基本框架才算完成：

    #include"RBTree.h"namespace MyMapSet{templateclass set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool Insert(const K& key){return _t.Insert(key);}private:RBTree _t;};}

    #include"RBTree.h"namespace MyMapSet{templateclass map{struct MapKeyOfT{const K& operator()(const pair& kv){return kv.first;}};public:bool Insert(const pair& kv){return _t.Insert(kv);}private:RBTree _t;};}

    ---

    2.迭代器

    那么map和set只要是C++的容器，就一定会存在迭代器，下面我们直接通过代码来分析迭代器的常用功能该如何实现。

    templatestruct __RBTreeIterator{typedef RBTreeNode Node;typedef __RBTreeIterator Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}};

    创建一个迭代器类能更好的帮助我们在红黑树类中实现迭代器功能。

    这些功能容易理解，这里就不做过多解释。

    下面我们来分析关键功能++。

     首先红黑树是二叉搜索树，其数据本质上是按升序的顺序排序，所以当使用++时，我们得到的一定是按升序的下一个数据。

    而我们已经知道，红黑树的中序遍历结果即为升序，所以在一棵同时包含父子节点的树中，其三个节点的大小顺序为：左子节点

    所以如果该节点为左子节点，那么++之后的节点就是其父节点，如果该节点为父节点，那么++之后的节点则会是其右子树的最小节点。而如果该节点为右子节点，那么就说明其为该棵同时包含父子节点的树中的最大节点，此时就要循环往上遍历，直至循环至根节点，说明此时已经为整棵树的最大节点，再++即为空。

    或者循环过程中cur节点为父节点的子节点，再++则为父节点。

    Self& operator++(){if (_node->_right)//有右子树，去找右子树的最左子节点{Node* leftMin = _node->_right;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}_node = leftMin;}else//没有右子树，则找到其父节点{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right)//如果该节点为父节点的右子树，则向上循环{cur = parent;parent = parent->_parent;}_node = parent;//直至循环至根节点，或者循环过程中cur节点为父节点的子节点}return *this;}

    完成迭代器类的实现之后，紧接着就是将其封装在红黑树类中：

    templateclass RBTree{typedef RBTreeNode Node;public:typedef __RBTreeIterator Iterator;Iterator Begin(){Node* leftMin = _root;while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return Iterator(leftMin);}Iterator End(){return Iterator(nullptr);}

     而迭代器的begin，即为整棵树的最左节点，end即为空。

    最后再将其分别封装到map和set中，即可完成迭代器的实现：

    set：

    public:typedef typename RBTree::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}

    map：

    public:typedef typename RBTree::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}

     测试如下：

    最后还有一个值得关注的问题，就是set和map的key都是不能被修改的，但是我们上边的代码并不能实现：

    这是不合理的，而解决的方法为：

    map：       

    RBTree _t;

    typedef typename RBTree::Iterator iterator;

    set：        

    RBTree _t;

    typedef typename RBTree::Iterator iterator;

    在封装时即将key定义为const类型，便可保证其不能被修改。 

    ---

    3.map重载[]

    map不同于set的另外一点就在于其重载了运算符[]，可以使得map通过key来直接得到其value。

    当key存在时，就返回其对应的value，不存在则会新插入该key，并返回其迭代器。

    所以想要重载[]，我们还需对插入函数进行改进：

    pair 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;Node* cur = _root;while (cur){if (kot(cur->_data) _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;//插入后cur会变，所以提前记录cur->_col = RED;//新增节点给红色        //此处省略插入步骤       _root->_col = BLACK;return make_pair(Iterator(newnode), true);//树不为空，但不存在，返回新节点}

    要将插入函数的返回值改为pair类型，同时包含Iterator和bool。

    此时我们便可在map中重载[]：

    V& operator[](const K& key){pair ret = _t.Insert(make_pair(key,V()));return ret.first->second;}

    定义ret去接收返回值，其中ret.first得到的是迭代器，而迭代器中也包含data的pair类型，所以再取second即可返回value。 

    测试如下：

    ---

     总结 

    关于map和set就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！