std::ranges::find_end

Definiert in Header `<algorithm>`
Aufruf-Signatur
template< std::forward_iterator I1, std::sentinel_for<I1> S1, std::forward_iterator I2, std::sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity > erfordert std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2> constexpr ranges::subrange<I1> find_end( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(seit C++20)
template< ranges::forward_range R1, ranges::forward_range R2, class Pred = ranges::equal_to, class Proj1 = std::identity, class Proj2 = std::identity > requires std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2> constexpr ranges::borrowed_subrange_t<R1> find_end( R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(seit C++20)

1) Sucht nach dem letzten Vorkommen der Sequenz [first2, last2) im Bereich [first1, last1), nach Projektion mit proj1 bzw. proj2. Die projizierten Elemente werden mit dem binären Prädikat pred verglichen.

2) Dasselbe wie in (1), verwendet aber r1 als ersten Quellbereich und r2 als zweiten Quellbereich, als ob ranges::begin(r1) als first1, ranges::end(r1) als last1, ranges::begin(r2) als first2 und ranges::end(r2) als last2 verwendet würden.

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.

[bearbeiten] Parameter

first1, last1	-	das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente definiert (auch Haystack genannt)
first2, last2	-	das Iterator-Sentinel-Paar, das den Bereich der zu durchsuchenden Elemente (auch Nadel genannt) definiert
r1	-	der Bereich der zu untersuchenden Elemente (auch Haystack genannt)
r2	-	der zu durchsuchende Bereich von Elementen (auch Nadel genannt)
pred	-	binäres Prädikat zum Vergleichen der Elemente
proj1	-	Projektion, die auf die Elemente im ersten Bereich angewendet wird
proj2	-	Projektion, die auf die Elemente im zweiten Bereich angewendet wird

[bearbeiten] Rückgabewert

1) Ein ranges::subrange<I1>{}, wertinitialisiert mit dem Ausdruck {i, i + (i == last1 ? 0 : ranges::distance(first2, last2))}, das das letzte Vorkommen der Sequenz [first2, last2) im Bereich [first1, last1) (nach Projektionen mit proj1 und proj2) bezeichnet. Wenn [first2, last2) leer ist oder wenn keine solche Sequenz gefunden wird, wird der Rückgabewert effektiv mit {last1, last1} initialisiert.

2) Dasselbe wie in (1), außer dass der Rückgabetyp ranges::borrowed_subrange_t<R1> ist.

[bearbeiten] Komplexität

Höchstens $\scriptsize S\cdot(N-S+1)$ $S\cdot(N-S+1)$ Anwendungen des entsprechenden Prädikats und jeder Projektion, wobei $\scriptsize S$ $S$ gleich ranges::distance(first2, last2) und $\scriptsize N$ $N$ gleich ranges::distance(first1, last1) für (1) ist, oder $\scriptsize S$ $S$ gleich ranges::distance(r2) und $\scriptsize N$ $N$ gleich ranges::distance(r1) für (2) ist.

[bearbeiten] Hinweise

Eine Implementierung kann die Effizienz der Suche verbessern, wenn die Eingabeiteratoren std::bidirectional_iterator modellieren, indem sie vom Ende zum Anfang sucht. Die Modellierung des std::random_access_iterator kann die Vergleichsgeschwindigkeit verbessern. All dies ändert jedoch nichts an der theoretischen Komplexität des Worst-Case.

[bearbeiten] Mögliche Implementierung

struct find_end_fn
{
    template<std::forward_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr ranges::subrange<I1>
        operator()(I1 first1, S1 last1,
                   I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        if (first2 == last2)
        {
            auto last_it = ranges::next(first1, last1);
            return {last_it, last_it};
        }
        auto result = ranges::search(
            std::move(first1), last1, first2, last2, pred, proj1, proj2);
 
        if (result.empty())
            return result;
 
        for (;;)
        {
            auto new_result = ranges::search(
                std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);
            if (new_result.empty())
                return result;
            else
                result = std::move(new_result);
        }
    }
 
    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
    constexpr ranges::borrowed_subrange_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(pred),
                       std::move(proj1), std::move(proj2));
    }
};
 
inline constexpr find_end_fn find_end {};

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>
 
void print(const auto haystack, const auto needle)
{
    const auto pos = std::distance(haystack.begin(), needle.begin());
    std::cout << "In \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" found \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
        << std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}
 
int main()
{
    using namespace std::literals;
    constexpr auto secret{"password password word..."sv};
    constexpr auto wanted{"password"sv};
 
    constexpr auto found1 = std::ranges::find_end(
        secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend());
    print(secret, found1);
 
    constexpr auto found2 = std::ranges::find_end(secret, "word"sv);
    print(secret, found2);
 
    const auto found3 = std::ranges::find_end(secret, "ORD"sv,
        [](const char x, const char y) { // uses a binary predicate
            return std::tolower(x) == std::tolower(y);
        });
    print(secret, found3);
 
    const auto found4 = std::ranges::find_end(secret, "SWORD"sv, {}, {},
        [](char c) { return std::tolower(c); }); // projects the 2nd range
    print(secret, found4);
 
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => not found
}

Ausgabe

In "password password word..." found "password" at position [9..17)
             ^^^^^^^^
In "password password word..." found "word" at position [18..22)
                      ^^^^
In "password password word..." found "ord" at position [19..22)
                       ^^^
In "password password word..." found "sword" at position [12..17)
                ^^^^^

[bearbeiten] Siehe auch

ranges::find_lastranges::find_last_ifranges::find_last_if_not (C++23)(C++23)(C++23)	Findet das letzte Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt)[edit]
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	Findet das erste Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt)[edit]
ranges::find_first_of (C++20)	Sucht nach einem der Elemente aus einer Menge von Elementen (Algorithmus-Funktionsobjekt)[edit]
ranges::adjacent_find (C++20)	Findet die ersten beiden benachbarten Elemente, die gleich sind (oder eine gegebene Bedingung erfüllen) (Algorithmus-Funktionsobjekt)[edit]
ranges::search (C++20)	Sucht nach dem ersten Vorkommen eines Elementbereichs (Algorithmus-Funktionsobjekt)[edit]
ranges::search_n (C++20)	Sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt)[edit]
find_end	Findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktionstempelat) [edit]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen