? ? ? ? STL一共提供了四種與set(集合)相關(guān)的算法，分別是并集(union)、交集(intersection)、差集(difference)、對稱差集(symmetric difference)。

目錄

set_union

set_itersection

set_difference

set_symmetric_difference

---

? ? ? ? 所謂set，可細(xì)分為數(shù)學(xué)上定義的和STL的定義兩種，數(shù)學(xué)上的set允許元素重復(fù)而未經(jīng)排序，例如{1,1,4,6,3},STL的定義(也就是set容器)則要求元素不得重復(fù)，并且經(jīng)過排序，例如{1,3,4,6}。本節(jié)的四個算法所接受的set，必須是有序區(qū)間(sorted range),元素值可重復(fù)出現(xiàn)。換句話說，它們可接受STL的set/multiset容器作為輸入?yún)^(qū)間。

? ? ? ? SGI另外提供了hash_set/hash_multiset兩種容器，以hashtable為底層機制。其內(nèi)的元素并未呈現(xiàn)排序狀態(tài)，所以雖然名稱也是set字樣，缺不可以應(yīng)用于本節(jié)的四個算法。

? ? ? ? 本節(jié)四個算法都至少有四個參數(shù)，分別表現(xiàn)兩個set區(qū)間，以下所有說明都以S1代表第一區(qū)間[first1, last1),以S2代表第二區(qū)間[first2, last2).每一個set算法都提供兩個版本，第二個版本允許用戶指定"a<b"的意義，因為這些算法判斷兩個元素是否相等的依據(jù)，完全靠“小于”運算。

? ? ? ? a <b && b< a 推導(dǎo)出 a==b

? ? ? ? 以下程序測試四個set相關(guān)算法。欲使用它們，必須包含<algorithm>

#include <set>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;template <class T>
struct display {void operator() (const T& x) {cout << x << " ";}
};int main() {int ia1[6] = {1, 3, 5, 7, 9, 11};int ia2[7] = {1, 1, 2, 3, 5, 8, 13};multiset<int> S1(ia1, ia1+6);multiset<int> S2(ia2, ia2+7);for_each(S1.begin(), S1.end(), display<int>());// 1 3 5 7 9 11cout << endl;for_each(S2.begin(), S2.end(), display<int>());// 1 1 2 3 5 8 13cout << endl;auto first1 = S1.begin();auto last1 = S1.end();auto first2 = S2.begin();auto last2 = S2.end();cout <<  "Union of S1 and S2:";set_union(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 1 1 2 3 5 7 9 11 13cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "intersection of S1 and S2:";set_intersection(first1, last1, first2, last2, ostream_iterator<int>(cout, " "));// 1 3 5cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "difference of S1 and S2 (S1-S2): " ;set_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 7 9 11cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "Symmetric difference of S1 and S2: " ;set_symmetric_difference(first1, last1, first2, last2, ostream_iterator<int>(cout, " ")); // 1 2 7 8 9 11 13cout << endl;first1 = S1.begin();first2 = S2.begin();cout << "difference of S2 and S1 (S2-S1): ";set_difference(first2, last2, first1, last1, ostream_iterator<int>(cout, " ")); // 1 2 8 13cout << endl;return 0;
}

? ? ? ? 執(zhí)行結(jié)果如下：

1 3 5 7 9 11 
1 1 2 3 5 8 13 
Union of S1 and S2:1 1 2 3 5 7 8 9 11 13 
intersection of S1 and S2:1 3 5 
difference of S1 and S2 (S1-S2): 7 9 11 
Symmetric difference of S1 and S2: 1 2 7 8 9 11 13 
difference of S2 and S1 (S2-S1): 1 2 8 13 

? ? ? ? 請注意，當(dāng)集合(set)允許重復(fù)元素的存在時，并集、交集、差集、對稱差集的定義，都與直觀定義有些微的不同。例如上述的并集結(jié)果，我們會直觀以為是{1,2,3,5,7,8,9,11,13},而上述的對稱差結(jié)果，我們會直觀以為是{2,7,8,9,11,13},這都是未考慮重復(fù)元素的結(jié)果。以下各小節(jié)會詳細(xì)說明。

set_union

? ? ? ? 算法set_union可構(gòu)造S1、S2之并集。也就是說，它能構(gòu)造出集合，此集合內(nèi)含S1或S2內(nèi)的每一個元素。S1、S2及其并集都是以排序區(qū)間表示。返回值為一個迭代器，指向輸出區(qū)間的尾端。

