STL之multiset

multiset<T> st;

• 定义了一个multiset变量st，st里面可以存放T类型的数据，并且能够自动排序。初始st为空。
• 排序规则：表达式“a<b”为true，则a排在b的前面。
• st.insert 添加元素，st.find查找元素， st.erase删除元素，复杂度都是$log(n)$

头文件#include <set>//使用multiset和set都需要使用

multiset<T>::iterator p;

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

• 与指针的不同：

  multiset上的迭代器可++，–，用!=和==比较，但不可以比大小，不可以加减整数，不可相减

• st.begin()返回值类型为multiset<T>::iterator,是指向st中的头一个元素的迭代器

• st.end()返回值类型为multiset<T>::iterator,是指向st中的最后一个元素后面的迭代器

• 对迭代器++，其就是指向容器中下一个元素，–则令其指向上一个元素

一般用法

#include<iostream>
#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;//迭代器，近似于指针
	for(i=st.begin();i!=st.end();i++){
		cout<<*i<<',';
	} 
	cout<<endl;
	i=st.find(22);//查找22，返回值为迭代器
	if(i == st.end()){//找不到则返回值为end() 
		cout<<"Not Found"<<endl;
	} 
	else {//找到则返回指向找到元素的迭代器 
		cout<<"Found "<<*i<<endl;
	}
	st.insert(22);//插入22
	i=st.find(22);//再次查找 
	if(i == st.end()){ 
		cout<<"Not Found"<<endl;
	} 
	else {
		cout<<"Found "<<*i<<endl;
	}
	i = st.lower_bound(13);
	//返回最靠后的迭代器i，使得[begin(),i)中的元素都在13前面，复杂度为log(n)
	cout<< *i <<endl;
	i=st.upper_bound(8);
	// 回最靠前的迭代器i，使得[i,end())中的元素都在8后面，复杂度为log(n)
	cout<< *i <<endl;
	st.erase(i);//删除迭代器指向的元素，即12，并非删除迭代器
	for(i=st.begin();i!=st.end();i++)
		cout << * i << ',';
	cout<<endl; 
	return 0; 
}

自定义排序规则的用法

• 使用greater进行从大到小排序
• 自定义规则（结构体）

#include<iostream>
#include<set>//使用multiset和set使用该头文件 
using namespace std;
struct Rule1 {
	bool operator() ( const int & a, const int & b) const{
	return (a%10) < (b%10);//返回值为true则说明a必须在b前面，但若个位数字相同，采取何种方式排序呢 
	}
};
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]);//插入a[i]的复制品 
	multiset<int, greater<int> >::iterator i;
	for(i=st.begin();i!=st.end();i++){
		cout<<*i<<',';
	} 
	cout<<endl;
	multiset<int,Rule1> st2;//个位数字从小到大排列 
	for(int i=0;i<10;i++)
		st2.insert(a[i]);//插入a[i]的复制品
	multiset<int, Rule1>::iterator p; 
	for(p=st2.begin();p!=st2.end();p++){
		cout<<*p<<',';
	} 
	cout<<endl;
	p=st2.find(133);//查找133，返回值为迭代器
	if(p == st2.end()){//找不到则返回值为end() 
		cout<<"Not Found"<<endl;
	} 
	else {//找到则返回指向找到元素的迭代器 
		cout<<"Found "<<*p<<endl;
	}
	
	return 0; 
}