STL之set和multiset、 map和multimap详解

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

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[] = {,,,,};
    set<int> iset(ia , ia+);
    for(ITE i = iset.begin() ; i != iset.end() ; i++)
        cout << *i;
    cout << endl;

    cout << "size= " << iset.size() << endl;//5
    cout << "3 count= " << iset.count() << endl;//1

    iset.insert();
    cout << "size= " << iset.size() << endl;//5
    cout << "3 count= " << iset.count() << endl;//1

    iset.insert();
    cout << "size= " << iset.size() << endl;//6
    cout << "3 count= " << iset.count() << endl;//1

    iset.erase();

    iset.insert();
    cout << "size= " << iset.size() << endl;//5
    cout << "3 count= " << iset.count() << endl;//1
    cout << "1 count= " << iset.count() << endl;//0

    for(ITE i = iset.begin() ; i != iset.end() ; i++)
        cout << *i;
    cout << endl;//0 2 3 4 5


    ITE ite1 = iset.find();
    if(ite1 != iset.end())
        cout << "3 found" << endl;

    return ;

}
           

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

的类型即可。

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" , ) );
    mymap["jjhou"] = ;//重载[]运算符，实现和insert一样的功能
    mymap["jerry"] = ;//插入，并用2初始化value
    mymap["jason"] = ;
    mymap["jimmy"] = ;
    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 = ;//通过map修改value而不是key。看出map迭代器类型。
    int number2 = mymap["jerry"];//演示map[]重载运算符的作用
    cout << number2 << endl;//9
    return ;
}
           

理解上述的例子，重点理解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的不同之处。。后面再使用就很简单了，我们不必要深究这下面的原理了。很容易，清楚了红黑树，一切都变得那么容易了。