关联式容器之集合set与多重集合multiset

一、集合简介

set，又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一、且按一定顺序排列的。因为其内部是通过非线性的二叉树结构方式来组织（具体是借助红黑树的结构原理实现的），所以在插入的时候比vector快，但查找和末尾添加比vector慢。

set与顺序性容器vector、deque、list相比最大的特点：set是内部排序的，也就是set的所有元素是按一定顺序排列的。set不支持随机访问，查询效率强于list。并且set还能像数学中的“集合”一样，保证集合中的元素是唯一的。

multiset，是多重集合，其实现方式和set是相似的，只是它不要求集合中的元素是唯一的，也就是说multiset集合中的同一个元素可以出现多次。

二、集合基本使用方法

1.申明集合变量

要使用set或者multiset，首先要引入set头文件：#include<set>。简单地申明集合时，集合中的元素默认是按照从小到大排列的，当然可以指定排序规则：

//默认情况下，set内部元素按照从小到大排列 
set<int> s1;
//指定比较函数为less<T>，set内部元素按照从小到大排列（非降序）
set<int,less<int> > s2;
//指定比较函数为greater<T>，set内部元素按照从大到小排列（非升序）
set<int,greater<int> > s3;
set<string,greater<string> > s4;

2.常用成员函数

集合提供了下列常用的成员函数：

1. size()，获取元素数量；
2. empty()，判断集合是否为空；
3. insert(x)，插入元素x；
4. erase(x)，删除元素x，或者删除迭代器x指向的元素；
5. count(x)，获取集合中元素x出现次数，对于set，返回值为0或者1；对于multiset返回值不止0和1；
6. clear()，清空集合；
7. 和其他容器一样，提供了begin()、end()、rbegin()、rend()。

#include<iostream>
#include<set>
using namespace std;
int main()
{
    set<int> s;
	cout<<"size:"<<s.size()<<endl;
	
	s.insert(1);
	cout<<"size:"<<s.size()<<endl;
	//begin()指向第一个元素的迭代器，其值就是*(s.begin())
	//end()指向最后一个元素下一个位置的迭代器，
	//那么最后一个元素的值是*(--s.end()) 
	cout<<*(s.begin())<<" "<<*(--s.end())<<endl; 
	
	int a[8] = {2,2,5,3,8,3,1,0};
	for(int i=0;i<8;i++){
		s.insert(a[i]);
		cout<<"size:"<<s.size()<<endl;
		cout<<*(s.begin())<<" "<<*(--s.end())<<endl;	
	}
	//上面通过循环将数组的元素插入到集合中
	//其实也可以这样一步实现：s.insert(a,a+8);
	
	cout<<s.count(8)<<endl;
	s.erase(8);
	cout<<s.count(8)<<endl;

	s.erase(s.begin());   //通过迭代器删除元素
	
	//遍历set 
	set<int>::iterator it = s.begin();
	for(;it!=s.end();it++) cout<<*it<<" ";
	cout<<endl;
	
	//反向遍历set 
	set<int>::reverse_iterator rit = s.rbegin();
	for(;rit!=s.rend();rit++) cout<<*rit<<" ";
	cout<<endl;
	
	s.clear();
	cout<<"size:"<<s.size()<<endl;
	if(s.empty()) cout<<"none."<<endl;
    return 0;
}

此外，还可以借助C++语言for循环的高级用法遍历set：

#include<iostream>
#include<set>
using namespace std;
int main()
{
    set<int> s{1,2,3,4,5,6,7,8,9,10};
	for(int n:s){
		cout<<n<<endl;
	}
    return 0;
}

3.查找元素

集合提供了find成员函数用于查找元素是否存在，返回值是迭代器：

#include<iostream>
#include<set>
using namespace std;

