C++数据结构——埃拉托斯特尼筛法以及求集合的交集，并集，差集

今天药忘吃喽~ 2021-11-22 03:24 193阅读 0赞

**1.放入集合中自定义的类通常需要重载==和<运算符  
  
2.集合存储指定类型的键，且不允许有重复的键  
  
3.STL set类迭代器按照递增顺序遍历元素  
  
4.集合的应用：埃拉托斯特尼筛法--找出小于等于n的所有素数  
\*从整数m=2(m<n)开始，遍历集合的元素，删除所有2\*k<=n(k>=2)的元素  
![20130804005704078][]  
  
实现代码：  
template<typename T>  
//找出小于等于n的所有素数  
set<T> sieve(int n)  
\{  
set<T> res;  
for(int i=2;i<=n;i++) //初始化集合   
 \{   
res.insert(i);  
 \}  
  
for(int m=2;m\*m<=n;m++) //只需循环到m的二次方根   
\{   
int tem=2\*m;  
while(res.count(m)&&tem<=n) //count返回集合中m的个数，不存在时返回0   
\{   
res.erase(tem);  
tem+=m;   
\}  
\}  
  
return res;  
\}  
  
  
int main()  
\{   
  
set<int> s;  
s=sieve<int>(25);  
for(int x:s)  
\{   
cout<<x<<ends;  
\}  
  
return 0;  
\}  
  
  
output:  
2 3 5 7 11 13 17 19 23**

**5.交集,并集，差集**

**tips:STL set类的特性**

**\*不允许有重复的键  
 \* 迭代器按照递增顺序遍历元素**

**实现代码：  
\#include<iostream>  
\#include<set>  
using namespace std;  
  
  
template<typename T>  
//并集   
set<T> operator+(set<T> &s1,set<T> &s2)  
\{  
set<T> res; //保存结果   
 for(int x:s1)  
 \{   
res.insert(x);  
 \}  
  
 for(int x:s2)  
 \{   
res.insert(x);  
 \}  
  
 return res;  
\}  
  
  
  
  
template<typename T>  
//差集   
set<T> operator-(set<T> &s1, set<T> &s2)  
\{  
auto p1=s1.begin();  
auto p2=s2.begin();  
set<T> res; //保存结果   
while(p1!=s1.end()&&p2!=s2.end()) //扫描集合s1和s2   
\{   
if(\*p1<\*p2)  
 res.insert(\*p1++);  
else if(\*p1>\*p2)  
 p2++;  
else  
\{   
p1++;  
p2++;  
\}  
\}  
  
if(p1!=s1.end()) //把s1剩余元素加入结果集  
\{   
res.insert(\*p1++);  
\}   
  
return res;  
  
\}   
  
  
  
  
template<typename T>  
//交集   
set<T> operator\*(set<T> &s1,set<T> &s2)  
\{  
auto p1=s1.begin();  
auto p2=s2.begin();  
set<T> res; //保存结果   
while(p1!=s1.end()&&p2!=s2.end()) //扫描集合s1和s2   
\{   
if(\*p1<\*p2)  
 p1++;  
else if(\*p1>\*p2)  
 p2++;  
else  
\{   
res.insert(\*p1++); //把相同元素加入结果集   
p2++;  
\}   
\}   
  
return res;   
\}  
  
  
  
  
template<typename T>  
//打印集合所有元素  
void print(set<T> &s)  
\{  
for(int x:s)  
\{  
 cout<<x<<ends;  
\}   
\}  
  
  
int main()  
\{  
set<int> s1\{1,3,4,5,7,8,11\};  
set<int> s2\{2,4,5,8,9\};  
set<int> res;  
cout<<"s1: ";  
print(s1);  
  
cout<<endl<<"s2: ";  
print(s2);  
  
cout<<endl<<"s1+s2 : ";  
res=s1+s2;  
print(res);  
  
cout<<endl<<"s1-s2 : ";  
res=s1-s2;  
print(res);  
  
cout<<endl<<"s1\*s2 : ";  
res=s1\*s2;  
print(res);  
  
  
  
return 0;  
\}  
  
  
  
  
运行结果  
![Center][]**

[20130804005704078]: /images/20211122/44577ded271b49009536267b8f3cb9da.png
[Center]: /images/20211122/37f910a2fc55474dbeee1988b4417af9.png