std::ranges:: find_end

From cppreference.net

Definiert im Header `<algorithm>`
Aufrufsignatur
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 > 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 und proj2 entsprechend. Die projizierten Elemente werden mit dem binären Prädikat pred verglichen.

2) Gleich wie (1) , verwendet jedoch 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ürde.

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.

Inhaltsverzeichnis

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 suchenden Elemente definiert (auch needle genannt)
r1	-	der Bereich der zu untersuchenden Elemente (auch haystack genannt)
r2	-	der Bereich der zu suchenden Elemente (auch needle 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

Rückgabewert

1) ranges:: subrange < I1 > { } wertinitialisiert mit Ausdruck { i, i + ( i == last1 ? 0 : ranges:: distance ( first2, last2 ) ) } das das letzte Vorkommen der Sequenz

first2

last2

im Bereich

first1

last1

bezeichnet (nach Projektionen mit proj1 und proj2 ). Falls

first2

last2

leer ist oder keine solche Sequenz gefunden wird, ist der Rückgabewert effektiv initialisiert mit { last1, last1 } .

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

Komplexität

Höchstens $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.

Hinweise

Eine Implementierung kann die Effizienz der Suche verbessern, wenn die Eingabe-Iteratoren das Konzept 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 nicht die theoretische Komplexität des Worst-Case.

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

Beispiel

Diesen Code ausführen

#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) { // verwendet ein binäres Prädikat
            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); }); // projiziert den 2. Bereich
    print(secret, found4);
    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => nicht gefunden
}

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)
                ^^^^^

Siehe auch

ranges::find_last ranges::find_last_if ranges::find_last_if_not (C++23) (C++23) (C++23)	findet das letzte Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	findet das erste Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt)
ranges::find_first_of (C++20)	sucht nach einem beliebigen Element aus einer Menge von Elementen (Algorithmus-Funktionsobjekt)
ranges::adjacent_find (C++20)	findet die ersten zwei benachbarten Elemente, die gleich sind (oder ein gegebenes Prädikat erfüllen) (Algorithmus-Funktionsobjekt)
ranges::search (C++20)	sucht nach dem ersten Vorkommen eines Bereichs von Elementen (Algorithmus-Funktionsobjekt)
ranges::search_n (C++20)	sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Algorithmus-Funktionsobjekt)
find_end	findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktions-Template)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: find_end

Inhaltsverzeichnis

Parameter

Rückgabewert

Komplexität

Hinweise

Mögliche Implementierung

Beispiel

Siehe auch