STL算法-交集,并集,差集,对称差

http://blog.csdn.net/weiwenhp/article/details/8691463

学数学时我们知道人集合的概念,所谓集合就是符合某个条件的一堆元素.针对它们做的最多的操作就是求交集,并集,差集,对称差集.不过集合有个特性就是不能有重复的元素.

而STL中的算法中的交并集,所用到的容器不一定要是不能有重复元素.并集等的结果是排好序的一个集合.默认是通过<来比较.所以按照默认操作容器的元素必须可以进行运算符<的操作,如果是自定义类型必须重载运算符<.当然也可以通过传一个函数对象实现元素的比较功能.

 

下面来举几个简单的例子看下

该例子针对集合one,two做交,并集等操作,结果保存到result中

#include //用STL的算法需要引用此头文件

#include

#include

using namespace std;

 

set one;

one.insert(11);

one.insert(22);

one.insert(33);

 

set two;

two.insert(11);

two.insert(44);

two.insert(55);

 

vector result;

result.resize( one.size() + two.size() );   //result是用来保存one和two的交,并,差集的.自然要保定它的大小.要能装得下one,two两者元素之和.

vector:iterator retEndPos; //这是那些算法函数返回的结果

 

交集set_intersection

交集就是同时属于两个集合的元素,也就是同时属于one和two的元素.

//该函数返回的结果是所以相同元素插入到result后,最后一个元素的迭代器

retEndPos = set_intersection( one.begin(), one.end(), two.begin(), two.end() , result.begin());

result.resize( retEndPos - result.begin() ) ; //重新调整result的大小,使其大小刚好等于并集元素个数.

//此时result中的元素是11,one和two中只有11是共同元素嘛

 

并集set_union

并集就是把两个元素所有元素合并到一起嘛,去除掉重复的.

retEndPos = set_union( one.begin(), one.end(), two.begin(), two.end() , result.begin());

result.resize( retEndPos - result.begin() ) ;

//此时result中的元素为11 22 33 44 55

 

差集set_difference

差集就是两个集之间的差. 比如one - two就是只属于one但不属于two的元素,也就是去掉one中与two相同的元素.反过来two - one就是去掉two中与one相同的元素.

retEndPos = set_difference( one.begin(), one.end(), two.begin(), two.end() , result.begin());

result.resize( retEndPos - result.begin() ) ;  //此时result中元素为 22 33

retEndPos = set_difference( two.begin(), two.end(), one.begin(), one.end() , result.begin());  //one 与two的位置互换了

result.resize( retEndPos - result.begin() ) ; //此时result中元素为 44 55

 

对称差集set_symmetric_difference

对称差指只属于one或two,但不同时属于one和two的.实际上就是one和two的并集 与 one和two交集的 差集

retEndPos = set_symmetric_difference( one.begin(), one.end(), two.begin(), two.end() , result.begin());

result.resize( retEndPos - result.begin() ) ; //此时result中元素为 22 33 44 55