multiset 用法

# multiset 用法

C++ 语言中，multiset 是 <set> 库中一个非常有用的类型，它可以看陈给一个序列，插入一个数，删除一个数都能在 O (logn) 的时间内完成，而且它能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。

# 放入自定义类型的数据

不只是 int 类型，multiset 还可以存储其他的类型诸如 string 类型，结构（struct 或 class）类型。

而对于自定义类型 multiset 并不知道如何去比较，需要我们定义 multiset 里面的 rec 类型变量之间的小于关系的含义：

struct rec{
    int x,y;
};
multiset<rec>h;

1. 定义一个比较类 cmp，cmp 的内部 operator 函数的作用是比较 rec 类型 a 和 b 的大小，例如

   struct cmp{
   	bool operator()(const rec&a,const rec&b){
       return a.x < b.x || a.x == b.x && a.y < b.y;
     }
   }
   

2. 然后将语句 "multiset<rec>h;" 改成 “multiset<rec,cmp>h;” 这样之后，我们就告诉了序列 h 如何去比较里面的元素

完整代码如下：

struct rec{
    int x,y;
};
struct cmp{
	bool operator()(const rec&a,const rec&b){
    return a.x < b.x || a.x == b.x && a.y < b.y;
  }
}
multiset<rec,cmp>h;