前言：这篇文章将继续分享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>，其中K一般是不能更改的，而V是能够更改的。
二.map和set实现
由于map和set的底层都是红黑树，所以这里我们分享一种map和set共用一份红黑树代码的实现方式。
1.基本框架
首先我们要知道，map和set存储的数据类型是有区别的，前者为pair<K,V>键值对，后者为单一的数据类型K，所以对于红黑树的数据类型，我们需要做出更改：
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){}};能够看出，我们直接将数据类型改为模版T，用来替换pair<K,V>和K，数据直接用data代替。
当进行插入操作时，我们又会面临一些问题：
如果是set，当进行比较操作时直接比较K，无妨。但是如果是map，比较时则会比较pair，虽然pair类型可以进行比较，但是其底层的比较方式却与我们想要的结果不同。为了让map也进行key的比较，我们引入仿函数，通过仿函数，来获取到map中pair的key：
struct MapKeyOfT{const K& operator(const pair<K,V>& kv){return kv.first;}};struct SetKeyOfT{const K& operator(const K& key){return key;}};为了帮助map完成操作，set也同样需要一个仿函数。
由于仿函数需要创建对象使用，所以我们还需引入新的模版KeyOfT：
template<class K, class T,class KeyOfT>class RBTree{typedef RBTreeNode<T> 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) < kot(data)){parent = cur;cur = cur->_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{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:bool Insert(const K& key){return _t.Insert(key);}private:RBTree<K, K, SetKeyOfT> _t;};}#include"RBTree.h"namespace MyMapSet{template<class K,class V>class map{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:bool Insert(const pair<K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<K,V>, MapKeyOfT> _t;};}2.迭代器
那么map和set只要是C++的容器，就一定会存在迭代器，下面我们直接通过代码来分析迭代器的常用功能该如何实现。
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){}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;}完成迭代器类的实现之后，紧接着就是将其封装在红黑树类中：
template<class K, class T,class KeyOfT>class RBTree{typedef RBTreeNode<T> Node;public:typedef __RBTreeIterator<T, T&, T*> 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<K, K, SetKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}map：
public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::Iterator iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}测试如下：
最后还有一个值得关注的问题，就是set和map的key都是不能被修改的，但是我们上边的代码并不能实现：
这是不合理的，而解决的方法为：
map：
RBTree<K, pair<const K,V>, MapKeyOfT> _t;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
set：
RBTree<K, const K, SetKeyOfT> _t;
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
在封装时即将key定义为const类型，便可保证其不能被修改。
3.map重载[]
map不同于set的另外一点就在于其重载了运算符[]，可以使得map通过key来直接得到其value。
当key存在时，就返回其对应的value，不存在则会新插入该key，并返回其迭代器。
所以想要重载[]，我们还需对插入函数进行改进：
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;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;//插入后cur会变，所以提前记录cur->_col = RED;//新增节点给红色 //此处省略插入步骤 _root->_col = BLACK;return make_pair(Iterator(newnode), true);//树不为空，但不存在，返回新节点}要将插入函数的返回值改为pair类型，同时包含Iterator和bool。
此时我们便可在map中重载[]：
V& operator[](const K& key){pair<iterator, bool> ret = _t.Insert(make_pair(key,V()));return ret.first->second;}定义ret去接收返回值，其中ret.first得到的是迭代器，而迭代器中也包含data的pair类型，所以再取second即可返回value。
测试如下：
总结
关于map和set就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！