如何使用C++STL中的multiset

1、multiset 的内部实现和 set 一样，也是一颗红黑树，因此时间复杂度较高

如何声明一个 multiset？

multiset <value_type> name;

还要在头文件中加上 "#include<set>"

2、和 set 相比，multiset 和 set 所支持的内置函数几乎一模一样

主要有：size()/empty()/clear()/insert(x)/erase(x)/find(x)/count(x)/begin()/end()

分别是 大小/判断为空/清空/插入/删除/寻找/查找个数/首迭代器/尾迭代器

其中，insert,erase,find 的时间复杂度都是 O（logn）

count 的时间复杂度是 O（元素 x 个数+logn）

其它的时间复杂度为 O（1）

log 以 2 为底，n 是 multiset 中所有元素个数

3、那么，为什么还要有“multiset”这个东西呢？

因为这个 multiset 不会自动去重，当你遇到不能去重的时候，就可以用multiset

如图，set 与 multiset 的对比

4、还有，因为 multiset 不会自动去重，这让 count(x) 函数派上了用场

set 会去重，所以元素 x 只会出现 0 次或 1 次，还不如用 find(x) 函数

但 multiset 不一样

如图，set 与 multiset 的对比

5、还有，和 set 一样，mutiset 声明时的类型必须定义小于号

int,string 等C++内置变量类型已经自动定义好了小于号

但如果 multiset 中元素类型为自定义的结构体时，你需要学会重载运算符

如果我们这么写，编译器就会报错

6、总而言之，multiset 就是 set 的不去重版本，可以根据需要选择合适的容器，降低编程难度