1.map和set成员
其实在源码中map和set都是依托于红黑树来实现的，也就是说map和set的一切功能，都其实是在红黑树里面操作的，所以大家模拟实先得map和set其实他的成员列表里面，只有一个成员，那就是一颗红黑树。
2.map和set的模板
我们知道，map和set是不同的容器，而且map是一种键值对的容器，而set之时一个存储单个资料的容器，可是c++为了让map和set使用同一种方法的红黑树，引入了模板，当我们传入的是map的模板，红黑树就实例化为map的红黑树，当我们传入的是set的模板时，红黑树就实例化为set的红黑树，所以因为模板，一份同样代码的红黑树，能同时为两个不同的容器服务。
与大家的平常的认知不同的时，map传入的模板并不是
pair<k,v>的类型，同样set传入的也不是k,类型，map的实际模板是
pair<k,pair<k,v>>的键值对
set的实际模板是
pair<k,k>的键值对。
对你没有看错，两个传入的都是键值对，这样做的好处是，因为红黑树的节点里面存储的数据类型是不一样的，为了建立泛型，既能存储map的pair，又能存储set的k，于是干脆，让map和set都传入第二个类型给节点，这样就是建立了泛型编程。
3.map和set红黑树的节点
原来我们单独的红黑树的节点类型设置为pair，但是这里既可能是pair，有可能是看，所以这里我么套用模板。加上之前的节点的四要素，左孩子，右孩子，父亲节点，以及颜色，那么此时就完成了新的红黑树节点包装：
4.仿函数在map和set的应用
大家知道map和set的底层是红黑树，因为我们这里引入了模板，所以红黑树的实现同样得作调整。比如插入接口的实现，我们之前的插入接口是插入pair类型的数据，比较各个节点的大小，同样只需要比较pair的first即可，只是此时我们红黑树节点存储数据类型是模板T，假如是map调用,T,就是键值对，比较第一个值即可，但是若是是set调用,T就是单纯地k,我们只用比较k本身即可
所以怎样达成，不同类型调用data用不同地方法比较呢？
类似于优先级队列地实现，我们不妨引入一个仿函数，map构建map的仿函数，用来重载->符号获得第二个值；set实现set的仿函数用来重载->符号获得k本身即可。
这样我们不同的类别调用就实例化为红黑树，也就有不同的比较方式。
map仿函数：
set仿函数：
应用：
5.map和set的迭代器
指针，因此我们就需要为节点的指针封装为一个迭代器，重载它的各种运算符，使他的可能返回各自的值，同样因为既有const迭代器，又有普通迭代器，因此这里我们需要新的模板：就是map和set的迭代器同list的迭代器极为相似，基于两者存储的都是节点，不
//构造一个迭代器
template<class T,class Ptr,class Ref>
当ptr和ref被实例化为const，那么它就是一个const迭代器的封装。（这里和list的封装很相似。不在过多赘述）
一些重载函数：就是下面
6.map和set的迭代器++和–
我们知道一个迭代器的++或者–，就是指向，下一个和他相邻的节点，然而这里的底层确实一颗红黑树，我们应该怎么准确找到每个节点的相邻节点呢？
如图所示，就是一个红黑树，那么1节点的迭代器++,后应该指向的是节点6，6的迭代器++后指向的是节点8，对此大家不妨总结一下规律：因为底层是二叉搜索树，因而一定是满足左<根<右的规律，所以，倘若从1开始，下一个比他大的节点一定是，自己右子树的最大节点，上图中是6，**而6的话他的下一个一定是孩子是父亲左孩子的祖先，**如图1是8的左孩子，所以8一定是6的下一个节点。
减减和加加相反，就是找到这棵树中比自己小的上一个节点，也就是说找自己左子树的最大值即可，周到最大值后，就因该找，父亲右孩子的祖先就是孩子如6的iterator减减后就是1的iterator。
7.map和set的插入封装
如果不在就插入，bool设置为true,如果在就返回当前在的节点，然后bool设置为fasle，所以关于红黑树的插入我们别的就不用重新写，只用再写一遍返回值即可：就是map和set的insert在源码中的返回值就是pair<iterator,bool>类型的，意思
注意：
这样的：就是大家pair返回的迭代器是普通的迭代器，而set的迭代器
肯定编不过的，因此大家有必要专门为迭代器在写出一份构造函数，使之能够将普通迭代器拷贝构造给const迭代器：就是就是是说set的迭代器底层只有const迭代器，然而我们的insert迭代器用的是普通迭代器，所以你编译的时候
8.总结
问题。就是map和set的封装的难点就在于泛型思想在红黑树的体现，同时迭代器的复用，也是难点然而只要之气list的迭代器器封装掌握了，这里也不