STL之set和multiset、 map和multimap详解

青旅半醒 2022-05-29 09:58 203阅读 0赞

[基本用法参考这篇，本篇主要讲解内部实现过程。][Link 1]

# set和multiset介绍 #

set/multiset以底层红黑树为结构，set的key和value是合一的，value就是key，因此通过比较key插入平衡二叉树，因此可以可以通过迭代器，从小到大输出key，也就是所谓的自动排序，二叉树以及排好序了。禁止通过迭代器修改key，否则二叉树结构变化了。特性和set集合差不多，唯一的区别就在于允许键值重复，底层采用RB-tree的。  
set也就是集合，一群特性相同的集合。  
set的特性：  
1、所以元素都会根据元素的键值自动排序。  
2、set元素的**键值就是实值，实值就是键值**。set不允许两个元素有相同的键值。  
3、底层直接用红黑树实现，然后通过中序遍历，即可返回键值由小到大的排列。  
4、不允许相同的元素存在，底层采用RB-tree的`inset_equal()`当插入的元素已经存在于集合中，那么将忽略，而mulitiset采用`inset_equal()`实现，允许相同的key存在于集合之中。

#include <iostream>
    #include <list>
    #include <algorithm>
    #include <iterator>
    #include <deque>
    #include <queue>
    #include <algorithm>
    #include <stdio.h>
    #include <string>
    #include <set>
    using namespace std;
    int main(void)
    {
        typedef set<int>::const_iterator ITE;
        int ia[5] = {
       4,3,2,1,0};
        set<int> iset(ia , ia+5);
        for(ITE i = iset.begin() ; i != iset.end() ; i++)
            cout << *i;
        cout << endl;
    
        cout << "size= " << iset.size() << endl;//5
        cout << "3 count= " << iset.count(3) << endl;//1
    
        iset.insert(3);
        cout << "size= " << iset.size() << endl;//5
        cout << "3 count= " << iset.count(3) << endl;//1
    
        iset.insert(5);
        cout << "size= " << iset.size() << endl;//6
        cout << "3 count= " << iset.count(3) << endl;//1
    
        iset.erase(1);
    
        iset.insert(3);
        cout << "size= " << iset.size() << endl;//5
        cout << "3 count= " << iset.count(3) << endl;//1
        cout << "1 count= " << iset.count(3) << endl;//0
    
        for(ITE i = iset.begin() ; i != iset.end() ; i++)
            cout << *i;
        cout << endl;//0 2 3 4 5
    
    
        ITE ite1 = iset.find(3);
        if(ite1 != iset.end())
            cout << "3 found" << endl;
    
        return 0;
    
    }

![这里写图片描述][Image 1]

# 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;//key和value比较使用同一个函数
    private:  
      typedef rb_tree<key_type, value_type, 
                      identity<value_type>, key_compare, Alloc> rep_type;//指定5个模板参数 
      rep_type t;  // 使用红黑树来表现set,就是一颗红黑树
    public: 
      typedef typename rep_type::const_iterator iterator;//定义迭代器是 const类型，所以不允许通过迭代器修改set里面的数值
      .....
      }

重点在于set是如何定义红黑树的，仅仅需要定义一个`Key`的类型即可。  
![这里写图片描述][70]

# map和multimap介绍 #

1、所以元素都会根据元素的键值（key）自动被排序。  
2、map的所有元素都是pair，同时拥有实值(value)和键值(key)。pair的第一个元素是key，第二个是value。map不允许两个元素拥有相同的键值，multimap允许。  
3、map迭代器不允许改变map的元素的key，否则破坏map排序。但是可以修改value，例如键是学生，值是学生的成绩单，那么成绩应该可以变。所以迭代器允许修改value而不允许修改key。  
4、底层通过红黑树实现。

## map之Demo ##

#include <bits/stl_tree.h>
    #include<map>
    #include<string>
    #include<stdio.h>
    int main(void)
    {
        map<string , int > mymap;//string为key int为value，二者pair成红黑树的Value
        mymap.insert( pair<string , int>("david" , 5) );
        mymap["jjhou"] = 1;//重载[]运算符，实现和insert一样的功能
        mymap["jerry"] = 2;//插入，并用2初始化value
        mymap["jason"] = 3;
        mymap["jimmy"] = 4;
        map<string , int >::iterator mymapIter = mymap.begin();
        for( ; mymapIter!= mymap.end() ; ++mymapIter){
            cout << (*mymapIter).first << ' ' << (*mymapIter).second << endl;
            //cout << mymapIter->first << ' ' << mymapIter->second << endl;
            cout << (mymapIter.operator->())->first  << endl;
        }
    
        mymapIter = mymap.find("mchen");//返回迭代器
        if(mymapIter == mymap.end())
            cout << "mchen not found" << endl;
    
        mymapIter = mymap.find("jerry");//此时，此迭代器指向jerry
        if(mymapIter != mymap.end())
            cout << "jerry found" << endl;
        mymapIter->second = 9;//通过map修改value而不是key。看出map迭代器类型。
        int number2 = mymap["jerry"];//演示map[]重载运算符的作用
        cout << number2 << endl;//9
        return 0;
    }