//遍历容器的模板函数 
template<typename Iter>
void list_elements(Iter begin, Iter end){
    while(begin!=end){
        cout<<*begin<<" ";
        begin++;
    }
    cout<<endl;    
}
int main()
{ 
    int a[8] = {2,2,5,3,8,3,1,0};
    set<int> s(a,a+8);
    if(!(s.empty())) list_elements(s.begin(),s.end());
    
    if(s.find(8)!=s.end()) cout<<"found!"<<endl;
    else cout<<"not found!"<<endl;
    return 0;
}

此外，集合还提供了成员函数 lower_bound(x) 用来查找第一个大于等于目标变量 x 的迭代器，提供 upper_bound(x) 用来查找第一个大于目标变量 x 的迭代器，这两个成员函数内部都是通过二分查找实现。

#include<iostream>
#include<set>
using namespace std;

//遍历容器的模板函数 
template<typename Iter>
void list_elements(Iter begin, Iter end){
    while(begin!=end){
        cout<<*begin<<" ";
        begin++;
    }
    cout<<endl;    
}
int main()
{ 
    int a[8] = {2,2,5,3,8,3,1,0};
    set<int> s(a,a+8);
    if(!(s.empty())) list_elements(s.begin(),s.end());

    auto it1 = s.lower_bound(3);
    if(it1!=s.end()) cout<<*it1<<endl;

    auto it2 = s.upper_bound(3);
    if(it2!=s.end()) cout<<*it2<<endl;
    return 0;
}

三、元素是结构体的集合

和优先队列一样，如果集合的元素为结构体或者类，那么需要指定相应的比较函数，或者结构体（或者类）重载相应的运算符：

#include<iostream>
#include<set>
using namespace std;
struct Point{
    double x,y;
    Point(double x,double y){
        this->x = x;
        this->y = y;
    }
};
//通过结构体自定义类似于less<T>和greater<T>的仿函数 
struct cmp{
    bool operator ()(const Point &a,const Point &b){
        return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
    }
}; 

void print(const set<Point,cmp> &s){
    for(auto ite=s.begin();ite!=s.end();ite++) cout<<"("<<ite->x<<","<<ite->y<<") ";
    cout<<endl;
}

int main()
{
    set<Point,cmp> s; 
    s.insert(Point(1,1));
	//插入时，会被判断与前面的Point(1,1)“相等”，不会被插入到集合里
    s.insert(Point(1,1));
    print(s);
    
    s.insert(Point(1,2));
    //插入时，会被判断与前面的Point(1,2)“相等”，不会被插入到集合里
    s.insert(Point(2,1));
    print(s);
    return 0;
}

#include<iostream>
#include<set>
using namespace std;
struct Point{
    int x,y;
    Point(int x,int y){
        this->x = x;
        this->y = y;
    }
}; 
//比较规则：坐标点到原点的距离 
bool operator < (const Point &a,const Point &b){
	return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}

void print(const set<Point> &s){
    for(auto ite=s.begin();ite!=s.end();ite++) cout<<"("<<ite->x<<","<<ite->y<<") ";
    cout<<endl;
}

int main(){
    set<Point> s;            //set<Point,less<Point> > s;
    s.insert(Point(1,1));
	//插入时，会被判断与前面的Point(1,1)“相等”，不会被插入到集合里
    s.insert(Point(1,1));
    print(s);
    
    s.insert(Point(1,2));
    //插入时，会被判断与前面的Point(1,2)“相等”，不会被插入到集合里
    s.insert(Point(2,1));
    print(s);
    return 0;
}

