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;
}

重点关注这样几个点：

1. key_type和Value_type都是key本身，而且key和value都是用一个Compare函数的。
2. 定义了一个rep_type类型的t，而这个rep_type就是rb_tree，我们上次说过的五个参数都在这里。
3. 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;
    
}

从上往下看需要注意：

1. key和data一起组成了value
2. 调用红黑树时，传入了key和value，要注意这里的value是pair
3. 第三个参数是如何从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()，在插入时元素可以相同。