(转)set集合的用法

2022-11-08 16:29:38

原地址：http://blog.csdn.net/chaiwenjun000/article/details/50561775

SET 集合

百度百科中说集合中的元素有三个特征：

1.确定性（集合中的元素必须是确定的） 2.互异性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1） 3.无序性（集合中的元素没有先后之分。）

而STL中的集合set ,按照定义保证了元素的确定性，互异性，神奇的是其中的元素却是有序的！

卓越的前辈们在c++里为我们封装好了set，只需要在头文件里

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;

就可以方便的使用了。

如何定义一个set？

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. set<_type> _name;
  2. _type集合元素的类型 ，除了基本类型也可以是自定义类型。
  3. _name 该集合的名称

我们以int为例做一下示范

先介绍几个set常用的函数
.insert(v) //插入一个元素v
.erase(v) //删除一个元素v (可以是元素的值，也可以是迭代器（后面会有介绍）)
.empty() //判断是否为空
.count(v)//判断 v出现了几次

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;
  3. int main(){
  4. set<int>st; //定义了一个int类型的集合，名称为st
  5. st.insert(1); st.insert(7);    st.insert(4);
  6. if(!st.empty())
  7. printf("yes\n");
  8. if(st.count(1)) printf("1yes\n"); else printf("1no\n");
  9. if(st.count(2)) printf("2yes"); else printf("2no\n");
  10. }

SET的应用

有了这几个函数，set就可以做很多事了，其中最常用的就是 判断一个数是否出现过。 
set内部使用红黑树实现，也就是平衡的二叉树查找树，其插入删除查找的效率是稳定的O(logn)。这个效率是很高的，当然设计合适的hash函数速度更快O（1），但对于一般的问题这个已经足够了，而且简单书写。

下面就以昨天CF第三题为例做下示范
http://codeforces.com/contest/620/problem/C

长度为n的珠子链， 从左到右位置标号1~n， 每个位置的珠子可能有不同的种类，
规定连续的一段中如果存在两个珠子种类相同，则称为好珠子段，问最多有多少好珠子段，并打印段的位置。

方法
直接贪心，遇到两个相同的珠子，就记录下来位置。然后将之前的标记清空。
标记方法？  ai 范围 1≤ ai ≤ 10^9,开那么大的数组显然不行，而且清空也麻烦
直接用set即可！

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  7. const int maxn = 100000*4;
  8. int arr[maxn];
  9. int cnt[maxn];
  10. set<int>st;
  11. int main()
  12. {
  13. int t;
  14. scanf("%d",&t);
  15. int c = 0;
  16. for(int i=0;i<t;i++){
  17. scanf("%d",&arr[i]);
  18. if(!st.count(arr[i])) //没有标记过的
  19. st.insert(arr[i]);
  20. else
  21. {
  22. st.clear(); //清空set
  23. cnt[c++] = i+1; //记录标记的位置（出现第二次的珠子位置）
  24. }
  25. }
  26. cnt[c-1] = t;
  27. if(c == 0)
  28. printf("-1\n");
  29. else{
  30. printf("%d\n",c);
  31. int l = 1;
  32. for(int i=0;i<c;i++){
  33. printf("%d %d\n",l,cnt[i]);
  34. l = cnt[i]+1;
  35. }
  36. }
  37. return 0;
  38. }

SET的遍历

这里用到了迭代器的相关知识，学完C++后再去深究，这里知道怎么用就行了。

前面说了set中的元素是有序的，那么我们来遍历一下。

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;
  3. int main(){
  4. set<int>st; //定义了一个int类型的集合，名称为st
  5. st.insert(1); st.insert(7);    st.insert(4);
  6. st.insert(0);
  7. for(set<int>::iterator it = st.begin();it!=st.end();++it){
  8. printf("%d ",*it);
  9. }
  10. }
  11. 可以看出迭代器的使用和指针类似 ， 也是通过解引用运算符 *it来获取值，也可以通过++ -- 移动。
  12. 也可以单个取出元素
  13. set<int>::iterator it = st.begin();
  14. printf("%d\n",*it);
  15. 注意这里的.begin()代表了set中的首元素位置，而.end()代表的是尾元素位置的下一个位置。
  16. STL中很多容器都是这样的左闭右开区间，不用去深究。

SET 集合

百度百科中说集合中的元素有三个特征：

