c/c++语言开发共享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));  }