STL算法-交集,并集,差集,對稱差

學數學時我們知道人集合的概念,所謂集合就是符合某個條件的一堆元素.針對它們做的最多的操作就是求交集,并集,差集,對稱差集.不過集合有個特性就是不能有重複的元素.

而STL中的算法中的交并集,所用到的容器不一定要是不能有重複元素.并集等的結果是排好序的一個集合.預設是通過<來比較.是以按照預設操作容器的元素必須可以進行運算符<的操作,如果是自定義類型必須重載運算符<.當然也可以通過傳一個函數對象實作元素的比較功能.

下面來舉幾個簡單的例子看下

該例子針對集合one,two做交,并集等操作,結果儲存到result中

#include <algorthm> //用STL的算法需要引用此頭檔案

#include <set>

#include <vector>

using namespace std;

set<int> one;

one.insert(11);

one.insert(22);

one.insert(33);

set<int> two;

two.insert(11);

two.insert(44);

two.insert(55);

vector<int> result;

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

vector<int>: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是共同元素嘛

并集就是把兩個元素所有元素合并到一起嘛,去除掉重複的.

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

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

//此時result中的元素為11 22 33 44 55

差集就是兩個集之間的差. 比如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

對稱差指隻屬于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