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

Examine la plage partitionnée (comme si par ranges::partition) la plage [first, last) ou r et localise la fin de la première partition, c'est-à-dire l'élément projeté qui ne satisfait pas pred ou last si tous les éléments projetés satisfont pred.

Les entités de type fonction décrites sur cette page sont objets fonctions d'algorithmes (informellement connus sous le nom de niebloids), c'est-à-dire :

• Les listes explicites d'arguments de modèle ne peuvent pas être spécifiées lors de l'appel de l'un d'eux.
• Aucun d'eux n'est visible par recherche dépendante des arguments.
• Lorsque l'un d'eux est trouvé par recherche non qualifiée normale en tant que nom à gauche de l'opérateur d'appel de fonction, recherche dépendante des arguments est inhibée.

Paramètres

Valeur de retour

L'itérateur après la fin de la première partition dans [ first , last ) ou l'itérateur égal à last si tous les éléments projetés satisfont pred .

Complexité

Étant donné N = ranges:: distance ( first, last ) , effectue O(log N) applications du prédicat pred et de la projection proj .

Cependant, si les sentinelles ne modélisent pas std:: sized_sentinel_for < I > , le nombre d'incrémentations d'itérateur est O(N) .

Notes

Cet algorithme est une forme plus générale de ranges::lower_bound , qui peut être exprimé en termes de ranges::partition_point avec le prédicat [ & ] ( auto const & e ) { return std:: invoke ( pred, e, value ) ; } ) ; .

Exemple

#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

Voir aussi