STL容器的并集（set_union）、交集（set_intersection）和差集（set_difference）函数的使用

快来打我* 2022-11-21 09:53 133阅读 0赞

集合的交集并集和差集并不是只能用于set对象，STL提供了支持这些操作的算法，它们是通用函数。然而所有set对象都自动满足使用这些算法的先决条件—**容器必须先经过排序**。  
再三注意，使用这三个函数之前，容器必须先进行**排序**。

*  set\_union()
 *  set\_intersection()
 *  set\_difference()  
    这三个函数的接口都相同，接受五个迭代器参数。前两个迭代器定义了第一个容器的区间，接下来两个迭代器定义了第二个容器的区间，最后一个迭代器是输出迭代器，指出将结果集合复制到什么位置。这几个函数的前四个参数一样，只有第五个参数有多重版本。

> EX1：set\_union(A.begin(),A.end(),B.begin(),B.end(),inserter( C1 , C1.begin() ) );  
> 前四个参数依次是第一的集合的头尾，第二个集合的头尾。第五个参数的意思是将集合A、B取合集后的结果存入集合C中。
> 
> EX2：set\_union(A.begin(),A.end(),B.begin(),B.end(),ostream\_iterator(cout," “));这里的第五个参数的意思是将A、B取合集后的结果直接输出，（cout," "）双引号里面是输出你想用来间隔集合元素的符号或是空格。

下面是set\_union的原型：  
template<class InputIterator1, class InputIterator2, class OutputIterator>  
OutputIterator set\_union(  
InputIterator1\_First1 ,  
InputIterator1\_Last1 ,  
InputIterator2\_First2 ,  
InputIterator2\_Last2 ,  
OutputIterator\_Result  
);  
链接: [set\_union][set_union].

// set_union example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::set_union, std::sort
    #include <vector>       // std::vector
    
    int main () {
        
      int first[] = {
        5,10,15,20,25};
      int second[] = {
        50,40,30,20,10};
      std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
      std::vector<int>::iterator it;
    
      std::sort (first,first+5);     //  5 10 15 20 25
      std::sort (second,second+5);   // 10 20 30 40 50
    
      it=std::set_union (first, first+5, second, second+5, v.begin());
                                                   // 5 10 15 20 25 30 40 50  0  0
      v.resize(it-v.begin());                      // 5 10 15 20 25 30 40 50
      std::cout << "The union has " << (v.size()) << " elements:\n";
      for (it=v.begin(); it!=v.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
      return 0;
    }

链接：[set\_intersection][set_intersection].

// set_intersection example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::set_intersection, std::sort
    #include <vector>       // std::vector
    
    int main () {
        
      int first[] = {
        5,10,15,20,25};
      int second[] = {
        50,40,30,20,10};
      std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
      std::vector<int>::iterator it;
    
      std::sort (first,first+5);     //  5 10 15 20 25
      std::sort (second,second+5);   // 10 20 30 40 50
    
      it=std::set_intersection (first, first+5, second, second+5, v.begin());
                                                   // 10 20 0  0  0  0  0  0  0  0
      v.resize(it-v.begin());                      // 10 20
    
      std::cout << "The intersection has " << (v.size()) << " elements:\n";
      for (it=v.begin(); it!=v.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }

链接：[set\_difference][set_difference].

// set_difference example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::set_difference, std::sort
    #include <vector>       // std::vector
    
    int main () {
        
      int first[] = {
        5,10,15,20,25};
      int second[] = {
        50,40,30,20,10};
      std::vector<int> v(10);                      // 0  0  0  0  0  0  0  0  0  0
      std::vector<int>::iterator it;
    
      std::sort (first,first+5);     //  5 10 15 20 25
      std::sort (second,second+5);   // 10 20 30 40 50
    
      it=std::set_difference (first, first+5, second, second+5, v.begin());
                                                   //  5 15 25  0  0  0  0  0  0  0
      v.resize(it-v.begin());                      //  5 15 25
    
      std::cout << "The difference has " << (v.size()) << " elements:\n";
      for (it=v.begin(); it!=v.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }

# 关于第五个迭代器参数 #

在上面的案例中，第五的参数为v.begin()，这要求容器v必须先被分配好了足够的空间。如果v为空则不行。于是可以使用模板迭代器**ostream\_iterator**和**insert\_iterator**来解决问题.

## 使用ostream\_iterator直接输出 ##

// set_union example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::set_union, std::sort
    #include <vector>       // std::vector
    #include<string>
    #include<iterator>
    #include<algorithm>
    using namespace std;
    int main() {
        
    		vector<string> set1{
         "buffoon","thinkers","for","heavy","can","for" };
    		vector<string> set2{
         "metal","any","food","elegant","deliver","for" };
    		vector<string> result;
    		vector<string>::iterator it;
    		ostream_iterator<string, char> out(cout, " ");
    	//使用前必须先排序
    	sort(set1.begin(), set1.end());     
    	sort(set2.begin(), set2.end());   
    
    	copy(set1.begin(), set1.end(),out);//buffoon can for for heavy thinkers
    	cout << "" << endl;
    	copy(set2.begin(), set2.end(),out);//any deliver elegant food for metal
    	cout << "" << endl;
    
    	set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
    	//并集结果：any buffoon can deliver elegant food for for heavy metal thinkers
    	return 0;
    }

## 使用insert\_iterator插入到新的容器中 ##

// set_union example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::set_union, std::sort
    #include <vector>       // std::vector
    #include<string>
    #include<iterator>
    #include<algorithm>
    using namespace std;
    int main() {
        
    		vector<string> set1{
         "buffoon","thinkers","for","heavy","can","for" };
    		vector<string> set2{
         "metal","any","food","elegant","deliver","for" };
    		vector<string> result;
    		vector<string>::iterator it;
    		ostream_iterator<string, char> out(cout, " ");
    
    		insert_iterator<vector<string> > inserter(result,result.begin());
    
    	//使用前必须先排序
    	sort(set1.begin(), set1.end());     
    	sort(set2.begin(), set2.end());   
    
    	copy(set1.begin(), set1.end(),out);//buffoon can for for heavy thinkers
    	cout << "" << endl;
    	copy(set2.begin(), set2.end(),out);//any deliver elegant food for metal
    	cout << "" << endl;
    
    	//将求并集的结果放入result
    	set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), inserter);
    
    	copy(result.begin(), result.end(), out);
    	//并集结果：any buffoon can deliver elegant food for for heavy metal thinkers
    	return 0;
    }

[set_union]: http://www.cplusplus.com/reference/algorithm/set_union/?kw=set_union
[set_intersection]: http://www.cplusplus.com/reference/algorithm/set_intersection/
[set_difference]: http://www.cplusplus.com/reference/algorithm/set_difference/