首页 > 代码库 > stl_algorithm算法之融合算法

stl_algorithm算法之融合算法

融合算法:

7.64、template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (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);
    *result++ = (*first2 < *first1)? *first2++ : *first1++; //使用op< 进行比较排序。
  }
}
//第一个区间和第二个区间进行融合,融合之后的result是排序好的。

 

7.65、inplace_merge //合并

7.66、template <class InputIterator1, class InputIterator2>
bool includes (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2)
{
  while (first2!=last2) {
    if ( (first1==last1) || (*first2 < *first1) ) return false;
    if (!(*first1<*first2)) ++first2;
    ++first1;
  }
  return true;
}
//所做的事情是:判断第一个区间是否包含在第二个区间中。前提是这两个区间是已经排序好的。

 

7.67、template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (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; ++first1; 
    }
    else if (*first2<*first1) 
    { 
      *result = *first2; ++first2; 
    }
    else 
    { 
      *result = *first1; ++first1; ++first2; 
    }
    ++result;
  }
  return result;
}
//所做的事情是:合并两个区间并排好序.

 

7.68、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 (*first2 < *first1) 
      ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}
//所做的事情是:获得两个区间的交集,返回这个集合。

 

7.69、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 (*first2<*first1) 
      ++first2;
    else 
    { 
      ++first1; ++first2;
    }
  }
  return std::copy(first1,last1,result);
}
//所做的事情是:获得第一个区间中与第二个区间不同的元素。

 

7.70、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 (*first2<*first1) 
    { 
      *result = *first2; ++result; ++first2;
    }
    else 
    { 
      ++first1; ++first2; 
    }
  }
}
//所做的事情是:获取两个区间中不同的元素。

stl_algorithm算法之融合算法