std::ranges::is_sorted_until
| 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< std::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order< |
(2) | (seit C++20) |
Untersucht den Bereich [first, last) und findet den größten Bereich, der bei first beginnt und in dem die Elemente in nicht absteigender Reihenfolge sortiert sind.
Eine Sequenz ist in Bezug auf einen Komparator comp sortiert, wenn für jeden Iterator it, der auf die Sequenz zeigt, und jede nicht-negative Ganzzahl n, so dass it + n ein gültiger Iterator ist, der auf ein Element der Sequenz zeigt, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) zu false ausgewertet wird.
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 |
[bearbeiten] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente für die obere Grenze der Sortierung definiert |
| r | - | der Bereich, für den die obere Grenze der Sortierung gesucht wird |
| comp | - | Vergleichsfunktion, die auf die projizierten Elemente angewendet wird |
| proj | - | Projektion, die auf die Elemente angewendet wird |
[bearbeiten] Rückgabewert
Die obere Grenze des größten Bereichs, der bei first beginnt und in dem die Elemente in nicht absteigender Reihenfolge sortiert sind. Das heißt, der letzte Iterator it, für den der Bereich [first, it) sortiert ist.
[bearbeiten] Komplexität
Linear zur Distanz zwischen first und last.
[bearbeiten] Mögliche Implementierung
struct is_sorted_until_fn { template<std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_strict_weak_order<std::projected<I, Proj>> Comp = ranges::less> constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const { if (first == last) return first; for (auto next = first; ++next != last; first = next) if (std::invoke(comp, std::invoke(proj, *next), std::invoke(proj, *first))) return next; return first; } template<ranges::forward_range R, class Proj = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less> constexpr ranges::borrowed_iterator_t<R> operator()(R&& r, Comp comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::ref(comp), std::ref(proj)); } }; inline constexpr is_sorted_until_fn is_sorted_until; |
[bearbeiten] Hinweise
ranges::is_sorted_until gibt für leere Bereiche und Bereiche der Länge eins einen Iterator zurück, der gleich last ist.
[bearbeiten] Beispiel
#include <array> #include <algorithm> #include <iostream> #include <iterator> #include <random> int main() { std::random_device rd; std::mt19937 g {rd()}; std::array nums {3, 1, 4, 1, 5, 9}; constexpr int min_sorted_size = 4; int sorted_size = 0; do { std::ranges::shuffle(nums, g); const auto sorted_end = std::ranges::is_sorted_until(nums); sorted_size = std::ranges::distance(nums.begin(), sorted_end); std::ranges::copy(nums, std::ostream_iterator<int>(std::cout, " ")); std::cout << " : " << sorted_size << " leading sorted element(s)\n"; } while (sorted_size < min_sorted_size); }
Mögliche Ausgabe
4 1 9 5 1 3 : 1 leading sorted element(s) 4 5 9 3 1 1 : 3 leading sorted element(s) 9 3 1 4 5 1 : 1 leading sorted element(s) 1 3 5 4 1 9 : 3 leading sorted element(s) 5 9 1 1 3 4 : 2 leading sorted element(s) 4 9 1 5 1 3 : 2 leading sorted element(s) 1 1 4 9 5 3 : 4 leading sorted element(s)
[bearbeiten] Siehe auch
| (C++20) |
Prüft, ob ein Bereich aufsteigend sortiert ist (Algorithmus-Funktionsobjekt) |
| (C++11) |
Findet den größten sortierten Teilbereich (Funktionstemplate) |
