std:: search

From cppreference.net

Défini dans l'en-tête `<algorithm>`
template < class ForwardIt1, class ForwardIt2 > ForwardIt1 search ( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last ) ;	(1)	(constexpr depuis C++20)
template < class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 search ( ExecutionPolicy && policy, ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last ) ;	(2)	(depuis 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 depuis 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)	(depuis C++17)
template < class ForwardIt, class Searcher > ForwardIt search ( ForwardIt first, ForwardIt last, const Searcher & searcher ) ;	(5)	(depuis C++17) (constexpr depuis C++20)

1-4) Recherche la première occurrence de la séquence d'éléments

s_first

s_last

dans la plage

first

last

1) Les éléments sont comparés en utilisant operator == .

3) Les éléments sont comparés en utilisant le prédicat binaire donné p .

2,4) Identique à (1,3) , mais exécuté selon la policy .

Ces surcharges participent à la résolution de surcharge seulement si toutes les conditions suivantes sont satisfaites :

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> est true .	(jusqu'à C++20)
std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> est true .	(depuis C++20)

5) Recherche dans la plage

first

last

le motif spécifié dans le constructeur de searcher .

La bibliothèque standard fournit les chercheurs suivants :

default_searcher (C++17)	implémentation de l'algorithme de recherche de la bibliothèque standard C++ (modèle de classe)
boyer_moore_searcher (C++17)	implémentation de l'algorithme de recherche Boyer-Moore (modèle de classe)
boyer_moore_horspool_searcher (C++17)	implémentation de l'algorithme de recherche Boyer-Moore-Horspool (modèle de classe)

(depuis C++17)

Table des matières

Paramètres

first, last	-	la paire d'itérateurs définissant l' intervalle des éléments à examiner
s_first, s_last	-	la paire d'itérateurs définissant l' intervalle des éléments à rechercher
policy	-	la politique d'exécution à utiliser
searcher	-	le chercheur encapsulant l'algorithme de recherche et le motif à rechercher
p	-	prédicat binaire qui renvoie true si les éléments doivent être traités comme égaux. La signature de la fonction de prédicat doit être équivalente à ce qui suit : bool pred ( const Type1 & a, const Type2 & b ) ; Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs de type (éventuellement const) `Type1` et `Type2` indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour `Type1` un déplacement équivaut à une copie (depuis C++11) ). Les types Type1 et Type2 doivent être tels que les objets de types ForwardIt1 et ForwardIt2 puissent être déréférencés puis implicitement convertis en Type1 et Type2 respectivement.
Exigences de type
- `ForwardIt1, ForwardIt2` doivent satisfaire aux exigences de LegacyForwardIterator .
- `BinaryPred` doit satisfaire aux exigences de BinaryPredicate .

Valeur de retour

1-4) Itérateur vers le début de la première occurrence de la séquence

s_first

s_last

dans la plage

first

last

. Si aucune occurrence n'est trouvée, last est retourné.

s_first

s_last

est vide, first est retourné.

5) searcher ( first, last ) . first .

Complexité

1-4) Soit

N

égal à std:: distance ( first, last ) et

S

égal à std:: distance ( s_first, s_last ) :

1,2) Au maximum

N\cdotS

comparaisons en utilisant operator == .

3,4) Au plus

N\cdotS

applications du prédicat p .

5) Dépend de searcher .

Exceptions

Les surcharges avec un paramètre de modèle nommé ExecutionPolicy signalent les erreurs comme suit :

Si l'exécution d'une fonction invoquée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy fait partie des politiques standard , std::terminate est appelé. Pour tout autre ExecutionPolicy , le comportement est défini par l'implémentation.
Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levé.

Implémentation possible

recherche (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< depuis 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;
    }
}

recherche (3)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< depuis 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;
    }
}

Exemple

Exécuter ce code

#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';
    }
}

Sortie :

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

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR	S'applique à	Comportement publié	Comportement corrigé
LWG 1205	C++98	la valeur de retour était ambiguë si `[` s_first `,` s_last `)` est vide	retourne first dans ce cas
LWG 1338	C++98	la résolution de LWG issue 1205 a été incorrectement appliquée, entraînant le retour de first si aucune occurrence n'est trouvée	retourne last dans ce cas
LWG 2150	C++98	la condition d'"occurrence de séquence" était incorrecte	corrigée

Voir aussi

find_end	trouve la dernière séquence d'éléments dans une certaine plage (modèle de fonction)
includes	retourne true si une séquence est une sous-séquence d'une autre (modèle de fonction)
equal	détermine si deux ensembles d'éléments sont identiques (modèle de fonction)
find find_if find_if_not (C++11)	trouve le premier élément satisfaisant des critères spécifiques (modèle de fonction)
lexicographical_compare	retourne true si une plage est lexicographiquement inférieure à une autre (modèle de fonction)
mismatch	trouve la première position où deux plages diffèrent (modèle de fonction)
search_n	recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (modèle de fonction)
default_searcher (C++17)	implémentation standard de l'algorithme de recherche de la bibliothèque C++ (modèle de classe)
boyer_moore_searcher (C++17)	implémentation de l'algorithme de recherche Boyer-Moore (modèle de classe)
boyer_moore_horspool_searcher (C++17)	implémentation de l'algorithme de recherche Boyer-Moore-Horspool (modèle de classe)
ranges::search (C++20)	recherche la première occurrence d'une plage d'éléments (objet fonction algorithme)

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:: search

Table des matières

Paramètres

Valeur de retour

Complexité

Exceptions

Implémentation possible

Exemple

Rapports de défauts

Voir aussi