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

Untersucht den partitionierten (wie durch ranges::partition) Bereich [first, last) oder r und lokalisiert das Ende der ersten Partition, d. h. das projizierte Element, das pred nicht erfüllt, oder last falls alle projizierten Elemente pred erfüllen.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

• Explizite Vorlagenargumentlisten können beim Aufruf einer von ihnen nicht angegeben werden.
• Keine von ihnen sind für argumentabhängige Namenssuche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Namenssuche unterbunden.

Parameter

Rückgabewert

Der Iterator nach dem Ende der ersten Partition innerhalb [ first , last ) oder der Iterator gleich last falls alle projizierten Elemente pred erfüllen.

Komplexität

Bei gegebenem N = ranges:: distance ( first, last ) führt O(log N) Anwendungen des Prädikats pred und der Projektion proj durch.

Wenn Sentinels jedoch nicht std:: sized_sentinel_for < I > modellieren, ist die Anzahl der Iterator-Inkremente O(N) .

Hinweise

Dieser Algorithmus ist eine allgemeinere Form von ranges::lower_bound , der mithilfe von ranges::partition_point mit dem Prädikat [ & ] ( auto const & e ) { return std:: invoke ( pred, e, value ) ; } ) ; ausgedrückt werden kann.

Beispiel

#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("Nach Partitionierung, 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 << "Partitionspunkt ist bei " << i << "; v[" << i << "] = " << *pp << '\n';
    print_seq("Erste Partition (alle geraden Elemente): ", v.cbegin(), pp);
    print_seq("Zweite Partition (alle ungeraden Elemente): ", pp, v.cend());
}

Nach Partitionierung, v: 2 4 6 8 5 3 7 1 9
Partitionspunkt ist bei 4; v[4] = 5
Erste Partition (alle geraden Elemente): 2 4 6 8
Zweite Partition (alle ungeraden Elemente): 5 3 7 1 9

Siehe auch