#include<iostream>
#include<set>
using namespace std;
struct Point{
    double x,y;
    Point(double x,double y){
        this->x = x;
        this->y = y;
    }
};
//比较规则：坐标点到原点的距离 
bool operator < (const Point &a,const Point &b){
	return a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y;
}
bool operator > (const Point &a,const Point &b){
	return a.x*a.x+a.y*a.y>b.x*b.x+b.y*b.y;
	//return b<a; 亦可
}
int main()
{
    //默认情况，使用的是less<T>，需要使用到Point结构体重载的<运算 
    set<Point> s1;
    //指定使用greater<T>，需要使用到Point结构体重载的>运算
    set<Point,greater<Point> > s2; 
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        s1.insert(Point(x,y));
        s2.insert(Point(x,y));
    }
    
    //遍历s1 
    for(auto it = s1.begin();it!=s1.end();it++){
        cout<<"("<<(it->x)<<","<<(it->y)<<")"<<endl;
    }
    //遍历s2 
    for(auto it = s2.begin();it!=s2.end();it++){
        cout<<"("<<(it->x)<<","<<(it->y)<<")"<<endl;
    }
    return 0;
}

上面的程序，依次输入四个坐标点 $(1,1)、(-1,-1)、(-1,1)、(1,-1)$，存入到 set 中的只有坐标点 $(1,1)$，因为 set 会将这四个坐标点“看成”是相等的数据，去重后只会留下第一个坐标点。

读者可能会有疑问，Point 结构体中并没有重载==运算符，set 是如何判断两个 Point 变量相等的呢？以默认使用 Point 结构体重载的 < 运算初始化的集合 s1 为例，内部去重时如果要比较两个 Point 变量 a、b 的大小，当 !(a < b) && !(b < a) 时就认为 a、b相等。同理，以使用 Point 结构体重载的 > 运算初始化的集合 s2 为例，内部去重时如果要比较两个 Point 变量 a、b 的大小，当 !(a > b) && !(b > a) 时就认为 a、b相等。上面的程序，如果将 s1,s2 修改为 multiset，就没了去重的效果。

*四、集合相关操作

STL的algorithm库中提供了一系列的函数用来实现类似于数学中集合的操作——并集、交集、差集、对称集，还可以判断一个集合是否是另一个集合的子集。特殊地，因为set内部重载了==和!=运算符，可以直接用==和!=判断两个集合是否相等（集合所有元素依次相等）。

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
//遍历容器的模板函数
template<typename Iter>
void list_elements(Iter begin, Iter end){
    while(begin!=end){
    	cout<<*begin<<" ";
    	begin++;
	}
    cout<<endl;    
}

int main(){
	set<int> s1,s2,s3;
	
	s1.insert(1); 
	s1.insert(2); 
	s1.insert(3); 
	
	s2.insert(2); 
	s2.insert(3);
	s2.insert(4);
	
	cout<<"s1:";
	list_elements(s1.begin(),s1.end()); 
	cout<<"s2:";
	list_elements(s2.begin(),s2.end()); 
	
	//并集 
	set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin())); 
	list_elements(s3.begin(),s3.end());
	
	s3.clear();
	//交集 
	set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin())); 
	list_elements(s3.begin(),s3.end());
	
	s3.clear();
	//差集：s1-s2（s1中有,s2中没有） 
	set_difference(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin())); 
	list_elements(s3.begin(),s3.end());
	
	s3.clear();
	//差集：s2-s1（s2中有,s1中没有） 
	set_difference(s2.begin(),s2.end(),s1.begin(),s1.end(),inserter(s3,s3.begin())); 
	list_elements(s3.begin(),s3.end());
	
	s3.clear();
	//对称集：并集-交集（仅在s1中出现或者仅在s2中出现） 
	set_symmetric_difference(s2.begin(),s2.end(),s1.begin(),s1.end(),inserter(s3,s3.begin())); 
	list_elements(s3.begin(),s3.end());
	
	s2.erase(4);
	//判断s1是否包含s2（s2是否是s1的子集） 
	if(includes(s1.begin(),s1.end(),s2.begin(),s2.end())) cout<<"YES"<<endl;
	else cout<<"NO"<<endl; 
	
	//判断集合是否相等 
	if(s1!=s2) cout<<"no equal\n";
	
	s1.erase(1);
	if(s1==s2) cout<<"equal\n";
	return 0;
}