注意事項

• 四種相關算法：并集、交集、差集、對稱差集
• 本章的四個算法要求元素不可以重復并且經過了排序
• 底層接受STL的set/multiset容器作為輸入空間
• 不接受底層為hash_set和hash_multiset兩種容器

并集 set_union

• s1 U s2
• 考慮到s1 和 s2中每個元素都不唯一，如果單個元素在S1中出現了m次，在s2中出現了n次，那么該數值在并集區間內出現的次數是 max(n,m)，假設m小于n。那么m個數來自s1，m-n個數來自s2
• 穩定算法 相對次序不會改變
• 版本一使用 operator <?
• 版本二使用 comp 進行比較
• 注意：set已經排好順序

template <class InputIterator1,class InputIterator2,class OutputIterator>
OutputIterator set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){//如果均沒有到達末尾//在兩個區間內分別移動迭代器，首先將元素較小的數值(假設為A區)記錄于目標區，移動A區迭代器使其前進，同一時間B區迭代器保持不變//如果兩個迭代器指向的元素的大小是一致的，均移動兩個迭代器while(true){//只要兩個區間中有一個到達末尾就需要結束循環//將尚未到達尾端的區間的所有剩余元素拷貝到目的端//此刻的[first1,last1)和[first2，last2)之中有一個是空白的區間if (first1==last1)return std::copy(first2,last2,result);if (first2==last2)return std::copy(first1,last1,result);if (*first1 < *first2){*result = *first1;++first1;} else if(*first1 > *first2){*result = *first2;++first2;} else{ //*first1 == *first2*result = *first1;++first1;++first2;}++result;}}

int main(){int first[] = {5,10,15,20,25};int second[] = {50,40,30,20,10};std::vector<int>v(10);std::vector<int>::iterator it;std::sort(first,first+5);      //5,10,15,20,25std::sort(second,second+5);  //10,20,30,40,50it = std::set_union(first,first+5,second,second+5,v.begin()); // 5 10 15 20 25 30 40 50  0  0v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50std::cout << "The union has " << (v.size()) << " elements:\n";for (auto tmp : v) {std::cout << tmp << " ";}std::cout << std::endl;
}///Users/chy/Desktop/exceptional/cmake-build-debug/exceptional
//The union has 8 elements:
//5 10 15 20 25 30 40 50
//
//Process finished with exit code 0

交集 set_intersection

• 構造元素的交集，即同時出現在兩個集合中的元素
• 返回迭代器指向輸出區間的尾端?
• 考慮到s1 和 s2中每個元素都不唯一，如果單個元素在S1中出現了m次，在s2中出現了n次，那么該數值在交集區間內出現的次數是 min(n,m)
• 穩定算法 相對次序不會改變
• 版本一使用 operator <?
• 版本二使用 comp 進行比較
• 注意：set已經排好順序

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

int main(){int first[] = {5,10,15,20,25};int second[] = {50,40,30,20,10};std::vector<int>v(10);std::vector<int>::iterator it;std::sort(first,first+5);      //5,10,15,20,25std::sort(second,second+5);  //10,20,30,40,50it = std::set_intersection(first,first+5,second,second+5,v.begin()); // 10 20 0  0  0  0  0  0  0  0v.resize(it-v.begin()); // 10 20std::cout << "The intersection has " << (v.size()) << " elements:\n";for (auto tmp : v) {std::cout << tmp << " ";}std::cout << std::endl;
}///Users/chy/Desktop/exceptional/cmake-build-debug/exceptional
//The union has 2 elements:
//10 20
//
//Process finished with exit code 0

差集 set_difference

• ?構造集合S1 - S2。此集合包含出現于S1但是不出現于S2的每一個元素
• 返回迭代器指向輸出區間的尾端?
• 考慮到s1 和 s2中每個元素都不唯一，如果單個元素在S1中出現了m次，在s2中出現了n次，那么該數值在交集區間內出現的次數是 max(m-n，0)
• 穩定算法 相對次序不會改變
• 版本一使用 operator <?
• 版本二使用 comp 進行比較
• 注意：set已經排好順序

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;++result;++first1;}else if (*first1 > *first2){++first2;} else{++first1;++first2;}}return std::copy(first1,last1,result);
}

int main(){int first[] = {5,10,15,20,25};int second[] = {50,40,30,20,10};std::vector<int>v(10);std::vector<int>::iterator it;std::sort(first,first+5);      //5,10,15,20,25std::sort(second,second+5);  //10,20,30,40,50it = std::set_difference(first,first+5,second,second+5,v.begin()); // 5 15 25  0  0  0  0  0  0  0v.resize(it-v.begin()); // 5 15 25std::cout << "The difference has " << (v.size()) << " elements:\n";for (auto tmp : v) {std::cout << tmp << " ";}std::cout << std::endl;
}///Users/chy/Desktop/exceptional/cmake-build-debug/exceptional
//The union has 2 elements:
//5 15 25
//
//Process finished with exit code 0

對稱差集 set_symmetric_difference

• 構造出 (s1 - s2) U (s2 - s1)
• 打印出現于s1但是不出現于s2 以及出現于s2但是不出現于s1的每一個元素
• 考慮到s1 和 s2中每個元素都不唯一，如果單個元素在S1中出現了m次，在s2中出現了n次，那么該數值在交集區間內出現的次數是 | n - m|
• 穩定算法 相對次序不會改變
• 版本一使用 operator <?
• 版本二使用 comp 進行比較
• 注意：set已經排好順序

template <class InputIterator1,class InputIterator2,class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result){while (true){//以下兩個條件不會同時成立 即if (first1 == last1){return std::copy(first2,last2,result);}if (first2 == last2){return std::copy(first1,last1,result);}if (*first1 < *first2){*result = *first1;++result;++first1;}else if (*first1 > *first2){*result = *first2;++result;++first2;} else{++first1;++first2;}}
}

int main(){int first[] = {5,10,15,20,25};int second[] = {50,40,30,20,10};std::vector<int>v(10);std::vector<int>::iterator it;std::sort(first,first+5);      //5,10,15,20,25std::sort(second,second+5);  //10,20,30,40,50it = std::set_symmetric_difference(first,first+5,second,second+5,v.begin()); //5 15 25 30 40 50  0  0  0  0v.resize(it-v.begin()); // 5 15 25 30 40 50std::cout << "The set_symmetric_difference has " << (v.size()) << " elements:\n";for (auto tmp : v) {std::cout << tmp << " ";}std::cout << std::endl;
}///Users/chy/Desktop/exceptional/cmake-build-debug/exceptional
//The union has 2 elements:
//5 15 25 30 40 50 
//
//Process finished with exit code 0