[STL source code analysis] summary notes (9): set/multiset and map/multimap

00 Write it at the front

【STL Source analysis 】 Summary notes （8）： Red and black trees （RB-tree） To explore the
The content of this article is much simpler on the basis of red and black trees .set and map Need to understand its structure , In actual use STL In the process, it is better to use it easily .

Because red and black trees are used as the bottom layer , So notice that the elements are automatically sorted .

01 set/multiset

set

set The bottom layer of the tree is supported by red and black trees , So it will be based on the key Automatic sorting . about set Come on ,key Namely value, and set Two elements are not allowed to have the same key.

Empathy , We can't change it either set The element value of , This can be seen from the back set Of iterator I can see .

set The structure is as follows ：

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

Focus on these points ：

1. key_type and Value_type All are key In itself , and key and value It's all in one Compare Functional .
2. Defined a rep_type Type of t, And this rep_type Namely rb_tree, The five parameters we mentioned last time are all here .
3. key_type and value_type All are key, The next parameter refers to how to get value Medium key, there identity Return itself , accord with set Characteristics of . and Compare In the first line, you can see that the default is incremental sorting .

identity Is defined as follows ：

template<class T>
struct identity:public unary_function<T,T>{
    const T& operator()(const T& x)const{return x;}
}

That is to say, it is introduced into oneself , Return to yourself .

Look again. set Of iterator

typedef typename rep_type::const_iterator iterator;

yes rb_tree Of const_iterator, It also shows that the element value cannot be changed at will .

In fact set Much like what we mentioned earlier container adapter（ Container adapter ）, Because its functions are realized by red black tree .

multiset

multiset allow key repeat , This is also with set The difference between .

And their bottom layer is realized by red black tree , How to distinguish them ？

In fact, the difference lies in the red and black trees insert Use of functions .

set The red black tree is used insert_unique(), Ensure that the inserted elements are not repeated , and multiset It uses insert_equal(), The elements can be the same when inserting .

insert_unique() No error will be reported when inserting the same element , It just can't be inserted successfully .

02 map and multimap

map

map The bottom layer of the tree is also supported by red and black trees , So it will be based on the key Automatic sorting .map The special point is that all the elements are in pairs （pair）,pair Include key and value,map Two elements are not allowed to have the same key, and iterator It cannot be modified key, But it can be modified value.

map The structure is as follows ：

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

From top to bottom, you should pay attention to ：

1. key and data Together make up value
2. When calling red black tree , Into key and value, Pay attention here value yes pair
3. The third parameter is how to start from value To take key, about pair It is the first parameter key, So I called select1st return pair Of first

Let's take a look at iterator

typedef typename rep_type::iterator iterator;

there iterator It's not like set Medium const_iterator, Because it is allowed to pass iterator modify value, however key Do not modify the .

So in the above definition Key yes const Type of .

One more map Unique operator []

T& operator[](const key_type& k){
    return (*((insert(value_type(k,T()))),first)).second;
}

Explain this operation briefly . Let's say I have a map yes a, that a[i] You can bring in key To find the corresponding value. If it doesn't exist , Then the default value will be inserted .

multimap

multimap And map The difference is the same as above , Allow key value repetition .

map The red black tree is used insert_unique(), Ensure that the inserted elements are not repeated , and multimap It uses insert_equal(), The elements can be the same when inserting .