function template
<algorithm>

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.

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for random-access iterators.

The behavior of this function template is equivalent to:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
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;
}


Parameters

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).
The function shall not modify its argument.
This can either be a function pointer or a function object.

Return value

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.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
// 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;
}


Output:
odd: 1 3 5 7 9

Complexity

On average, logarithmic in the distance between first and last: Performs approximately log2(N)+2 element comparisons (where N is this distance).
On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

Data races

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

Exceptions

Throws if either an element comparison or an operation on an iterator throws.
Note that invalid arguments cause undefined behavior.

See also

partition
Partition range in two (function template )
find_if_not
Find element in range (negative condition) (function template )
binary_search
Test if value exists in sorted sequence (function template )

C++