首页 > 代码库 > stl_algorithm算法之分割算法

stl_algorithm算法之分割算法

分割算法:

7.49、template <class InputIterator, class UnaryPredicate>
bool is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  while (first!=last && pred(*first)) { //第一个while找到左边所有连续的符合pred函数的元素
    ++first;
  }
  while (first!=last) { //从第一个while获得的最后一个不符合pred函数的元素开始。
    if (pred(*first)) return false; //如果还存在满足pred函数的元素就返回FALSE,
    ++first;
  }
  return true;
}
//所做的事情是:判断整个区间的元素是否是按照左右互不相同的规则进行分割的。
//这个函数经常会和其他函数进行交互使用。

 

7.50、template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
                   BidirectionalIterator last, 
                   UnaryPredicate pred)
{
  while (first!=last) {
    while (pred(*first)) { 
      ++first;
      if (first==last) return first; 
    }
    do { 
      --last; 
      if (first==last) return first; 
     } while (!pred(*last)); 
    swap (*first,*last); 
    ++first; 
  }
  return first;
}
//所做的事情是:将元素按照pred函数区分开,返回的是不符合pred函数条件的first。

 

7.51、template <class InputIterator, class OutputIterator1,
class OutputIterator2, class UnaryPredicate pred>
pair<OutputIterator1,OutputIterator2>
partition_copy (InputIterator first, InputIterator last,
         OutputIterator1 result_true, OutputIterator2 result_false,
         UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) {
      *result_true = *first; //符合pred函数的元素为result_true
      ++result_true;
    }
    else {
      *result_false = *first; //不符合pred函数的元素为result_false
      ++result_false;
    }
    ++first;
  }
  return std::make_pair (result_true,result_false);
}
//所做的事情是:将其组队。

 

7.52、template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,
                   UnaryPredicate pred)
{
  auto n = distance(first,last);
  while (n>0)
  {
    ForwardIterator it = first;
    auto step = n/2;
    std::advance (it,step);
    if (pred(*it)) 
    { 
      first=++it; n-=step+1; 
    }
    else n=step;
  }
  return first;
}

stl_algorithm算法之分割算法