stdpartition_point(3)
std::partition_point - std::partition_point
Synopsis
Defined in header <algorithm>
template< class ForwardIt, class UnaryPredicate > (since C++11)
ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p ); (1) (until C++20)
template< class ForwardIt, class UnaryPredicate > (since C++20)
constexpr ForwardIt partition_point( ForwardIt first, ForwardIt last, UnaryPredicate p );Examines the partitioned (as if by std::partition) range [first, last) and locates the end of the first partition, that is, the first element that does not satisfy p or last if all elements satisfy p.
Parameters
first, last - the partitioned range of elements to examine
Type requirements
ForwardIt must meet the requirements of LegacyForwardIterator.
UnaryPredicate must meet the requirements of Predicate.
Return value
The iterator past the end of the first partition within [first, last) or last if all elements satisfy p.
Complexity
Given N = std::distance(first, last), performs O(log N) applications of the predicate p. However, for non-LegacyRandomAccessIterators, the number of iterator increments is O(N).
Notes
This algorithm is a more general form of std::lower_bound, which can be expressed in terms of std::partition_point with the predicate [&](auto const& e) { return e < value; });.
Example
// Run this code
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
int main()
{
std::array<int, 9> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
auto is_even = [](int i) { return i % 2 == 0; };
std::partition(v.begin(), v.end(), is_even);
auto p = std::partition_point(v.begin(), v.end(), is_even);
std::cout << "Before partition:\n ";
std::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " "));
std::cout << "\nAfter partition:\n ";
std::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " "));
}
Output:
See also
is_sorted checks whether a range is sorted into ascending order