std::ranges::partition_point
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, |
(1) | (seit C++20) |
| template< ranges::forward_range R, class Proj = std::identity, |
(2) | (seit C++20) |
Untersucht den partitionierten (als ob 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, wenn alle projizierten Elemente pred erfüllen.
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[edit] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den partiell geordneten Bereich der zu untersuchenden Elemente definiert |
| r | - | der partiell geordnete Bereich, der untersucht werden soll |
| pred | - | Prädikat, das auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[edit] Rückgabewert
Der Iterator hinter dem Ende der ersten Partition innerhalb von [first, last) oder der Iterator gleich last, wenn alle projizierten Elemente pred erfüllen.
[edit] Komplexität
Bei N = ranges::distance(first, last) werden O(log N) Anwendungen des Prädikats pred und der Projektion proj durchgeführt.
Wenn jedoch Sentinels std::sized_sentinel_for<I> nicht modellieren, ist die Anzahl der Iterator-Inkremente O(N).
[edit] Anmerkungen
Dieser Algorithmus ist eine allgemeinere Form von ranges::lower_bound, die sich mit Hilfe von ranges::partition_point mit dem Prädikat [&](auto const& e) { return std::invoke(pred, e, value); }); ausdrücken lässt.
[edit] 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("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()); }
Mögliche Ausgabe
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
[edit] Siehe auch
| (C++20) |
Prüft, ob ein Bereich aufsteigend sortiert ist (Algorithmus-Funktionsobjekt) |
| (C++20) |
Gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist (Algorithmus-Funktionsobjekt) |
| (C++11) |
Findet den Partitionierungspunkt eines partitionierten Bereichs (Funktionstemplate) |
