std::ranges:: partition_point

Untersucht den partitionierten (als ob durch ranges::partition ) Bereich [ first , last ) oder r und ermittelt das Ende der ersten Partition, das heißt 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 Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.

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