STL:multiset

multiset

有时需要大量增加删除数据同时还需要进行大量数据的查找并且增加删除数据,查找数据都能在 log(n)复杂度完成,这种时候排序+二分查找显然不可行,可以使用"平衡二叉树"数据结构存放数据,体现在STL中就是四种"排序容器" multiset set multimap map。它们共同的特点是它们是排好序的,你只需要把数据插进去就行而不用管数据放在哪,它能够自动维持有序的特性也就是自动排好序

multiset< T > st;

定义了一个multiset变量st,st里面可以存放T类型的数据并且能自动排序。开始st为空

排序规则:表达式"a < b"为true则 a 排在 b 前面

可用 st.insert添加元素,st.find查找元素,st.erase删除元素，复杂度都是 log(n)

用法示例:

#include <iostream>
#include <cstring>
#include <set>                 //使用multiset和set需要此头文件
using namespace std;
int main()
{
    multiset<int> st;
    int a[10]={1,14,12,13,7,13,21,19,8,8 };
    for(int i = 0;i < 10; ++i)
          st.insert(a[i]); //插入的是a [i]的复制品
    multiset<int>::iterator i; 
//遍历访问multimap里的东西要用迭代器。multiset就像一个类型的名字。迭代器近似于指针
    for(i = st.begin(); i != st.end(); ++i)
            cout << * i << ",";
    cout << endl;
输出:1,7,8,8,12,13,13,14,19,21,
    
    
    i = st.find(22); //查找22，返回值是迭代器
    if( i == st.end()) //找不到则返回值为 end()
          cout << "not found" << endl;
    st.insert(22); //插入 22
    i = st.find(22);
    if( i == st.end())
          cout << "not found" << endl;
    else
          cout << "found:" << *i <<endl;
    //找到则返回指向找到的元素的迭代器
输出：
not found
found:22    
    
//此时st内顺序为1,7,8,8,12,13,13,14,19,21,    
    i = st.lower_bound(13);
//返回最靠后的迭代器 it,使得[begin(),it)中的元素都在 13 前面,复杂度 log(n)
    cout << * i << endl;
    i = st.upper_bound(8);
//返回最靠前的迭代器 it,使得[it,end())中的元素都在 8 后面,复杂度 log(n)
    cout << * i << endl;
    st.erase(i); 
//删除迭代器 i 指向的元素,即12
    for(i = st.begin(); i != st.end(); ++i)
          cout << * i << ",";
    return 0;
}
输出：
13
12
1,7,8,8,13,13,14,19,21,22,

multiset上的迭代器multiset < T >::iterator p;

p是迭代器,相当于指针。可用于指向multiset中的元素。访问multiset中的元素要通过迭代器。

与指针的不同：
multiset上的迭代器可 ++ ，–， 用 != 和 == 比较，不可比大小,不可加减整数,不可相减

st.begin() 返回值类型为 multiset< T >::iterator,是指向st中的头一个元素的迭代器
st.end() 返回值类型为 multiset< T >::iterator,是指向st中的最后一个元素后面的迭代器
对迭代器 ++就指向容器中下一个元素,-- 则令其指向上一个元素

自定义排序规则的multiset 用法

例1:

#include<iostream>
#include<cstring>
#include<set>
using namespace std;

struct Rule1{
       bool operator()(const int & a,const int & b)const{
           return (a%10) < (b%10);
       }   
};

int main(){
    multiset<int,greater<int>>st;     //排序规则从大到小
    int a[10]={1,14,12,13,7,13,21,19,8,8 };
    for(int i = 0;i < 10; ++i)
            st.insert(a[i]);
    multiset<int,greater<int> >::iterator i;
    for(i = st.begin(); i != st.end(); ++i)
            cout << * i << ",";
    cout << endl;
    
    multiset<int,Rule1 > st2;//st2的元素排序规则为：个位数小的排前面
    for(int i = 0;i < 10; ++i)
            st2.insert(a[i]);
    multiset<int,Rule1>::iterator p;
    for(p = st2.begin(); p != st2.end(); ++p)
          cout << * p << ",";
    cout << endl;
    p = st2.find(133);
    cout << * p << endl;

    return 0;
}
输出:
21,19,14,13,13,12,8,8,7,1,
1,21,12,13,13,14,7,8,8,19,
13
之所以没有133却找得到且指向13,原因在于find(x)的原理:在排序容器中找一个元素y，使得“x必须排在y前面”和 “y必须排在x前面”都不成立。在这种情况下133和13是相等的

例2:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

struct Student {
       char name[20];
       int id;
       int score;
};
Student students [] = { {"Jack",112,78},{"Mary",102,85},
        {"Ala",333,92},{"Zero",101,70},{"Cindy",102,78}};
struct Rule {
 bool operator() (const Student & s1,const Student & s2) const {
       if( s1.score != s2.score) return s1.score > s2.score;
       else return (strcmp(s1.name,s2.name) < 0);  //分数相等按姓名字典顺序排名
       }
};
int main()
{
      multiset<Student,Rule> st;
      for(int i = 0;i < 5;++i)
              st.insert(students[i]);    //插入的是students[i]的复制品
      multiset<Student,Rule>::iterator p;
      for(p = st.begin(); p != st.end(); ++p)
          cout << p->score <<" "<<p->name<<" "
                << p->id <<endl;
      Student s = { "Mary",1000,85};
      p = st.find(s);
      if( p!= st.end())
        cout << p->score <<" "<< p->name<<" "
            << p->id <<endl;
      return 0;
}
输出:
92 Ala 333
85 Mary 102
78 Cindy 102
78 Jack 112
70 Zero 101
85 Mary 102
明明两个Mary明明不一样却能找到。因为查找的时候不是用==号去判断是否相等的。两个东西谁排在前面都可以就是相等的。这Mary的id不一样但是拿去排序谁排在前面都可以,因为排序规则和id无关,只看name和score。