std::find_end

Definiert in Header `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(1)	(constexpr seit C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(seit C++17)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(4)	(seit C++17)

Sucht nach dem letzten Vorkommen des Zielbereichs [first2, last2) im Quellbereich [first1, last1).

1) Elemente werden mit operator== verglichen.

2) Elemente werden mit dem angegebenen binären Prädikat p verglichen.

3,4) Gleich wie (1,2), aber ausgeführt gemäß policy.

Diese Überladungen nehmen nur an der Überladungsauflösung teil, wenn der Wert des folgenden Ausdrucks true ist:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(bis C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(seit C++20)

Parameter

first1, last1	-	das Paar von Iteratoren, das den Quell-bereich
definiertfirst2, last2	-	das Paar von Iteratoren, das den Ziel-bereich
definiertp	-	binäres Prädikat, das `true` zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte äquivalent zu Folgendem sein: `bool pred(const Type1 &a, const Type2 &b);` Während die Signatur kein `const &` haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss in der Lage sein, alle Werte des Typs (möglicherweise const) `Type1` und `Type2` unabhängig von der Werteklasse zu akzeptieren (daher ist `Type1 &` nicht erlaubt, ebenso wenig wie `Type1` außer wenn für `Type1` eine Verschiebung gleich einer Kopie ist(seit C++11)). Die Typen `Type1` und `Type2` müssen so sein, dass Objekte der Typen `ForwardIt1` und `ForwardIt2` dereferenziert und dann implizit in `Type1` bzw. `Type2` konvertiert werden können.
policy	-	die zu verwendende Ausführungsstrategie
Typanforderungen
- `ForwardIt1` muss die Anforderungen von LegacyForwardIterator erfüllen.
- `ForwardIt2` muss die Anforderungen von LegacyForwardIterator erfüllen.

Rückgabewert

Iterator auf den Beginn des letzten Vorkommens des Zielbereichs im Quellbereich.

Wenn der Zielbereich leer ist oder nicht im Quellbereich vorkommt, wird last1 zurückgegeben.

Komplexität

Gegeben $\scriptsize N_1$ $N 1$ als std::distance(first1, last1) und $\scriptsize N_2$ $N 2$ als std::distance(first2, last2):

1) Höchstens

N 2 \cdot(N 1 -N 2 +1)

Vergleiche mit operator==.

2) Höchstens

N 2 \cdot(N 1 -N 2 +1)

Anwendungen von p.

3)

𝓞(N 2 \cdot(N 1 -N 2 +1))

Vergleiche mit operator==.

4)

𝓞(N 2 \cdot(N 1 -N 2 +1))

Anwendungen von p.

Ausnahmen

3,4) Während des Ausführungsprozesses:

Wenn die für die Parallelisierung erforderlichen temporären Speicherressourcen nicht verfügbar sind, wird std::bad_alloc ausgelöst.
Wenn während des Zugriffs auf Objekte über ein Algorithmusargument eine nicht abgefangene Ausnahme ausgelöst wird, wird das Verhalten durch die Ausführungsstrategie bestimmt (für Standardstrategien wird std::terminate aufgerufen).

Mögliche Implementierung

find_end (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2)
{
    if (first2 == last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, last2);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
{
    if (first2== last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, first2, p);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

Beispiel

Dieses Programm ausführen

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>

auto print_result = [](auto result, const auto& v)
{
    result == v.end()
        ? std::cout << "Sequence not found\n"
        : std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
                    << '\n';
};

int main()
{
    const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    
    for (const auto& x : {std::array{1, 2, 3}, {4, 5, 6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
        print_result(iter, v);
    }
    
    for (const auto& x : {std::array{-1, -2, -3}, {-4, -5, -6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
                                  [](int x, int y)
                                  {
                                      return std::abs(x) == std::abs(y);
                                  });
        print_result(iter, v);
    }
}

Ausgabe:

Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	Angewendet auf	Verhalten wie veröffentlicht	Richtiges Verhalten
LWG 1205	C++98	Der Rückgabewert war unklar, wenn der Zielbereich leer ist	gibt in diesem Fall `last1` zurück
LWG 2150	C++98	Die Bedingung des "Vorkommens" war falsch	korrigiert

Siehe auch

ranges::find_end (C++20)	findet die letzte Folge von Elementen in einem bestimmten Bereich (Algorithmusfunktionsobjekt)
search	sucht nach dem ersten Vorkommen eines Bereichs von Elementen (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::search (C++20)
includes	bestimmt, ob eine Sequenz eine Untersequenz einer anderen ist (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::includes (C++20)
adjacent_find	findet die ersten beiden benachbarten Elemente, die gleich sind (oder ein gegebenes Prädikat erfüllen) (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	findet das erste Element, das bestimmte Kriterien erfüllt (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
find_first_of	sucht nach einem beliebigen Element aus einer Menge von Elementen (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::find_first_of (C++20)
search_n	sucht nach dem ersten Vorkommen einer bestimmten Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Funktionsschablone & Algorithmusfunktionsobjekt)
ranges::search_n (C++20)

Compiler-Unterstützung
Freistehend und gehostet
Sprache
Standardbibliothek
Standardbibliotheks-Header
Benannte Anforderungen
Feature-Test-Makros (C++20)
Sprachunterstützungsbibliothek
Concepts-Bibliothek (C++20)
Diagnosebibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogrammbibliothek
Containerbibliothek
Iteratorenbibliothek
Ranges-Bibliothek (C++20)
Algorithmenbibliothek
Zeichenkettenbibliothek
Textverarbeitungsbibliothek
Numerikbibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabebibliothek
Dateisystembibliothek (C++17)
Nebenläufigkeitsunterstützungsbibliothek (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolindex
Externe Bibliotheken

de.cppreference.net

Namespaces

Variants