NOIP学习小站一、集合简介
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.常用成员函数
集合提供了下列常用的成员函数：
- size()，获取元素数量；
- empty()，判断集合是否为空；
- insert(x)，插入元素x；
- erase(x)，删除元素x，或者删除迭代器x指向的元素；
- count(x)，获取集合中元素x出现次数，对于set，返回值为0或者1；对于multiset返回值不止0和1；
- clear()，清空集合；
- 和其他容器一样，提供了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;
}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());
set<int>::iterator it1 = s.lower_bound(3);
if(it1!=s.end()) cout<<*it1<<endl;
set<int>::iterator 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){
set<Point>::iterator ite = s.begin();
for(;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){
set<Point>::iterator ite = s.begin();
for(;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(set<Point>::iterator it = s1.begin();it!=s1.end();it++){
cout<<"("<<(it->x)<<","<<(it->y)<<")"<<endl;
}
//遍历s2
for(set<Point,greater<Point> >::iterator 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;
}