c++ set用法详解

c++ stack用法详解

set

set就是集合，STL的set用二叉树实现，集合中的每个元素只出现一次(参照数学中集合的互斥性)，并且是排好序的(默认按键值升序排列)

访问元素的时间复杂度是 O ( log ⁡ 2 n ) O(\log_2n) O(log2​n)

在c++中，set的头文件是#include

set具有迭代器set::iterator i 定义一个迭代器,名为i 可以把迭代器理解为C语言的指针

set常用操作

1. set<int> q; //以int型为例 默认按键值升序
2. set<int,greater<int>> p; //降序排列
3. int x;
4. q.insert(x); //将x插入q中
5. q.erase(x); //删除q中的x元素,返回0或1,0表示set中不存在x
6. q.clear(); //清空q
7. q.empty(); //判断q是否为空，若是返回1，否则返回0
8. q.size(); //返回q中元素的个数
9. q.find(x); //在q中查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 q.end()
10. q.lower_bound(x); //返回一个迭代器，指向第一个键值不小于x的元素
11. q.upper_bound(x); //返回一个迭代器，指向第一个键值大于x的元素
13. q.rend(); //返回第一个元素的的前一个元素迭代器
14. q.begin(); //返回指向q中第一个元素的迭代器
16. q.end(); //返回指向q最后一个元素下一个位置的迭代器
17. q.rbegin(); //返回最后一个元素

复制代码

set单元素应用

1. #include<iostream>
2. #include<set>
3. using namespace std;
4. int main()
5. {
6. set<int> q; //默认按升序排列
7. q.insert(5);
8. q.insert(5);
9. q.insert(5);
10. cout<<"q.size "<<q.size()<<endl; //输出 1 ,在set插入中相同元素只会存在一个
12. q.clear(); //清空set
13. cout<<"q.size "<<q.size()<<"\n\n";
15. q.insert(4);
16. q.insert(4);
17. q.insert(3);
18. q.insert(3);
19. q.insert(2);
20. q.insert(1);
22. cout<<"lower_bound "<<*q.lower_bound(3)<<endl; //返回3
23. cout<<"upper_bound "<<*q.upper_bound(3)<<"\n\n"; //返回4
25. set<int>::iterator i;
26. for( i=q.begin();i!=q.end();i++) //set的遍历
27. cout<<*i<<" "; //输出1 2 3 4，可见自动按键值排序
28. cout<<endl;
30. q.erase(4); //删除q中的 4
32. for(i=q.begin();i!=q.end();i++) //再次遍历set 只输出 1 2 3
33. cout<<*i<<" ";
34. cout<<"\n\n";
37. set<int,greater<int>> p; //降序排列
38. p.insert(1);
39. p.insert(2);
40. p.insert(3);
41. p.insert(4);
42. p.insert(5);
43. for(i=p.begin();i!=p.end();i++)
44. cout<<*i<<" ";
45. cout<<endl;
47. return 0;
48. }

复制代码

set多元素应用(结构体)

1. #include<iostream>
2. #include<set>
3. using namespace std;
4. struct node{
5. int a,b;
6. bool operator< (const node W)const
7. {
8. return a>W.a; //按a的值升序
9. }
10. }t;
11. int main()
12. {
13. set<node> q;
14. t.a=1;
15. t.b=2;
16. q.insert(t);
18. t.a=4;
19. t.b=2;
20. q.insert(t);
22. t.a=3;
23. t.b=5;
24. q.insert(t);
26. set<node>::iterator i;
27. for(i=q.begin();i!=q.end();i++)
28. {
29. t=*i;
30. cout<<t.a<<" "<<t.b<<endl;
31. }
32. return 0;
33. }

复制代码

例题

题目：HDU - 2094 产生冠军

代码：

1. #include<iostream>
2. #include<set>
3. using namespace std;
4. int main()
5. {
6. int n;
7. string a,b;
8. while(cin>>n && n)
9. {
10. set<string> A,B;
11. for(int i=0;i<n;i++)
12. {
13. cin>>a>>b;
14. A.insert(a);
15. A.insert(b);
16. B.insert(b);
17. }
19. if(A.size()-B.size()==1)
20. cout<<"Yes\n";
21. else
22. cout<<"No\n";
23. }
24. return 0;
25. }

复制代码

---

c++ stack用法详解