std::ranges::partition_point() algorithm

od C++20

Simplified

// (1)
constexpr I
    partition_point( I first, S last, Pred pred, Proj proj = {} );

// (2)
constexpr ranges::borrowed_iterator_t<R>
    partition_point( R&& r, Pred pred, Proj proj = {} );

The type of arguments are generic and have the following constraints:

• I - std::forward_iterator
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• Pred:
  • (1) - std::indirect_unary_predicate<std::projected<I, Proj>>
  • (2) - std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>>
• Proj - (none)

The Proj template argument has the following default type std::identity for all overloads.

Detailed

// (1)
template<
  std::forward_iterator I,
  std::sentinel_for<I> S,
  class Proj = std::identity,
  std::indirect_unary_predicate<std::projected<I, Proj>> Pred
>
constexpr I
    partition_point( I first, S last, Pred pred, Proj proj = {} );

// (2)
template<
  ranges::forward_range R,
  class Proj = std::identity,
  std::indirect_unary_predicate<std::projected<ranges::iterator_t<R>, Proj>> Pred
>
constexpr ranges::borrowed_iterator_t<R>
    partition_point( R&& r, Pred pred, Proj proj = {} );

Examines the partitioned (as if by ranges::partition) range [first; last) or r and locates the end of the first partition, that is, the projected element that does not satisfy pred or last if all projected elements satisfy pred.

The function-like entities described on this page are niebloids.

Parameters

first last	The range of elements to examine.
r	The range of elements to examine.
pred	The predicate to apply to the projected elements.
proj	The projection to apply to the elements.

Return value

The iterator past the end of the first partition within [first; last) or the iterator equal to last if all projected elements satisfy pred.

Complexity

Given N as ranges::distance(first, last):

Performs O(log(N)) applications of the predicate pred and projection proj.

However, if sentinels don't model std::sized_sentinel_for<I>, the number of iterator increments is O(N).

Exceptions

(none)

Possible implementation

partition_point(1) and partition_point(2)

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
    for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
    std::cout << '\n';
};

int main()
{
    std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto is_even = [](int i) { return i % 2 == 0; };

    std::ranges::partition(v, is_even);
    print_seq("After partitioning, v: ", v.cbegin(), v.cend());

    const auto pp = std::ranges::partition_point(v, is_even);
    const auto i = std::ranges::distance(v.cbegin(), pp);
    std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

    print_seq("First partition (all even elements): ", v.cbegin(), pp);
    print_seq("Second partition (all odd elements): ", pp, v.cend());
}

Notes

This algorithm is a more general form of ranges::lower_bound, which can be expressed in terms of ranges::partition_point with the predicate [&](auto const& e) { return std::invoke(pred, e, value); });.

Examples

Main.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

auto print_seq = [](auto rem, auto first, auto last)
{
    for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
    std::cout << '\n';
};

int main()
{
    std::array v {1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto is_even = [](int i) { return i % 2 == 0; };

    std::ranges::partition(v, is_even);
    print_seq("After partitioning, v: ", v.cbegin(), v.cend());

    const auto pp = std::ranges::partition_point(v, is_even);
    const auto i = std::ranges::distance(v.cbegin(), pp);
    std::cout << "Partition point is at " << i << "; v[" << i << "] = " << *pp << '\n';

    print_seq("First partition (all even elements): ", v.cbegin(), pp);
    print_seq("Second partition (all odd elements): ", pp, v.cend());
}

Possible Output

After partitioning, v: 2 4 6 8 5 3 7 1 9
Partition point is at 4; v[4] = 5
First partition (all even elements): 2 4 6 8
Second partition (all odd elements): 5 3 7 1 9