std::partition_point

template <class ForwardIterator, class UnaryPredicate>  ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,                                   UnaryPredicate pred);

Get partition point

Returns an iterator to the first element in the partitioned range [first,last) for which pred is not true, indicating its partition point.

The elements in the range shall already be partitioned, as if partition had been called with the same arguments.

该函数通过比较已排序范围中的非连续元素来优化比较次数，这对于随机访问迭代器特别高效。

此函数模板的行为等同于

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

参数

first, last: Forward iterators to the initial and final positions of the partitioned sequence. The range checked is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
pred: Unary function that accepts an element in the range as argument, and returns a value convertible to bool. The value returned indicates whether the element goes before the partition point (if true, it goes before; if false goes at or after it).
该函数不得修改其参数。
This can either be a function pointer or a function object.

返回值

An iterator to the first element in the partitioned range [first,last) for which pred is not true, or last if it is not true for any element.

示例

// partition_point example
#include <iostream>     // std::cout
#include <algorithm>    // std::partition, std::partition_point
#include <vector>       // std::vector

bool IsOdd (int i) { return (i%2)==1; }

int main () {
  std::vector<int> foo {1,2,3,4,5,6,7,8,9};
  std::vector<int> odd;

  std::partition (foo.begin(),foo.end(),IsOdd);

  auto it = std::partition_point(foo.begin(),foo.end(),IsOdd);
  odd.assign (foo.begin(),it);

  // print contents of odd:
  std::cout << "odd:";
  for (int& x:odd) std::cout << ' ' << x;
  std::cout << '\n';

  return 0;
}

输出

odd: 1 3 5 7 9

复杂度

On average, logarithmic in the distance between first and last: Performs approximately log₂(N)+2 element comparisons (where N is this distance).
对于非随机访问迭代器，迭代器前进本身会在平均情况下产生额外的线性复杂度。

数据竞争

Some of the objects in the range [first,last) are accessed.

异常

如果元素比较或迭代器操作引发异常，则抛出。
请注意，无效参数会导致未定义行为。

另见

partition: 将范围划分为两部分（函数模板）

find_if_not: 在范围中查找元素（否定条件）（函数模板）

binary_search: 测试值是否存在于已排序序列中（函数模板）