### 前言
? 本節介紹set集合的相關算法，分別是并集set_union，差集set_difference，交集set_intersection
和對稱差集set_symmetric_difference，這是個函數都提供了兩個版本的函數原型：第一個版本是采用默認的排序比較方式operator<；第二個版本是用戶通過仿函數comp自行指定排序方式。注意：這四個算法接受的輸入區間都是有序的，輸出也是有序的。下面對set算法進行剖析，具體注釋詳見源碼，同時給出例子說明該算法的功能。本文源碼摘自SGI STL中的<stl_algo.h>文件。
### set算法源碼剖析
~~~
/*
下面是計算set集合的相關算法，分別是并集set_union，差集set_difference，交集set_intersection
和對稱差集set_symmetric_difference，這是個函數都提供了兩個版本的函數原型
第一個版本是采用默認的排序比較方式 operator<
第二個版本是用戶通過comp自行指定排序方式
注意：這四個算法接受的輸入區間都是有序的，輸出也是有序的
*/
// Set algorithms: includes, set_union, set_intersection, set_difference,
// set_symmetric_difference. All of these algorithms have the precondition
// that their input ranges are sorted and the postcondition that their output
// ranges are sorted.
// 判斷[first1, last1)是否包含[first2, last2),
// 注意: 兩個區間要保證有序,默認排序方式是operator<，若要自行定義排序方式，則調用第二版本;
template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
while (__first1 != __last1 && __first2 != __last2)//遍歷兩個區間
if (*__first2 < *__first1)//first2小于first1表示不包含
return false;//返回FALSE
else if(*__first1 < *__first2)//若first1小于first2
++__first1;//尋找第一個區間下一個位置
else
++__first1, ++__first2;//若first2等于first1,遍歷兩區間的下一位置
return __first2 == __last2;//若第二個區間先到達尾端，則返回TRUE
}
//版本二：用戶通過comp自行指定排序方式
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool,
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first2, *__first1))
return false;
else if(__comp(*__first1, *__first2))
++__first1;
else
++__first1, ++__first2;
return __first2 == __last2;
}
//兩個集合區間的并集，同樣也有兩個版本
//求存在于[first1, last1)或存在于[first2, last2)內的所有元素
//注意：輸入區間必須是已排序
/*
default (1) :默認是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
custom (2) :用戶指定的排序方式
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
*/
//版本一：默認是operator<操作的排序方式
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
//兩個區間都尚未到達區間尾端，執行以下操作
while (__first1 != __last1 && __first2 != __last2) {
/*
在兩區間內分別移動迭代器，首先將元素較小者(假設為A區)記錄在目標區result
移動A區迭代器使其前進；同時另一個區的迭代器不變。然后進行一次新的比較，
記錄較小值，移動迭代器...直到兩區間中有一個到達尾端。若兩區間存在元素相等，
默認記錄第一區間的元素到目標區result.
*/
if (*__first1 < *__first2) {//first1小于first2
*__result = *__first1;//則result初始值為first1
++__first1;//繼續第一個區間的下一個元素位置
}
else if (*__first2 < *__first1) {//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 <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool,
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
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));
}
/*例子:
#include <iostream> // std::cout
#include <algorithm> // std::set_union, std::sort
#include <vector> // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_union (first, first+5, second, second+5, v.begin());
// 5 10 15 20 25 30 40 50 0 0
v.resize(it-v.begin()); // 5 10 15 20 25 30 40 50
std::cout << "The union has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
The union has 8 elements:
5 10 15 20 25 30 40 50
*/
//兩個集合區間的交集，同樣也有兩個版本
//求存在于[first1, last1)且存在于[first2, last2)內的所有元素
//注意：輸入區間必須是已排序，輸出區間的每個元素的相對排序和第一個區間相對排序相同
/*
default (1) :默認是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
custom (2) :用戶指定的排序方式
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
*/
//版本一：默認是operator<操作的排序方式
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
//若兩個區間都尚未到達尾端，則執行以下操作
while (__first1 != __last1 && __first2 != __last2)
//在兩個區間分別移動迭代器，直到遇到相等元素，記錄到目標區
//繼續移動迭代器...直到兩區間之中有到達尾端
if (*__first1 < *__first2) //第一個區間元素小于第二區間元素
++__first1;//移動第一區間的迭代器，此時第二區間的迭代器不變
else if (*__first2 < *__first1) //第二區間的元素小于第一區間元素
++__first2;//移動第二區間元素，此時第一區間的迭代器不變
else {//若第一區間元素等于第二區間元素
*__result = *__first1;//按第一區間的相對排序記錄到目標區
//分別移動兩區間的迭代器
++__first1;
++__first2;
//更新目標區迭代器，以便繼續記錄元素
++__result;
}
//若有區間到達尾部，則停止while循環
//此時，返回目標區
return __result;
}
//版本二：用戶根據仿函數comp指定排序規則
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool,
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2))
++__first1;
else if (__comp(*__first2, *__first1))
++__first2;
else {
*__result = *__first1;
++__first1;
++__first2;
++__result;
}
return __result;
}
/*例子：
#include <iostream> // std::cout
#include <algorithm> // std::set_intersection, std::sort
#include <vector> // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_intersection (first, first+5, second, second+5, v.begin());
// 10 20 0 0 0 0 0 0 0 0
v.resize(it-v.begin()); // 10 20
std::cout << "The intersection has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output:
The intersection has 2 elements:
10 20
*/
//兩個集合區間的差集，同樣也有兩個版本
//求存在于[first1, last1)但不存在于[first2, last2)內的所有元素
//注意：輸入區間必須是已排序，輸出區間的每個元素的相對排序和第一個區間相對排序相同
/*
default (1) :默認是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
custom (2) :用戶指定的排序方式
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
*/
//版本一：默認是operator<操作的排序方式
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
//若兩個區間都尚未到達尾端，則執行以下操作
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 <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result, _Compare __comp) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool,
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
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);
}
/*例子：
#include <iostream> // std::cout
#include <algorithm> // std::set_difference, std::sort
#include <vector> // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_difference (first, first+5, second, second+5, v.begin());
// 5 15 25 0 0 0 0 0 0 0
v.resize(it-v.begin()); // 5 15 25
std::cout << "The difference has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output：
The difference has 3 elements:
5 15 25
*/
//兩個集合區間的對稱差集，同樣也有兩個版本
//求存在于[first1, last1)但不存在于[first2, last2)內的所有元素以及出現在[first2, last2)但不出現在[first1, last1)
//注意：輸入區間必須是已排序
/*
default (1) :默認是operator<操作的排序方式
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
custom (2) :用戶指定的排序方式
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
*/
//版本一：默認是operator<操作的排序方式
template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
_LessThanComparable);
//若兩個區間都尚未到達尾端，則執行下面的操作
while (__first1 != __last1 && __first2 != __last2)
/*
情況1：若兩區間元素相等，則同時移動兩區間的迭代器.
情況2：若第一區間的元素小于第二區間元素，則把第一區間元素記錄到目標區，且移動第一區間迭代器.
情況3：若第一區間的元素大于第二區間元素，則把第二區間元素記錄到目標區，且移動第二區間迭代器.
*/
if (*__first1 < *__first2) {//屬于情況2
*__result = *__first1;//把第一區間元素記錄到目標區
++__first1;//移動第一區間迭代器.此時第二區間迭代器不變
++__result;
}
else if (*__first2 < *__first1) {//屬于情況3
*__result = *__first2;//把第二區間元素記錄到目標區
++__first2;//移動第二區間迭代器.此時第一區間迭代器不變
++__result;
}
else {//屬于情況1
//同時移動兩區間的迭代器
++__first1;
++__first2;
}
/*
只要兩區間之中有一個區間到達尾端，就結束上面的while循環
以下將尚未到達尾端的區間剩余的元素拷貝到目標區
此刻，[first1, last1)和[first2, last2)至少有一個是空區間
*/
return copy(__first2, __last2, copy(__first1, __last1, __result));
}
//版本二：用戶根據仿函數comp指定排序規則
template <class _InputIter1, class _InputIter2, class _OutputIter,
class _Compare>
_OutputIter
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_OutputIter __result,
_Compare __comp) {
__STL_REQUIRES(_InputIter1, _InputIterator);
__STL_REQUIRES(_InputIter2, _InputIterator);
__STL_REQUIRES(_OutputIter, _OutputIterator);
__STL_REQUIRES_SAME_TYPE(
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
__STL_BINARY_FUNCTION_CHECK(_Compare, bool,
typename iterator_traits<_InputIter1>::value_type,
typename iterator_traits<_InputIter2>::value_type);
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));
}
/*例子：
#include <iostream> // std::cout
#include <algorithm> // std::set_symmetric_difference, std::sort
#include <vector> // std::vector
int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
std::vector<int> v(10); // 0 0 0 0 0 0 0 0 0 0
std::vector<int>::iterator it;
std::sort (first,first+5); // 5 10 15 20 25
std::sort (second,second+5); // 10 20 30 40 50
it=std::set_symmetric_difference (first, first+5, second, second+5, v.begin());
// 5 15 25 30 40 50 0 0 0 0
v.resize(it-v.begin()); // 5 15 25 30 40 50
std::cout << "The symmetric difference has " << (v.size()) << " elements:\n";
for (it=v.begin(); it!=v.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Output：
The symmetric difference has 6 elements:
5 15 25 30 40 50
*/
~~~
參考資料：
《STL源碼剖析》侯捷
- 前言
- 空間配置器
- Traits編程技術
- STL源碼剖析——迭代器
- 全局函數construct(),destroy(),uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n()
- 序列容器之vector
- list容器的排序算法sort()
- 序列容器之list
- 序列容器之deque
- 容器配接器之stack
- 容器配接器之queue
- 容器配接器之priority_queue
- 最大堆heap
- 單向鏈表slist
- RB-Tree(紅黑樹)
- 關聯容器之set
- stl_pair.h學習
- 關聯容器之map
- 關聯容器之multiset
- 關聯容器之multimap
- 散列表hashtable
- stl_hash_fun.h學習
- 關聯容器之hash_set
- 關聯容器之hash_multiset
- 關聯容器之hash_map
- 關聯容器之hash_multimap
- 數值算法stl_numeric.h
- stl_relops.h學習
- 基本算法stl_algobase.h
- STL算法之set集合算法
- STL算法stl_algo.h
- STL算法之sort排序算法
- STL算法之find查找算法
- STL算法之merge合并算法
- STL算法之remove刪除算法
- STL算法之permutation排列組合
- STL函數對象