std::ranges::partition_point

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 = {} );

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 = {} );

Проверяет разделённый на части (как если бы с помощью ranges::partition) диапазон [first, last) или r и находит конец первой части, то есть проецируемый элемент, который не удовлетворяет pred или last, если все проецируемые элементы удовлетворяют pred.

Функциональные объекты, описанные на этой странице, являются функциональными объектами алгоритмов (неофициально называемыми ниеблоидами), то есть:

• При вызове любого из них нельзя указывать явные списки аргументов шаблона.
• Ни один из них не виден для поиска, зависящего от аргументов.
• Если любой из них найден с помощью обычного неквалифицированного поиска как имя слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

Возвращаемое значение

Итератор за концом первой части в пределах [first, last) или итератор, равный last, если все проецируемые элементы удовлетворяют pred.

Сложность

При заданном N = ranges::distance(first, last) выполняет O(log N) применений предиката pred и проекции proj.

Однако, если сентинелы не моделируют std::sized_sentinel_for<I>, количество приращений итератора составляет O(N).

Примечания

Этот алгоритм является более общей формой ranges::lower_bound, который можно выразить через ranges::partition_point с предикатом [&](auto const& e) { return std::invoke(pred, e, value); });.

Пример

#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());
}

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

См. также