? ? ? ? 由于S1和S2內(nèi)的每一個元素都不需要唯一，因此，如果某個值在S1出現(xiàn)n次，在S2出現(xiàn)m次，那么該值在輸出區(qū)間會出現(xiàn)max(n,m)次，其中n個來自S1，其余來自S2，在STL set容器內(nèi)，且

? ? ? ? set_union是一種穩(wěn)定(stable)操作，意思是輸入?yún)^(qū)間內(nèi)的每個元素的相對順序都不會改變。set_union有兩個版本，差別在于如何定義某個元素小于另一個元素。第一版本使用operator<進行比較，第二版本采用仿函數(shù)comp進行比較。

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;} else if (*first2 < *first1) {*result = *first2;++first2;} else {*result = *first1;++first1;++first2;}++result;}// 此時[first1,last1)和[first2,last2)至少有一個空白區(qū)間，邊界剩下的是都屬于union的元素return copy(first2, last2, copy(first1, last1, result));
}

? ? ? ? 從以上合并的過程，可以看出主要是利用了set/multi_set經(jīng)過排序的特性，而后對并集的特例化處理。和數(shù)學(xué)定義上的union處理略有差異。

set_itersection

? ? ? ? 算法set_itersection可構(gòu)造S1,S2之交集。也就是說，它能構(gòu)造出集合，此集合內(nèi)含同時出現(xiàn)在S1和S2的每一個元素。S1、S2及其交集都是以排序區(qū)間表示。返回值為一個迭代器，指向輸出區(qū)間的尾端。

? ? ? ? 由于S1和S2內(nèi)的每個元素都不需要唯一，因此，如果某個值在S1出現(xiàn)n次，在S2出現(xiàn)m次，那么該值在輸出區(qū)間出現(xiàn)min(n,m)次，并且全部來自S1.在STL set內(nèi)，且。

? ? ? ? set_itersection是一種穩(wěn)定(stable)的操作，意思是輸出區(qū)間內(nèi)的每個元素的相對順序都和S1內(nèi)的相對順序相同。它有兩個版本，其差異同set_union.其代碼定義如下：

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_itersection(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {++first1;} else if (*first2 < *first1) {++first2;} else { // *first1 == *first2*result = *first1;++first1;++first2;}++result;}return result;
}

? ? ? ? 對照set_itersection和set_union的算法實現(xiàn)，可發(fā)現(xiàn)內(nèi)部迭代器的前進邏輯是一致的；只是輸出時，只講*first1==*first2的數(shù)據(jù)輸出到result。對于邊界情況，因為其中一組迭代器已經(jīng)為空，所以也就沒有了新的元素加入，直接返回了result；

set_difference

? ? ? ? 算法set_difference可構(gòu)造S1、S2只差集。也就是說，它能構(gòu)造集合S1-S2，此集合內(nèi)容"出現(xiàn)于S1但不出現(xiàn)于S2"的每一個元素。S1、S2及其交集都是以排序區(qū)間表示。返回值為一個迭代器，指向輸出區(qū)間的尾端。

????????由于S1和S2內(nèi)的每個元素都不需要唯一，因此，如果某個值在S1出現(xiàn)n次，在S2出現(xiàn)m次，那么該值在輸出區(qū)間出現(xiàn)max(n-m,0)次

? ? ? ? set_difference是一種穩(wěn)定操作，輸出相對順序保持S1內(nèi)的相對順序。代碼如下：

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;++result;} else if (*first2 < *first1) {++first2;} else {++first1;++first2;}}return  copy(first1, last1, result);
}

? ? ? ? 有了前面set_union及set_itersecion算法的經(jīng)驗，可看出迭代器的邏輯還是保留的相同的步伐。只是輸出給result的值，只保留了*first1 < *first2的部分；正好符合S1-S2的特性。

set_symmetric_difference

? ? ? ? 算法set_symmetric_difference可構(gòu)造S1、S2之對稱差集。也就是構(gòu)造出,此集合內(nèi)含"出現(xiàn)在S1但不出現(xiàn)于S2"以及“出現(xiàn)在S2不出現(xiàn)在S1”的每一個元素。

? ? ? ? 有了前三個算法的基礎(chǔ)，很容易得出set_symmetric_difference的結(jié)果包含*first1<*first2,以及*first2-*first1的結(jié)果，同時需要將邊界情況保留。其代碼如下：

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result) {while (first1 != last1 && first2 != last2) {if (*first1 < *first2) {*result = *first1;++first1;++result;} else if (*first2 < *first1) {*result = *first2++first2;++result;} else {++first1;++first2;}}return  copy(first2, last2, copy(first1, last1, result));
}

?