00 写在前面
【STL源码剖析】总结笔记（8）：红黑树（RB-tree）探究
这篇的内容在红黑树的基础上就显得简单很多了。set和map需要了解其结构，在实际使用STL过程中最好可以做到轻松使用。
因为是红黑树作为底层，所以要注意元素是会自动排序的。
01 set/multiset
set
set的底层是依靠红黑树来支撑的，所以会根据元素的key自动排序。对于set来说，key就是value，而且set不允许两个元素有相同的key。
同理，我们也不可以修改set的元素值，这一点可以从后面set的iterator中看出来。
set的结构如下：
template <class Key,class Compare=less<Key>,class Alloc=alloc>
class set{
public:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare Value_compare;
private:
typedef rb_tree<key_type,value_type,identity<value_type>.key_compare,Alloc>rep_type;
rep_type t;
}
重点关注这样几个点：
- key_type和Value_type都是key本身，而且key和value都是用一个Compare函数的。
- 定义了一个rep_type类型的t，而这个rep_type就是rb_tree，我们上次说过的五个参数都在这里。
- key_type和value_type都是key，下一个参数是指如何取出value中的key，这里的identity返回本身，符合set的特性。而Compare在第一行可以看到默认为递增排序。
identity的定义如下：
template<class T>
struct identity:public unary_function<T,T>{
const T& operator()(const T& x)const{return x;}
}
也就是传入自己，返回自己。
再看一下set的iterator
typedef typename rep_type::const_iterator iterator;
是rb_tree的const_iterator，也说明了不可随意改动元素值。
这样看其实set很像我们前面提到的container adapter（容器适配器），因为它的功能都是依靠红黑树实现的。
multiset
multiset允许key重复，这也是与set的区别。
而它们的底层都是依靠红黑树实现的，那是如何区分的呢？
其实就是区别在于红黑树的insert函数的使用。
set使用的是红黑树的insert_unique()，保证插入元素不重复，而multiset使用的是insert_equal()，在插入时元素可以相同。
insert_unique()在插入相同元素时不会报错，只是不能插入成功。
02 map和multimap
map
map的底层也是依靠红黑树来支撑的，所以会根据元素的key自动排序。map比较特殊的一点是所有的元素都是成对的（pair），pair包括key和value，map不允许两个元素拥有相同的key，而且iterator也不可修改key，但是可以修改value。
map的结构如下：
template <class Key,class T,class Compare=less<Key>,class Alloc=alloc>
class map{
public:
typedef key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key,T> value_type;
typedef Compare key_compare;
...
private:
typedef rb_tree<key_type,value_type,select1st<value_type>,key_compare,Alloc>rep_type;
rep_type t;
}
从上往下看需要注意：
- key和data一起组成了value
- 调用红黑树时，传入了key和value，要注意这里的value是pair
- 第三个参数是如何从value中取key，对于pair来说就是第一个参数key，所以调用了select1st返回pair的first
再来看一下iterator
typedef typename rep_type::iterator iterator;
这里的iterator并不是类似set中的const_iterator，因为允许通过iterator修改value，但是key不可修改。
所以在上面的定义中Key是const类型的。
还有一个map独有的操作符[]
T& operator[](const key_type& k){
return (*((insert(value_type(k,T()))),first)).second;
}
简单解释一下这个操作。比如有一个map是a，那么a[i]就可以传入key用来找对应的value。如果不存在，那么会插入默认值。
multimap
multimap与map的区别也和上面一样，就是允许键值重复。
map使用的是红黑树的insert_unique()，保证插入元素不重复，而multimap使用的是insert_equal()，在插入时元素可以相同。