![这里写图片描述][70 1]  
理解上述的例子，重点理解map的\[\]运算符。以及迭代器的->运算符为何可以直接指向pair内部的first和second元素。重点关注这两点，然后使用起来就下笔如有神了。很轻松。下面通过源码分析之。

## map源码分析 ##

下面贴出map的简化版。

/* 简单的pair模板类，通过pair包含起来 */ 
    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) {}
    };
    
    
    
    template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>//key为键值型别，T为实值value型别，缺省采用递增排序。
    class map {
    public:
      typedef Key key_type;//键值型别
      typedef T data_type;//数据型别
      typedef T mapped_type;
      typedef pair<const Key, T> value_type;//元素型别（注意键和值，一起打成pair传递给红黑树）
      typedef Compare key_compare;//key比较函数，仿函数
    
      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 key和value的RB-tree。
    public:
      typedef typename rep_type::pointer pointer;
      typedef typename rep_type::const_pointer const_pointer;
      typedef typename rep_type::reference reference;
      typedef typename rep_type::const_reference const_reference;
      typedef typename rep_type::iterator iterator;
      typedef typename rep_type::const_iterator const_iterator;
      typedef typename rep_type::reverse_iterator reverse_iterator;
      typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
      typedef typename rep_type::size_type size_type;
      typedef typename rep_type::difference_type difference_type;
    
      //......
      //省略一些构造函数
      //......
    
      T& operator[](const key_type& k) {
       //中括号里面输入key，找出对应的值，如果没有则创建对应的key
        return (*((insert(value_type(k, T()))).first)).second;
      }//允许用中括号放元素，直接重载操作符，很牛逼哦。不好用而已，这种中括号功能很骚的哦
    
      pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
      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); }
      iterator insert(iterator position, const value_type& x) {
        return t.insert_unique(position, x);
      }
      void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }
    
      //......
      //省略一些insert/erase
      //......
    
      //将二元重载运算符声明为友元很聪明
      friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);//声明为友元的作用，应该已经很清楚了
      friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);//声明为友元的作用，已经很清楚了。
    };
    
    //定义二元重载运算符,直接调用底层红黑树的方法
    template <class Key, class T, class Compare, class Alloc>
    inline bool operator==(const map<Key, T, Compare, Alloc>& x, 
                           const map<Key, T, Compare, Alloc>& y) {
      return x.t == y.t;
    }
    template <class Key, class T, class Compare, class Alloc>
    inline bool operator<(const map<Key, T, Compare, Alloc>& x, 
                          const map<Key, T, Compare, Alloc>& y) {
      return x.t < y.t;
    }

1、map内部是将Key和Value包装成pair对象操作，所以当使用插入操作的时候，必须将key和Value通用保证成pair对象插入。如同`mymap.insert( pair<string , int>("david" , 5) );`，并且`typedef pair<const Key, T> value_type`中的key为const型别，所以不允许迭代器修改key的值，也就是说一个节点的key只可赋值一次而已，但是可以修改value数值。和上面的例子对应 起来了。  
2、`T& operator[](const key_type& k)`\[\]里面输入参数是key，返回是value的引用。首先`value_type(k, T())`将key和value合成一个pair临时对象，然后插入红黑树，并返回一个`pair`对象，first是迭代器（key不存在则指向新节点，存在则指向老节点），second是成功与否。然后通过迭代器获取pair元素的第二个值的引用。如果key存在，则修改其value，如果key不存在，则插入key并且用填入value。总之这里返回的时候value的引用。当做左值，则修改，当做右值则读取。  
3、注意map的迭代器指向的是节点，节点里面Value\_filed是pair对象。所以通过迭代器的`(*mymapIter)`是获取了节点中的pair对象，然后通过`.`运算符获取其中的key和value。  
4、\[\]运算符重载是map特有的方法，mulitimap里面并没有重载这个方法。

## mulimap源码分析 ##

里面源码和map一模一样，最大的不同就是里么没有重载\[\]运算符，并且使用了红黑树的`insert_equal`，因此允许重载的key存在。这就是和map的不同之处。。后面再使用就很简单了，我们不必要深究这下面的原理了。很容易，清楚了红黑树，一切都变得那么容易了。

[Link 1]: http://blog.csdn.net/ac_hexin/article/details/52042562
[Image 1]: 
[70]: /images/20220529/72eb30f96a1641c9bee50f810bd1a5f2.png
[70 1]: /images/20220529/51fc5bd32dab4dd2b2e0880926686b30.png