前言
set和map都是关联式容器，stl中树形结构的有四种，set，map，multiset,multimap.本次主要是讲他们的模拟实现和用法。
一、set、map、multiset、multimap
set
set的中文意思是集合，集合就说明不允许重复的元素
1…set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用红黑树来实现的
6. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。这个后面模拟实现会讲原因。
6. 使用set的迭代器遍历set中的元素，可以得到有序序列
7. set中的元素默认按照小于来比较
8.set中的元素不可以重复，所以可以用set来去重
9.set中的迭代器是双向迭代器
T是key，Compare是仿函数来控制比较规则，Alloc是空间配置器
构造函数没什么可说的，看一眼就懂了，这里的T有很大意义，后面模拟会提到。
重要函数
画横线的就是比较重要的，有几个注意事项：
1.关于insert，库里面的insert是提供迭代器位置插入的，这样做的目的有两个：
1.与其他stl的insert保持一致，比如vector，list都提供迭代器插入
2.看下面的emplace_hint，emplace版本的构造一般是直接在容器内部构造，而emplace_hint对应的版本就是迭代器位置插入，hint是提示，若pos指向的位置恰好是元素应插入的位置或邻近位置（如插入有序序列时，pos指向当前最后一个元素），红黑树可直接从pos开始验证，跳过大部分查找步骤，插入效率接近 O (1)；即使pos是错误提示，set 仍会按正常逻辑查找正确位置（退化至 O (log n)），但不会破坏元素的有序性
2.count就是计数，set里一定是一，这个接口是给multi版本使用的
3.lower_bound是大于等于元素的位置，upper_bound是大于元素的位置，这样是为了维护迭代器左闭右开的性质
map
1… map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为红黑树
第二个参数给的是T而不是Value，这里也有很大意义，后面模拟实现会提到，其他和set一样。
重要函数
map的重要接口和set类似，只多了比较重要的[] 和 at，都是通过key返回value的引用,他们的实现都得益于insert
[]功能很强大，支持修改，插入、插入 + 修改
int main()
{
map<int, int> mp;
mp.insert({ 0,1 });
mp[0] = 2;
mp[2];
mp[3] = 3;
return 0;
}
[]的实现实际上是这样,模拟实现还需要使用
V& operator[](const K& key)
{
pair<K,V> pr = make_pair(key,V());
iterator it = insert(pr).first;
return *it.second;
}
multi系列
multi中文意思是多重，就意味着允许键值对冗余，也就是key可以重复。
count的作用是给他的，如果想使用可以重复的集合就用multiset
multimap中没有提供[],因为key是可以重复的，那我该返回哪个呢？所以就不提供
二、模拟实现
set和map的使用都比较简单，主要还是在模拟上。
框架
第一个问题就来了，一个是key模型，一个是key-value模型，难道要写成两份代码吗？之前list的迭代器提到了，其实库里面很杜绝这种相似代码写两份的，我们看看库里是怎么解决的，其实上面提供了一点消息就是T
都搞成了两个参数<K,T>,其中T对于set就是K，对于map就是pair< K,V> ,这样就可以通过一份代码来实现set和map，先搭一个框架，节点存放的就是T类型了
template<class T>
struct RBTreeNode {
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color color;
T _kv;
RBTreeNode(const T& p)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,color(Color::RED)
,_kv(p)
{}
};
template<class K,class T>
class RBTree {
typedef RBTreeNode<T> Node;
private:
Node* _root;
}
set里面放的就是RBTree<K, K> _t;
map里面就是RBTree<K,pair<K, V> _t;
到了插入，又出现新问题了，现在insert能跑了吗？bool insert(const T& p)传的是T啊，对于set倒是能比大小，map呢？pair有一套自己的比较大小的规则，但是和实际插入的规则不同啊，所以还需要一个参数KofT，取出T中的K
map:
struct mapKOfT {
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
private:
RBTree<K,pair<K, V>,mapKOfT> _t;
set:
struct SetKOfT {
const K& operator()(const K& kv)
{
return kv;
}
};
RBTree<K, K, SetKOfT> _t;
insert就会变成KOfT koft;涉及到比大小都用koft套一层
到目前为止，基本的框架已经完事了。下一步，迭代器
迭代器
先看库里的迭代器怎么玩的
set为什么要这么搞呢？因为set本身就不支持任何的修改，所以set这两个都是const_iterator
但是对于map，map的value要支持修改，key不支持，所以不能搞成const，那他的key怎么防止修改呢？这个后面提，其实第一张图片已经看到了。
主要还是++ – begin end怎么实现：
迭代器架子很好搭建，因为有了list的基础
框架
template<class T,class Ref,class Ptr>
struct RBTree_Iterator
{
typedef RBTreeNode<T> Node;
typedef RBTree_Iterator<T, Ref, Ptr> Self;
Node* _node;
RBTree_Iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_kv;
}
Ptr operator->()
{
return &_node->_kv;
}
Self& operator--(){}
Self operator--(int){}
Self operator++(int){}
bool operator!=(const Self& ot)const
{
return _node != ot._node;
}
bool operator==(const Self& ot)const
{
return _node == ot._node;
}
};
红黑树里面：
typedef RBTree_Iterator<T, T&, T*> iterator;
typedef RBTree_Iterator<T, const T&, const T*> const_iterator;
关于begin end ++ 和 - -
迭代器区间是左闭右开，begin就是最小元素，end呢，可以给空吗？不可以，因为要支持–end()走到上一个元素，库里的实现是搞了个类似哨兵位头节点的东西。
这个头节点，左孩子是最小节点也就是begin(),右孩子是最大节点，
头节点的父亲是根，根的父亲是头节点
但是这样维护起来比较麻烦，模拟实现只是为了了解底层，造不出更好的。所以这里不使用头节点方式，end就按空节点来存放（但实际上不是这样）
begin
begin其实就是找到最左节点返回就可以
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left) cur = cur->_left;//考虑cur主要是考虑这是一颗空树的问题
return iterator(cur);
}
++ 和 - -
上代码：
Self& operator--()
{
Node* nodeleft = _node->_left;
if (nodeleft)
{
while (nodeleft->_right) nodeleft = nodeleft->_right;
_node = nodeleft;
return *this;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
return *this;
}
}
Self operator--(int)
{
Node* tmp(_node);
--(*this);
return RBTree_Iterator(tmp);
}
Self& operator++()
{
Node* noderight = _node->_right;
if (noderight)
{
while (noderight->_left) noderight = noderight->_left;
_node = noderight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//父亲有可能会为空，比如三角形结点的树
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
//如果父亲是空，说明这棵树已经遍历完全了
//如果父亲不是空，正常父亲给Node
_node = parent;
}
return *this;
}
Self operator++(int)
{
Self tmp(_node);
++(*this);
return tmp;
}
此时基本上红黑树里面的迭代器基本完全了，实现map和set
注意：这里不加typename编译不通过，原因：
类模板没有被实例化，没有生成具体代码，编译器不敢去里面找iterator
都没有检查代码错误，取到的有可能是内部类或者静态成员变量或者类型，加上typename就是告诉他是类型
//set:
typedef typename RBTree<K, K, SetKOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKOfT>::const_iterator const_iterator;
//map:
typedef typename RBTree<K, pair<K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, mapKOfT>::const_iterator const_iterator;
对于set的begin、end 和 cbegin、cend接口，const版本正常写，这里如果再写一个非const版本的会报错误，因为既然是非const，this指针会调用红黑树里非const版本的begin，返回非const迭代器，此时无法传给set里的const迭代器，所以只需要实现一个。
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}
对于map的begin、end系列正常就可以了
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
set、map防止修改
刚才已经讲了，set防止修改的方式就是迭代器都是const迭代器
那map呢？map不想让key修改，可以让value修改，来看库里的实现
他把那个T里面的key都换成了const key，我们也这么实现。
有的人会有疑问？那我map<const int ,int> mp;不是有两个const吗？不会报错吗？
不会，C++对重复的const编译器会进行优化成一个const。
typedef typename RBTree<K, pair<const K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, mapKOfT>::const_iterator const_iterator;
RBTree<K,pair<const K, V>,mapKOfT> _t;
这样map就做到了不能修改K但是可以修改V的效果。
map的【】实现
上面说了，第一件事就是改insert的返回值，主要就是改return的地方，搞成一个pair就可以了
pair<iterator,bool> insert(const T& p)
{
KOfT koft;
if (_root == nullptr)
{
_root = new Node(p);
_root->color = Color::BLACK;
return make_pair(iterator(_root),true);
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//用T了之后还有点问题 set是K，map是pair<k,v>怎么比？
//再传一个模板用来取出key即可
if (koft(cur->_kv) < koft(p))
{
parent = cur;
cur = cur->_right;
}
else if (koft(cur->_kv) > koft(p))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);
}
}
cur = new Node(p);
Node* newnode = cur;
if (koft(parent->_kv) < koft(p))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//这之前都是搜索树的逻辑
//
while (parent && parent->color == Color::RED)
{
Node* grandf = parent->_parent;
if (grandf->_left == parent)
{
Node* uncle = grandf->_right;
//叔叔存在且为红
if (uncle && uncle->color == Color::RED)
{
//判断
uncle->color = parent->color = Color::BLACK;
grandf->color = Color::RED;
//继续判断
cur = grandf;
parent = cur->_parent;
}
//叔叔不存在或者为黑
else
{
//开旋
//
if (parent->_left == cur)
{
RotateRight(grandf);
parent->color = Color::BLACK;
grandf->color = Color::RED;
}
else
{
//parent->right 是cur，grandf的左边是parent
RotateLeft(parent);
RotateRight(grandf);
cur->color = Color::BLACK;
grandf->color = Color::RED;
}
}
}
//祖父的右边是父亲
else
{
Node* uncle = grandf->_left;
//uncle不存在 或者uncle为黑
//uncle为红
if (uncle && uncle->color == Color::RED)
{
parent->color = uncle->color = Color::BLACK;
grandf->color = Color::RED;
cur = grandf;
parent = cur->_parent;
}
//uncle为黑或者不存在
else
{
//旋转
// grandf
//uncle parent
//cur
if (cur == parent->_right)
{
RotateLeft(grandf);
parent->color = Color::BLACK;
grandf->color = Color::RED;
}
else
{
RotateRight(parent);
RotateLeft(grandf);
cur->color = Color::BLACK;
grandf->color = Color::RED;
}
}
}
}
_root->color = Color::BLACK;
return make_pair(iterator(newnode), true);
}
}
改完之后就可以实现operator[]了，一句话看着不舒服可以分开
V& operator[](const K& key)
{
return (*(insert(make_pair(key, V())).first)).second;
}
set的insert也需要跟着改。
改完之后跑了一段代码，发现set的跑不过，map的可以，为什么呢？
所以在迭代器里需要提供一个普通迭代器构造const迭代器，库里面实现的很牛。
typedef RBTree_Iterator<T, T&, T*> iterator;
RBTree_Iterator(const iterator& it)//可以拿普通迭代器构造const迭代器
:_node(it._node)
{}
搞了一个迭代器参数永远是<T,T&,T*>无论外面传进来是const迭代器还是普通迭代器这里都是普通迭代器。
对于下面这个构造函数：
1.如果是普通迭代器，相当于普通迭代器的拷贝构造
2.如果是const迭代器，相当于普通迭代器来构造const迭代器。这样就能跑了。
另外，这一块其实也是库里一直都有的设计。任何的容器都支持const迭代器给非const迭代器
list<int> lt;
list<int>::const_iterator it = lt.begin();
三、完整代码
总结
map和set的东西不少，需要好好练习和掌握。