std::search

Definiert in Header `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last );	(2)	(seit C++17)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p );	(3)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 search( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p );	(4)	(seit C++17)
template< class ForwardIt, class Searcher > ForwardIt search( ForwardIt first, ForwardIt last, const Searcher& searcher );	(5)	(seit C++17) (constexpr seit C++20)

1-4) Durchsucht nach dem ersten Vorkommen der Sequenz von Elementen [s_first, s_last) im Bereich [first, last).

1) Elemente werden mit operator== verglichen.

3) Elemente werden mit dem gegebenen binären Prädikat p verglichen.

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

Diese Überladungen nehmen an der Auflösungsauflösung teil, nur wenn alle folgenden Bedingungen erfüllt sind

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true.	(bis C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true.	(seit C++20)

5) Durchsucht den Bereich [first, last) nach dem Muster, das im Konstruktor von searcher spezifiziert ist.

Die Standardbibliothek stellt folgende Sucher bereit:

default_searcher (C++17)	Implementierung des standardmäßigen C++-Bibliotheks-Suchalgorithmus (Klassen-Template) [bearbeiten]
boyer_moore_searcher (C++17)	Implementierung des Boyer-Moore-Suchalgorithmus (Klassen-Template) [bearbeiten]
boyer_moore_horspool_searcher (C++17)	Implementierung des Boyer-Moore-Horspool-Suchalgorithmus (Klassen-Template) [bearbeiten]

(seit C++17)

[edit] Parameter

first, last	-	das Iteratorenpaar, das den Bereich der zu untersuchenden Elemente definiert
s_first, s_last	-	das Iteratorenpaar, das den zu suchenden Elementbereich definiert
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
searcher	-	der Sucher, der den Suchalgorithmus und das zu suchende Muster kapselt
p	-	binäre Prädikatfunktion, die true zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte äquivalent zur folgenden sein: bool pred(const Type1 &a, const Type2 &b); Obwohl die Signatur nicht zwingend const & haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt, ebenso wenig wie Type1, es sei denn, für `Type1` ist eine Verschiebung gleichbedeutend mit einer Kopie(seit C++11)). Die Typen Type1 und Type2 müssen so beschaffen sein, dass Objekte der Typen ForwardIt1 und ForwardIt2 dereferenziert und dann implizit in Type1 bzw. Type2 konvertiert werden können.
Typanforderungen
- `ForwardIt1, ForwardIt2` müssen die Anforderungen an LegacyForwardIterator erfüllen.
- `BinaryPred` muss die Anforderungen an BinaryPredicate erfüllen.

[edit] Rückgabewert

1-4) Iterator zum Anfang des ersten Vorkommens der Sequenz [s_first, s_last) im Bereich [first, last). Wenn kein solches Vorkommen gefunden wird, wird last zurückgegeben.

Wenn [s_first, s_last) leer ist, wird first zurückgegeben.

5) searcher(first, last).first.

[edit] Komplexität

1-4) Bei

N

als std::distance(first, last) und

S

als std::distance(s_first, s_last)

1,2) Höchstens

N\cdotS

Vergleiche mit operator==.

3,4) Höchstens

N\cdotS

Anwendungen des Prädikats p.

5) Abhängig von searcher.

[edit] Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten Fehler wie folgt

Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

[edit] Mögliche Implementierung

search (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!(*it == *s_it))
                break;
        }
        ++first;
    }
}

search (3)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last, BinaryPred p)
{
    while (true)
    {
        ForwardIt1 it = first;
        for (ForwardIt2 s_it = s_first; ; ++it, ++s_it)
        {
            if (s_it == s_last)
                return first;
            if (it == last)
                return last;
            if (!p(*it, *s_it))
                break;
        }
        ++first;
    }
}

[edit] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string_view>
#include <vector>
 
using namespace std::literals;
 
bool contains(const auto& cont, std::string_view s)
{
    // str.find() (or str.contains(), since C++23) can be used as well
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
 
int main()
{
    const auto str{"why waste time learning, when ignorance is instantaneous?"sv};
    assert(contains(str, "learning"));
    assert(not contains(str, "lemming"));
 
    const std::vector vec(str.begin(), str.end());
    assert(contains(vec, "learning"));
    assert(not contains(vec, "leaning"));
 
    // The C++17 overload with searchers demo:
    constexpr auto quote
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };
 
    for (const auto word : {"pisci"sv, "Pisci"sv})
    {
        std::cout << "The string " << std::quoted(word) << ' ';
        const std::boyer_moore_searcher searcher(word.begin(), word.end());
        const auto it = std::search(quote.begin(), quote.end(), searcher);
        if (it == quote.end())
            std::cout << "not found\n";
        else
            std::cout << "found at offset " << std::distance(quote.begin(), it) << '\n';
    }
}

Ausgabe

The string "pisci" found at offset 43
The string "Pisci" not found

[edit] Fehlerberichte

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 1205	C++98	Der Rückgabewert war unklar, wenn `[`s_first`,` s_last`)` leer ist.	Gibt in diesem Fall first zurück.
LWG 1338	C++98	Die Auflösung von LWG-Problem 1205 wurde falsch angewendet, wodurch first zurückgegeben wird, wenn kein Vorkommen gefunden wird.	Gibt in diesem Fall last zurück.
LWG 2150	C++98	Die Bedingung "Sequenzvorkommen" war falsch.	korrigiert

[edit] Siehe auch

find_end	Findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Funktionstempelat) [edit]
includes	Gibt true zurück, wenn eine Sequenz eine Untersequenz einer anderen ist (Funktionstemplate) [edit]
equal	Bestimmt, ob zwei Elementmengen gleich sind (Funktionstempelat) [edit]
findfind_iffind_if_not (C++11)	Findet das erste Element, das bestimmte Kriterien erfüllt (Funktionstempelat) [edit]
lexicographical_compare	gibt true zurück, wenn ein Bereich lexikographisch kleiner als ein anderer ist (Funktionsvorlage) [editieren]
mismatch	Findet die erste Position, an der sich zwei Bereiche unterscheiden (Funktionstempelat) [edit]
search_n	Sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Funktionstempelat) [edit]
default_searcher (C++17)	Implementierung des standardmäßigen C++-Bibliotheks-Suchalgorithmus (Klassen-Template) [bearbeiten]
boyer_moore_searcher (C++17)	Implementierung des Boyer-Moore-Suchalgorithmus (Klassen-Template) [bearbeiten]
boyer_moore_horspool_searcher (C++17)	Implementierung des Boyer-Moore-Horspool-Suchalgorithmus (Klassen-Template) [bearbeiten]
ranges::search (C++20)	Sucht nach dem ersten Vorkommen eines Elementbereichs (Algorithmus-Funktionsobjekt)[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