STL算法_set相關算法篇

set相關算法所接受的set，必須是有序區間，元素值可以重復出現。

1）set_union算法：可構造S1，S2之並集。即構造出S1並S2，此集合內含S1或S2內的每一個元素。S1、S2及其並集都是以排序區間表示。返回值是一個迭代器，指向輸出區間的尾端。它是一種穩定操作，其輸入區間內的每個元素的相對順序不會改變。因S1和S2元素不唯一，如果某個值在S1中出現n次，在S2中出現m次，則該值在此算法輸出中出現max(m,n)次。其中n個來自S1，剩下的來自S2。

// set_union算法用來構造S1和S2之並集。即它能構造出集合S1US2，此集合內含S1或S2內的每一個元素。S1、S2及其並集
// 都是以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。
// 並集，求存在於[first1,last2)或存在於[first2,last2)的所有元素
// 注意：set是一種sorted range。這是以下算法的前提
// 版本1
template 
_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區）記錄於目標區，
    // 然後移動A區迭代器使之前進；同時間之另一個區迭代器不動。然後進行新一
    // 次的比大小，記錄小值，迭代器移動...直到兩區中有一區到達尾端。如果元
    // 素相等，去S1者記錄與目標區，並同時移動兩個迭代器。
    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));
}
// 版本2
template 
_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));
}

2）set_intersection算法：可構造S1，S2之交集。即構造出S1交S2，此集合內含同時出現於S1和S2內的每一個元素。S1，S2及其交集都是以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它也是一種穩定操做。因S1和S2元素不唯一，如果某個值在S1中出現n次，在S2中出現m次，則該值在此算法輸出中出現min(m,n)次。其全部來自S1。

// set_intersection算法用來構造S1和S2之交集。即構造出的集合含同時出現於S1和S2內的每一個元素。
// S1，S2及其交集都是以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它是穩定操作。
// 交集：求存在於[first1,last1)且存在於[first2,last2)的所有元素
// 注意：set是一種sorted range。這是算法的前提。
// 版本1
template 
_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;
    }
  return __result;
}
// 版本2
template 
_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;
}

3）set_difference算法：可構造S1，S2之差集。即它能夠構造出S1差S2，此集合內含“出現於S1但不出現與S2”的每一個元素。S1，S2及其交集都是以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它也是一種穩定的操作。因S1和S2元素不唯一，如果某個值在S1中出現n次，在S2中出現m次，則該值在此算法輸出中出現max(n-m,0)次。其全部來自S1。

// set_difference算法用來構造S1，S2之差集。即它能構造出S1-S2，此集合內含出現於S1但不出現與S2的每一個元素
// S1，S2及其交集都是以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它是穩定操作。
// 差集：求存在於[first1,last1)且不存在與[first2,last2)的所有元素
// 注意：set是一種sorted ranage。這是以下算法的前提。
// 版本1
template 
_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);
}
// 版本2
template 
_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);
}

4）set_symmetric_difference算法：可構造S1、S2之對稱差，即（S1差S2）並（S2差S1），此集合內含出現於S1但不出現與S2以及出現於S2但不出現於S1的每一個元素。S1，S2及其對稱差集都以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它也是穩定排序。因S1和S2元素不唯一，如果某個值在S1中出現n次，在S2中出現m次，則該值在此算法輸出中出現abs|m-n|次。如果n > m，輸出區間內的最後n-m個元素直接有S1復制而來，如果n < m，則輸出區間內的最後m-n個元素由S2復制而來。

// set_symmetric_difference算法用來可構造S1、S2之對稱差，即（S1差S2）並（S2差S1），
// 此集合內含出現於S1但不出現與S2以及出現於S2但不出現於S1的每一個元素。S1，S2及其對
// 稱差集都以排序區間表示。返回值為一個迭代器，指向輸出區間的尾端。它也是穩定排序。
// 對稱差集，求存在於[first1,last1)且不存在於[first2,last2)的所有元素，以及存在於
// [first2,last2)且不存在於[first1,lase1)的所有元素。
// 注意：上述定義只有在元素值獨一無二的情況下才成立。如果將set一般化，允許出現重復
// 元素，那麼set-symmetrix-difference的定義時：如果某值在[first1,last1)出現n次，在
// [first2,last2)出現m次，那麼它在result range中應該出現abs(n-m)次。
// 注意：set是一種sorted range。這是算法的前提。
// 版本1
template 
_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)
    // 在兩區間內分別移動迭代器。當兩區間內的元素相等，就讓兩區間同時前進；
    // 當兩區間內的元素不等，就記錄較小值於目標區，並令較小值所在區間前進
    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));
}
// 版本2
template 
_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));
}