坊網(wǎng)站建設(shè)seo快速排名工具
? ? ? ? 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));
}
?