set本质上是一棵红黑树，用法也就那么几个，插入删除lowerbound，再就是迭代器之类的
基本用法
begin()--返回指向第一个元素的迭代器
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
printf("%d",*s.begin());
//输出4
return ;
}
begin()
end()--返回指向最后一个元素的迭代器
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
printf("%d",*s.end());
//注意这里的跌倒器指向的是一个空位置！
//所以最好不要输出end() //输出末尾元素可以用下面的方法
//std::set<int>::iterator it=s.end();
//printf("%d",*--it);
return ;
}
end()
rbegin()--返回指向集合中最后一个元素的反向迭代器
rend()--返回指向集合中第一个元素的反向迭代器
find()--返回一个指向被查找到元素的迭代器
insert()--在集合中插入元素
size()--集合中元素的数目
clear()--清除所有元素
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
printf("%d\n",s.size());
s.clear();
printf("%d\n",s.size());
return ;
}
clear()
count()--返回某个值元素的个数//主要应用于multiset
#include<cstdio>
#include<set>
int main()
{
std::multiset<int>s;
s.insert();
s.insert();
s.insert();
printf("%d",s.count());
return ;
}
count
empty()--如果集合为空，返回true
erase()--删除集合中的元素
erase可以删除给定的元素，也可以删除迭代器
在multiset中，删除给定的元素是全部删除，而删除迭代器只会删除一次，下面还会讲到
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
s.erase();
s.erase(s.find());
if(s.find()==s.end()) printf("5 is not found\n");
if(s.find()==s.end()) printf("4 is not found\n");
if(s.find()!=s.end()) printf("6 is found");
return ;
}
erase()
lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
printf("%d",*s.lower_bound());
//输出为4
return ;
}
lower_bound()
upper_bound()--返回大于某个值元素的迭代器
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
s.insert();
s.insert();
s.insert();
printf("%d",*s.upper_bound());
//输出为4
return ;
}
upper_bound()
swap()--交换两个集合变量
#include<cstdio>
#include<set>
int main()
{
std::set<int>s;
std::set<int>a;
s.insert();
s.insert();
a.insert();
s.swap(a);
printf("%d",s.size());
//输出为1
return ;
}
swap()
几个常用操作
正序遍历所有元素
这个需要借助迭代器来实现
set中是重载了迭代器的++和--运算符的，所以直接使用就可以了
#include<cstdio>
#include<set>
#define sit set<int>::iterator
using namespace std;
int main()
{
set<int>s;
for(int i=;i<=;i++)
s.insert(i);
for(sit i=s.begin();i!=s.end();i++)
printf("%d ",*i);
//输出1 2 3 4 5 6 7 8 9 10
return ;
}
倒序遍历所有元素
可以使用rbegin和rend实现，他们与begin和end的关系如下图所示
#include<cstdio>
#include<set>
#define rsit set<int>::reverse_iterator
using namespace std;
int main()
{
set<int>s;
for(int i=;i<=;i++)
s.insert(i);
rsit it=s.rbegin();
for(rsit i=s.rbegin();i!=s.rend();i++)
printf("%d ",*i);
//输出10 9 8 7 6 5 4 3 2 1
return ;
}
multiset中删除元素
在multiset中，如果仅仅用erase($x$)来删除$x$元素，那么$x$的出现次数会变为$0$
解决方法是先找到$x$对应的迭代器，然后将迭代器删除，这样就可以使$x$只删除一次
#include<cstdio>
#include<set>
#define sit set<int>::iterator
using namespace std;
int main()
{
multiset<int>s;
s.insert();
s.insert();
s.insert();
s.erase();
printf("%d\n",s.count()); s.insert();
s.insert();
s.insert();
s.erase(s.find());
printf("%d\n",s.count());
//输出0 2
return ;
}
自定义排序规则
如果元素不在结构体中，需要自定义结构体并重载“$()$”运算符
#include<cstdio>
#include<set>
#define sit set<int>::iterator
using namespace std;
struct comp
{
bool operator ()(const int &a,const int &b)
{
return a>b;
}
};
int main()
{
set<int,comp>s;
for(int i=;i<=;i++)
s.insert(i);
for(sit i=s.begin();i!=s.end();i++)
printf("%d ",*i);
//输出10 9 8 7 6 5 4 3 2 1
return ;
}
若元素在结构体中，则需要重载$<$运算符
#include<cstdio>
#include<set>
#define sit set<node>::iterator
using namespace std;
struct node
{
int l,r;
node(int l=,int r=):l(l),r(r){};
bool operator < (const node &a) const
{
return r==a.r?l<a.l:r<a.r;
}
};
int main()
{
set<node>s;
for(int i=;i<=;i++)
s.insert(node(i,-i+));
for(sit i=s.begin();i!=s.end();i++)
printf("%d %d\n",i->l,i->r); //输出
/*
10 1
9 2
8 3
7 4
6 5
5 6
4 7
3 8
2 9
1 10
*/
return ;
}
在结构体中二分
只要重载了$<$，就可以在结构体中二分了
#include<cstdio>
#include<set>
#define sit set<node>::iterator
using namespace std;
struct node
{
int l,r;
node(int l=,int r=):l(l),r(r){};
bool operator < (const node &a) const
{
return r==a.r?l<a.l:r<a.r;
}
};
int main()
{
set<node>s;
for(int i=;i<=;i++)
s.insert(node(i,i));
sit it=s.lower_bound(node(,));
printf("%d %d",it->l,it->r); //输出 2 2
return ;
}
题目
都是可以用set水的大水题