1.确定性（集合中的元素必须是确定的） 2.互异性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1） 3.无序性（集合中的元素没有先后之分。）

而STL中的集合set ,按照定义保证了元素的确定性，互异性，神奇的是其中的元素却是有序的！

卓越的前辈们在c++里为我们封装好了set，只需要在头文件里

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;

就可以方便的使用了。

如何定义一个set？

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. set<_type> _name;
  2. _type集合元素的类型 ，除了基本类型也可以是自定义类型。
  3. _name 该集合的名称

我们以int为例做一下示范

先介绍几个set常用的函数
.insert(v) //插入一个元素v
.erase(v) //删除一个元素v (可以是元素的值，也可以是迭代器（后面会有介绍）)
.empty() //判断是否为空
.count(v)//判断 v出现了几次

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;
  3. int main(){
  4. set<int>st; //定义了一个int类型的集合，名称为st
  5. st.insert(1); st.insert(7);    st.insert(4);
  6. if(!st.empty())
  7. printf("yes\n");
  8. if(st.count(1)) printf("1yes\n"); else printf("1no\n");
  9. if(st.count(2)) printf("2yes"); else printf("2no\n");
  10. }

SET的应用

有了这几个函数，set就可以做很多事了，其中最常用的就是 判断一个数是否出现过。 
set内部使用红黑树实现，也就是平衡的二叉树查找树，其插入删除查找的效率是稳定的O(logn)。这个效率是很高的，当然设计合适的hash函数速度更快O（1），但对于一般的问题这个已经足够了，而且简单书写。

下面就以昨天CF第三题为例做下示范
http://codeforces.com/contest/620/problem/C

长度为n的珠子链， 从左到右位置标号1~n， 每个位置的珠子可能有不同的种类，
规定连续的一段中如果存在两个珠子种类相同，则称为好珠子段，问最多有多少好珠子段，并打印段的位置。

方法
直接贪心，遇到两个相同的珠子，就记录下来位置。然后将之前的标记清空。
标记方法？  ai 范围 1≤ ai ≤ 10^9,开那么大的数组显然不行，而且清空也麻烦
直接用set即可！

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <set>
  6. using namespace std;
  7. const int maxn = 100000*4;
  8. int arr[maxn];
  9. int cnt[maxn];
  10. set<int>st;
  11. int main()
  12. {
  13. int t;
  14. scanf("%d",&t);
  15. int c = 0;
  16. for(int i=0;i<t;i++){
  17. scanf("%d",&arr[i]);
  18. if(!st.count(arr[i])) //没有标记过的
  19. st.insert(arr[i]);
  20. else
  21. {
  22. st.clear(); //清空set
  23. cnt[c++] = i+1; //记录标记的位置（出现第二次的珠子位置）
  24. }
  25. }
  26. cnt[c-1] = t;
  27. if(c == 0)
  28. printf("-1\n");
  29. else{
  30. printf("%d\n",c);
  31. int l = 1;
  32. for(int i=0;i<c;i++){
  33. printf("%d %d\n",l,cnt[i]);
  34. l = cnt[i]+1;
  35. }
  36. }
  37. return 0;
  38. }

SET的遍历

这里用到了迭代器的相关知识，学完C++后再去深究，这里知道怎么用就行了。

前面说了set中的元素是有序的，那么我们来遍历一下。

[cpp] view plain copy
 

(转)set集合的用法(转)set集合的用法

  1. #include<set>
  2. using namespace std;
  3. int main(){
  4. set<int>st; //定义了一个int类型的集合，名称为st
  5. st.insert(1); st.insert(7);    st.insert(4);
  6. st.insert(0);
  7. for(set<int>::iterator it = st.begin();it!=st.end();++it){
  8. printf("%d ",*it);
  9. }
  10. }
  11. 可以看出迭代器的使用和指针类似 ， 也是通过解引用运算符 *it来获取值，也可以通过++ -- 移动。
  12. 也可以单个取出元素
  13. set<int>::iterator it = st.begin();
  14. printf("%d\n",*it);
  15. 注意这里的.begin()代表了set中的首元素位置，而.end()代表的是尾元素位置的下一个位置。
  16. STL中很多容器都是这样的左闭右开区间，不用去深究。
上一篇：Java统计一个字符串中各个字符出现的次数


下一篇：oracle行转列函数以及一些窗口函数（PIVOT ,OVER）