set的作用：判断某⼀个元素是不是在⼀个组⾥⾯

map的作用：映射，相当于字典，把⼀个值映射成另⼀个值，可以创建字典

首先要了解map和set常用的操作，对于stl容器，无非就是增删查改，但对于map/set来说，是不能修改的，因为红黑树的底层实现决定

红黑树存储值的类型是value_type,而value_type定义是：

 typedef pair<const Key, T> value_type;   //value_type的定义

对于一个map容器，每次插入、删除或者查找返回的迭代器，其指向的红黑树中node节点，对其iterator->，解出的值的类型是value_type，这是一个pair的包装类，这个，我们定义了它的Key为const Key,而其值的类型为T，这样对于每次返回的迭代器，我们就可以实现，其中Key为const类型不能修改，对于实值不是const,可以修改。

（实值也就是map的value）删除和插入是可行的，查也是可行的，这样其实就可以找出常用的几个接口：

pair<iterator,bool> insert (const value_type& val)   iterator代表新插入元素的位置，bool代表释放插入成功

iterator  erase (const_iterator position) 

iterator find (const value_type& val) const;

还要注意的是operator[]这个只有map支持，set是不支持的，这里需要注意的一点时：当使用operator[]时，如果key不存在，operator[]用默认的value与key构造键值对然后插入，返回改默认value的引用。

operator[]的原理是：  用构造一个键值对，然后调用insert()函数将该键值对插入到map中  如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器  如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器  operator[]函数最后将insert返回值键值对中的value返回

第二点就是其底层原理，两者的底层都是红黑树（平衡搜索树），导致容器中的元素是一个有序的序列，并且能够按照其内部比较对象所指示的特定排序准则进行排序，记住set的底层是<value,value>组成的键值对，不是单单的value值，但在使用的时候可以只插入value，其中排序准则通过仿函数实现，默认是小于排序，set和map的查询时间复杂度是logn

面试问题来了：

一个类型要做map和set的K有什么要求？

支持比较大小，因为底层是搜索树

map和set的特点是什么？

查找logN，遍历时按照key排序，去重，插入和删除都是logN

那么multi版本的set和map有什么特点？

multiset的key也不能被修改，因为底层也是红黑树，唯一不同就在于key是可以重复的

multimap为什么不支持operator[]操作呢？key重复！

这里底层原理一定会问到红黑树

所以也一定要知道什么是红黑树

这就要从数据结构中的二叉搜索树说起了，二叉搜索树的概念要辨析清楚，红黑树是一种改良版的二叉搜索树，在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路 径会比其他路径长出俩倍，因而是接近平衡的。

红黑树性质也应该知道：

1. 每个结点不是红色就是黑色

2. 根节点是黑色的 

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的 

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

这里又有问题，为什么默认节点是红色的？不是黑色的？

红色能够使对二叉树上述规则影响最小，如果是黑色的话，每次插入都一定会违反第四条