STL源码剖析（五）关联式容器--【set、multiset、map、multimap】

1. 写在前面

• 在前面我们对于RB-tree的设计与实现都有了一定的了解，那么这一节中所要解析的set以及map看起来就简单了许多，因为这两者都是以RB-tree作为其底层数据结构，大部分操作直接调用RB-tree的操作实现的，在这里就不再重复提及了，只针对set及map的性质及特有操作进行解析

2. set

2.1 set性质

1. set以RB-tree作为其底层机制
2. 所有元素都会根据元素的键值自动被排序
3. set的元素就是键值，set不允许两个元素有相同的键值
4. 不允许通过set的迭代器来改变set的元素值，因为set的元素值就是键值，更改了元素值就会影响其排列规则，如果任意更改元素值，会严重破坏set组织，因此在定义set的迭代器时被定义成了RB-tree的const_iterator
5. 由于set不允许有两个相同的键值，所以插入时采用的是RB-tree的insert_unique方式

2.2 set实现

• 以下只将set特有的一些性质通过其源码表现出来

template <class Key, class Compare = less<key>, class Alloc = allloc>
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, identify<value_type>, key_compare, Alloc> rep_type;rep_type t;      //采用红黑树来表现set
public://...typedef typename  rep_type::const_iterator iterator;  //定义为const_iterator，不允许更改//...//以下列举出的构造函数与插入均使用insert_unique方式template <class InputIterator>set(InputIterator first, InputIterator lst): t(Compare()) {
     t.insert_unique(first, last); }//...iterator insert(iterator position, const value_type& x) {
      //其中一个插入操作版本typedef typename rep_type::iterator rep_iterator;return t.insert_unique((rep_iterator&)position, x);}//...void erase(iterator position) {
         //其中一个版本的删除操作typedef typename rep_type::iterator rep_iterator;t.erase((rep_iterator&)position);}//...//在first和last的前闭后开的区间中进行二分查找第一个不小于x的值iterator lower_bound(const key_type& x) const {
    return t.low_bound(x);   }//在first和last的前闭后开的区间中进行二分查找第一个大于x的值iterator upper_bound(const key_type& x) const {
    return t.upper_bound(x);}//返回上述两种方式返回的迭代器区间pair<iterator, iterator> equal_range(const key_type& x) const {
    return t.equal_range(x);}//...
};

2.3 multiset

• 与set特性完全相同，唯一差别在于它允许键值重复，因此插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()

template < class Key, class Compare = less<Key>, class Alloc = alloc>
class multiset {
    
public:
//...template <class InputIterator>multiset(InputIterator first, InputInterator last): t(Compare()) {
     t.insert_equal(first, last); }//...
};

3. map

3.1 map性质

1. map采用RB-tree作为其底层机制
2. 所有元素都会根据元素的键值自动被排序
3. map的所有元素都是pair，同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为元素值，map不允许两个元素拥有相同的键值
4. 不能通过map的迭代器改变map的键值，因为map元素的键值关系到map元素的排列规则，任意改变map的元素键值会破坏map组织；但可以修正元素的实值
5. 由于map不允许有两个相同的键值，所以插入时采用的是RB-tree的insert_unique方式

3.2 pair

• pair是一个结构体类型，里面成员都是public的:

template <class T1, class T2>
struct pair {
    typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()) {
    }pair(const T1& a, const T2& b) : first(a), second(b)  {
    }
};

3.3 map实现

• 以下只将map特有的一些性质通过其源码表现出来：

template <class Key, class T,  class Compare = less<key>, class Alloc = allloc>
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;   //键值比较函数//调用元素比较函数class value_compare: public binary_function<value_type, value_type, bool> {
    friend class map<Key, T, Compare, Alloc>;protected:Compare comp;value_compare(Compare c) : comp(c) {
    }public:bool operator() (const value_type& x, const value_type& y) const {
    return comp(x.first, y.first);}};
private://...typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t;      //采用红黑树来表示map
public://...typedef typename  rep_type::iterator iterator;  //定义为iterator，允许更改//...//以下列举出的构造函数与插入均使用insert_unique方式template <class InputIterator>map(InputIterator first, InputIterator lst): t(Compare()) {
     t.insert_unique(first, last); }//...value_compare value_comp() const {
     return value_compare(t.key_compare());  } //元素比较//...T& operator[] (const key_type& k)  {
       //下标操作符return (*((insert(value_type(k, T()))).first)).second; }iterator insert(iterator position, const value_type& x) {
      //其中一个插入操作版本return t.insert_unique(position, x);}pair<iterator, bool> insert(const value_type& x)  {
     //另一个插入操作版本return t.insert_unique(x); }//...void erase(iterator position) {
         //其中一个版本的删除操作typedef typename rep_type::iterator rep_iterator;t.erase((rep_iterator&)position);}//...//在first和last的前闭后开的区间中进行二分查找第一个不小于x的值iterator lower_bound(const key_type& x) const {
    return t.low_bound(x);   }//在first和last的前闭后开的区间中进行二分查找第一个大于x的值iterator upper_bound(const key_type& x) const {
    return t.upper_bound(x);}//返回上述两种方式返回的迭代器区间pair<iterator, iterator> equal_range(const key_type& x) const {
    return t.equal_range(x);}//...
};

3.4 insert()函数及subscript()操作

1. insert()函数：针对参数只有一个元素值的插入函数：

pair<iterator, bool> insert(const value_type& x){
     return t.insert_unique(x); }

我们可以观察上面的函数，其返回值是一个pair类型，其第一个值为迭代器类型，第二个值为bool类型，其中bool类型代表此次插入是否成功，而迭代器类型则表示指向被插入的那个元素

2. subscript()操作：

用法有两种：

• 作为左值运用：

map<string, int> simap;
simap[string("jjhou")] = 1;    //左值运用

• 作为右值运用：

int number = simap[string("jjhou")];  //右值引用

分析下标操作函数：

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

1. 首先产生一个临时对象：

value_type(k, T())

2. 再将该元素插入到map中：

insert(value_type(k, T()))

3. 取插入操作返回的pair的第一元素：

(insert(value_type(k, T()))).first

4. 第一元素是一个迭代器，提领迭代器：

*((insert(value_type(k, T()))).first)

5. 获得一个map元素，取其第二元素：

(*((insert(value_type(k, T()))).first)).second

3.5 multimap

• 与map特性完全相同，唯一差别在于它允许键值重复，因此插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique()

template < class Key, class Compare = less<Key>, class Alloc = alloc>
class multimap {
    
public:
//...template <class InputIterator>multiset(InputIterator first, InputInterator last): t(Compare()) {
     t.insert_equal(first, last); }//...
};