多重集合multiset

多重集合是数学中的一个概念，是集合概念的推广。在一个集合中，相同的元素只能出现一次，因此只能显示出有或无的属性。而在多重集合之中，同一个元素可以出现多次。比如{1,1,1,2,2,3}不是一个集合，而是一个多重集合。一个元素在多重集合里出现的次数称为这个元素在多重集合里面的重数（或重次、重复度）。

在 C++ 中多重集合为multiset，同样是在头文件中定义，其实它就是一个可以装重复元素的set，所以基本的函数都和正常是一样的，我们不再重复叙述。

参见我的另一篇文章：

C++常用STL - set和map_都士的博客-CSDN博客

下面来看一个具体的例子：

multiset ms;
//初始时集合为空{}
ms.insert(5);
//插入元素5 {5}
ms.insert(4);
//插入元素4 {4, 5}
ms.insert(5);
//插入元素5 {4, 5, 5}
ms.insert(7);
//插入元素7 {4, 5, 5, 7}
ms.erase(3);
//删除元素3 {4, 5, 5, 7}
ms.erase(4);
//删除元素4 {5, 5, 7}
ms.erase(5);
//删除元素5 {7}

我们定义了一个存放int类型元素的多重集合ms，刚开始的时候为空。然后插入了4个元素，当前多重集合为{4, 5, 5, 7}。

后面有三个删除操作，第一个删除的元素是3，它在ms中并不存在，因此不会有任何变化（也不会出错）。第二个要删除的数是4，删完后ms中只剩下{5, 5, 7}。第三个要删除的数是5，它在ms中出现两次，erase函数会把这两个5都从集合中删去，因此最后集合变为{7}。

注意这里，multiset直接erase一个元素是把集合中这个元素全部都删掉。

那么问题来了，在有多个重复的数情况下，我们如何只从multiset里删除其中的一个数呢？这里要先介绍一个之前没有说的成员函数find。

find(x)函数返回指向第一个值为x的元素的迭代器，若x不在容器中，则返回尾后迭代器。

multiset ms;
//初始时集合为空 {}
ms.insert(5);
//插入元素5 {5}
ms.insert(4);
//插入元素4 {4, 5}
ms.insert(5);
//插入元素5 {4, 5, 5}
ms.insert(7);
//插入元素7 {4, 5, 5, 7}
multiset::iterator it;
it = ms.find(5);
//it指向第一个5的位置
cout << *it << endl;
//输出5
it = ms.find(6);
//此时 it 为尾后迭代器 ms.end()

因为有不存在的情况，所以使用find函数的时候，我们经常需要特判。

if (ms.find(x) != ms.end()) {//找得到的情况

} else {//找不到的情况

}

之前用的erase函数，它的参数是和容器内元素类型一样的，其实他还有别的版本：参数可以是一个迭代器。就是我们瞄准一个位置进行删除。

我们可以利用find函数来得到指向相应位置的迭代器，这样我们就可以只删除一个元素了。

multiset ms;
//初始时集合为空 {}
ms.insert(5);
//插入元素5 {5}
ms.insert(4); 
//插入元素4 {4, 5}
ms.insert(5);
//插入元素5 {4, 5, 5}
ms.insert(7);
//插入元素7 {4, 5, 5, 7}
ms.erase(ms.find(5)); 
//删除第一个元素5 {4, 5, 7}

警告：千万不能删除尾后迭代器，否则程序会出错。

所以在进行删除的时候，如果不确定这个元素是否存在，一定要加上判断。