set用法小结
2018-06-17 20:54:24来源:未知 阅读 ()
set本质上是一棵红黑树,用法也就那么几个,插入删除lowerbound,再就是跌倒器之类的
基本用法
begin()--返回指向第一个元素的迭代器
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); printf("%d",*s.begin()); //输出4 return 0; }
end()--返回指向最后一个元素的迭代器
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); printf("%d",*s.end()); //注意这里的跌倒器指向的是一个空位置! //所以最好不要输出end() //输出末尾元素可以用下面的方法 //std::set<int>::iterator it=s.end(); //printf("%d",*--it); return 0; }
rbegin()--返回指向集合中最后一个元素的反向迭代器
rend()--返回指向集合中第一个元素的反向迭代器
find()--返回一个指向被查找到元素的迭代器
insert()--在集合中插入元素
size()--集合中元素的数目
clear()--清除所有元素
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); printf("%d\n",s.size()); s.clear(); printf("%d\n",s.size()); return 0; }
count()--返回某个值元素的个数//主要应用于multiset
#include<cstdio> #include<set> int main() { std::multiset<int>s; s.insert(5); s.insert(5); s.insert(6); printf("%d",s.count(5)); return 0; }
empty()--如果集合为空,返回true
erase()--删除集合中的元素
erase可以删除给定的元素,也可以删除跌倒器
在multiset中,删除给定的元素是全部删除,而删除迭代器只会删除一次,下面还会讲到
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); s.erase(5); s.erase(s.find(4)); if(s.find(5)==s.end()) printf("5 is not found\n"); if(s.find(4)==s.end()) printf("4 is not found\n"); if(s.find(6)!=s.end()) printf("6 is found"); return 0; }
lower_bound()--返回指向大于(或等于)某值的第一个元素的迭代器
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); printf("%d",*s.lower_bound(4)); //输出为4 return 0; }
upper_bound()--返回大于某个值元素的迭代器
#include<cstdio> #include<set> int main() { std::set<int>s; s.insert(5); s.insert(4); s.insert(6); printf("%d",*s.upper_bound(4)); //输出为4 return 0; }
swap()--交换两个集合变量
#include<cstdio> #include<set> int main() { std::set<int>s; std::set<int>a; s.insert(4); s.insert(5); a.insert(6); s.swap(a); printf("%d",s.size()); //输出为1 return 0; }
几个常用操作
正序遍历所有元素
这个需要借助跌倒器来实现
set中是重载了迭代器的++和--运算符的,所以直接使用就可以了
#include<cstdio> #include<set> #define sit set<int>::iterator using namespace std; int main() { set<int>s; for(int i=1;i<=10;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 0; }
倒序遍历所有元素
可以使用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=1;i<=10;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 0; }
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(2); s.insert(2); s.insert(2); s.erase(2); printf("%d\n",s.count(2)); s.insert(2); s.insert(2); s.insert(2); s.erase(s.find(2)); printf("%d\n",s.count(2)); //输出0 2 return 0; }
自定义排序规则
如果元素不在结构体中,需要自定义结构体并重载“$()$”运算符
#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=1;i<=10;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 0; }
若元素在结构体中,则需要重载$<$运算符
#include<cstdio> #include<set> #define sit set<node>::iterator using namespace std; struct node { int l,r; node(int l=0,int r=0):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=1;i<=10;i++) s.insert(node(i,10-i+1)); 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 0; }
在结构体中二分
只要重载了$<$,就可以在结构体中二分了
#include<cstdio> #include<set> #define sit set<node>::iterator using namespace std; struct node { int l,r; node(int l=0,int r=0):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=1;i<=10;i++) s.insert(node(i,i)); sit it=s.lower_bound(node(1,2)); printf("%d %d",it->l,it->r); //输出 2 2 return 0; }
题目
都是可以用set水的大水题
BZOJ2783
BZOJ2028
BZOJ1058
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 单独编译 2020-05-10
- STL之set 2020-04-28
- 面试前必须要知道的C++ const用法 2020-03-10
- stl_map复习 2020-02-02
- C++中set的使用 2019-12-23
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash