欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

STL算法_set相关算法篇

程序员文章站 2022-03-24 22:23:28
set相关算法所接受的set,必须是有序区间,元素值可以重复出现。 1)set_union算法:可构造s1,s2之并集。即构造出s1并s2,此集合内含s1或s2内的每一个元素。s1、s2及其并集都是...

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));
}