初识multiset

通过前面对set容器的学习，我们已经完全掌握了set容器基本的增删查改操作，如果读者还不知道set容器可跳转《初识STL库中的set容器》。本节我们将会学习一个特殊的set容器——multiset，就像multimap对于map那样允许存在重复键值，multiset的特殊之处也在于允许存在重复键值。读者可以试想一下，如果set允许存在重复键值，那么影响最大的会是什么？没错，multimap会丧失“去重”功能，只能进行动态排序。值得注意的是，当我们需要统计multiset容器内所有的key的元素个数时，推荐使用count()而不是equal_range()。那我们就通过代码来了解multiset容器吧。

1. 如何创建multiset容器：创建multiset容器其实与创建set容器一样，没有什么区别。

#include<bits/stdc++.h>//万能头，以效率为中心 
#include<string>
#include<set>//包含头文件，养成好习惯 
/*multiset*/
/*动态排序去重*/ 
using namespace std;
/*multiset的创建方式*/
void test()
{
multiset<int> ms1;//直接创建
multiset<int> ms2{5,4,3,2,1} ;//初始化列表
multiset<int> ms3(ms2) ;//拷贝构造
multiset<int> ms4;
ms4=ms2;//'='运算符重载
multiset<int> ms5(ms2.begin(),ms2.end()) ;//迭代器范围构造 
}
int main(){
    test();
    return 0;
}

总共有4种方法初始化我们的multiset容器，你都学会了吗？

2. 如何为multiset容器添加元素：我们一般通过insert()或emplace()，还可以通过emplace_hint()。

#include<bits/stdc++.h>//万能头，以效率为中心 
#include<string>
#include<set>//set已经包含了multiset，无需另起头文件 
/*为multiset容器插入元素*/
/*不同于set容器，multiset容器允许存在重复键值*/
/*insert()、emplace_hint()、emplace()*/ 
using namespace std;
void test()
{
multiset<int> ms;
/*insert*/
ms.insert(0);//直接插入
ms.insert(ms.begin(),1) ;//带迭代器参数插入
multiset<int> s_t({7,7,3,7,10});
ms.insert(++s_t.begin(),s_t.end()) ;//区间插入 
ms.insert({2,7,4,5});//多个插入 
cout <<"multiset容器先后插入0、1、{7,7,3,7,10}、{2,7,4,5}后有元素："  ;
for(auto it = ms.begin();it!=ms.end();++it)cout << *it << " ";
cout << '\n';
cout << '\n';
/*emplace*/
/*参数是构造新元素的参数而不是对象*/ 
ms.emplace(0);//只能插入单个元素 
cout <<"multiset容器插入0后有元素："  ;
for(auto it = ms.begin();it!=ms.end();++it)cout << *it << " ";
cout << '\n';
cout << '\n';
/*emplace_hint()*/
/*有返回值，类型为迭代器。插入成功则返回指向新元素的迭代器，否则返回指向已有元素的迭代器。*/ 
auto hint = ms.begin();
for(int i=0;i<5;++i)
{
hint = ms.emplace_hint(hint,i+1);
}
cout <<"multimultiset容器插入1,2,3,4,5后有元素："  ;
for(auto it = ms.begin();it!=ms.end();++it)cout << *it << " ";
cout << '\n';
}
int main(){
    test();
    return 0;
}

编译结果如下：

总共有3种方法为我们的multiset容器添加元素，你都学会了吗？

3. 如何访问multiset容器内的元素：由于multiset和set一样没有'[]'和at()，所以一般是通过迭代器或是find()的方式进行访问。此外，我们还需要学会lower_bound()、upper_bound()这两种按条件查找元素的方法，通过count(key)或equal_range(key)能够查询key的元素个数。

#include<bits/stdc++.h>//万能头，以效率为中心 
#include<string>
#include<set>//包含头文件，养成好习惯 
/*如何访问multiset容器内的元素*/
using namespace std;
void test()
{
multiset<int> ms{1,2,3,3,3,4,5} ;
/*1.find()：有返回值，类型为迭代器。存在返回指向元素的迭代器，否则返回end()*/
if(ms.find(3)!=ms.end())cout << "存在元素" << *ms.find(3) << '\n';
if(ms.find(0)==ms.end())cout << "不存在元素0" << '\n';
/*2.迭代器*/
cout << "遍历set容器为： ";
for(multiset<int>::iterator it = ms.begin();it!=ms.end();++it) cout << *it << " ";
cout << '\n';
/*3.lower_bound()、upper_bound()和equal_range()*/
/*3.1lower_bound(key):返回指向最后一个键值<key的迭代器*/
cout << "通过lower_bound(key)找到所有键<key的元素";
 for(auto it =ms.begin();it!= ms.lower_bound(4);++it) cout << *it << " ";
 cout << '\n';
/*3.2upper_bound(key):返回指向第一个键值>key的迭代器*/
cout << "通过uper_bound(key)找到所有键>key的元素";
 for(auto it =ms.upper_bound(3);it!=ms.end() ;++it) cout << *it << " ";
 cout << '\n';
 /*3.3equal_range(key):返回一个pair<iterator,iterator>。其中first指向第一个键值==key的迭代器，second指向最后一个键值==key的迭代器*/
pair<multiset<int>::iterator,multiset<int>::iterator> range = ms.equal_range(3);
int cnt =0;
for(multiset<int>::iterator it = range.first;it!=range.second;++it)cnt++;
cout <<"通过equal_range(key)查看有几个键==key的元素总共有【" <<cnt <<"】个key==3的元素\n";
/*4.count()*/
 cout <<"通过count(key)查看有几个键==key的元素总共有【" <<ms.count(3) <<"】个key==3的元素\n";
 
}
int main(){
    test();
    return 0;
}

编译结果如下：

使用迭代器遍历multiset容器，使用find(key)查找第一个key，使用lower_bound()、upper_bound()按条件查找，如果需要统计元素个数则推荐使用count()而不是equal_range()。

4. 如何为multiset容器删除元素：我们一般通过erase()，还可以通过clear()清空容器。

#include<iomanip>
#include <iostream>
#include <set>
#include <string>
using namespace std;
/*erase()删除multiset内元素*/ 
void test()
{
multiset<int> ms({1,2,3,3,3,3,4,5,6,6}) ;
ms.erase(7);//直接删
cout << "把7删了：" ;
for(auto it = ms.begin();it!=ms.end();++it) cout << *it << " ";
cout << '\n';
ms.erase(ms.begin()) ;//删除迭代器指向元素
cout << "把第一个元素1删了：" ;
for(auto it = ms.begin();it!=ms.end();++it) cout << *it << " ";
cout << '\n';
ms.erase(++ms.begin(),ms.end()) ;//区间删除
cout << "除第一个元素以外的所有元素删了：" ;
for(auto it = ms.begin();it!=ms.end();++it) cout << *it << " ";
cout << '\n';
  
/*clear()*/
ms.clear();
cout << "全部清除后有元素：【"  << ms.size() << "】个\n";
}
int main() {
    test();
    return 0;
}

编译结果如下：

通过erase()三个重载函数实现不同方式的删除，读者都学会了吗？

总结：multiset容器和set容器十分“相似”，对应元素操作也相对冗杂，读者需自行归纳总结，分清楚他们之间的区别，切勿混淆使用，避免犯错！一般在算法竞赛上，multiset常常用于求取滑动窗口的中位数、查询和统计区间等。