1、 STL提供了4个set相关的算法，分别是并集（union）、交集（intersection）、差集（difference）和对称差集（symmetric difference），这4个算法接受的set必须是有序区间，都至少接受4个参数，分别表示两个set区间。
2、 set相关算法源代码
//并集，求存在于[first1, last1)或存在于[first2, last2)内的所有元素//注意：输入区间必须是已排序//版本一,默认是operator <操作的排序方式template>OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { //两个区间都尚未到达区间尾端，执行以下操作 while (first1 != last1 && first2 != last2) { /*在两区间内分别移动迭代器，首先将元素较小者(假设为A区)记录在目标区result 移动A区迭代器使其前进；同时另一个区的迭代器不变。然后进行一次新的比较， 记录较小值，移动迭代器...直到两区间中有一个到达尾端。若两区间存在元素相等， 默认记录第一区间的元素到目标区result.*/ if (*first1 < *first2) { *result = *first1; ++first1; } else if (*first2 < *first1) { *result = *first2; ++first2; } else { *result = *first1; ++first1; ++first2; } ++result; } /*只要两区间之中有一个区间到达尾端，就结束上面的while循环 以下将尚未到达尾端的区间剩余的元素拷贝到目标区 此刻，[first1, last1)和[first2, last2)至少有一个是空区间*/ return copy(first2, last2, copy(first1, last1, result));}//版本二,用户根据仿函数comp指定排序规则template OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) { while (first1 != last1 && first2 != last2) { if (comp(*first1, *first2)) { *result = *first1; ++first1; } else if (comp(*first2, *first1)) { *result = *first2; ++first2; } else { *result = *first1; ++first1; ++first2; } ++result; } return copy(first2, last2, copy(first1, last1, result));}//交集，求存在于[first1, last1)且存在于[first2, last2)内的所有元素//注意：输入区间必须是已排序//版本一,默认是operator <操作的排序方式template> OutputIterator set_intersection(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 { *result = *first1; ++first1; ++first2; ++result; } return result;}//版本二,用户根据仿函数comp指定排序规则template OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp) { while (first1 != last1 && first2 != last2) if (comp(*first1, *first2)) ++first1; else if (comp(*first2, *first1)) ++first2; else { *result = *first1; ++first1; ++first2; ++result; } return result;}//差集，求存在于[first1, last1)且不存在于[first2, last2)内的所有元素//注意：输入区间必须是已排序//版本一，默认是operator <操作的排序方式template> 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);}//版本二，用户根据仿函数comp指定排序规则template OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp) { while (first1 != last1 && first2 != last2) if (comp(*first1, *first2)) { *result = *first1; ++first1; ++result; } else if (comp(*first2, *first1)) ++first2; else { ++first1; ++first2; } return copy(first1, last1, result);}//对称差集，求存在于[first1, last1)但不存在于[first2, last2)内的所有元素以及出现在[first2, last2)但不出现在[first1, last1)的所有元素//注意：输入区间必须是已排序//版本一，默认是operator <操作的排序方式template> 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));} //版本二，用户根据仿函数comp指定排序规则template OutputIterator set_symmetric_difference(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result, Compare comp) { while (first1 != last1 && first2 != last2) if (comp(*first1, *first2)) { *result = *first1; ++first1; ++result; } else if (comp(*first2, *first1)) { *result = *first2; ++first2; ++result; } else { ++first1; ++first2; } return copy(first2, last2, copy(first1, last1, result));}
3、 具体例子
#include4、图解上述例子#include #include #include using namespace std;template struct display{ void operator()(const T& x) const{ cout << x << " "; }};int main(){ int ia[] = { 1, 3, 5, 7, 9, 11 }; int ib[] = { 1, 1, 2, 3, 5, 8, 13 }; multiset s1(begin(ia), end(ia)); multiset s2(begin(ib), end(ib)); for_each(s1.begin(), s1.end(), display ()); cout << endl; for_each(s2.begin(), s2.end(), display ()); cout << endl; multiset ::iterator first1 = s1.begin(); multiset ::iterator last1 = s1.end(); multiset ::iterator first2 = s2.begin(); multiset ::iterator last2 = s2.end(); cout << "union of s1 and s2:"; set_union(first1, last1, first2, last2, ostream_iterator (cout, " ")); cout << endl; cout << "intersection of s1 and s2:"; set_intersection(first1, last1, first2, last2, ostream_iterator (cout, " ")); cout << endl; cout << "difference of s1 and s2:"; set_difference(first1, last1, first2, last2, ostream_iterator (cout, " ")); cout << endl; cout << "symmetric differenceof s1 and s2:"; set_symmetric_difference(first1, last1, first2, last2, ostream_iterator (cout, " ")); cout << endl; system("pause"); return 0;}
set_union
set_intersection
set_difference
set_symmetric_difference
