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: 測試值是否存在於已排序序列中（函式模板）