std::ranges:: search

From cppreference.net

Défini dans l'en-tête `<algorithm>`
Signature d'appel
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 > search ( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(1)	(depuis 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 > search ( R1 && r1, R2 && r2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(2)	(depuis C++20)

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

first2

last2

dans la plage

first1

last1

. Les éléments sont comparés à l'aide du prédicat binaire pred après avoir été projetés avec proj2 et proj1 , respectivement.

2) Identique à (1) , mais utilise r1 comme première plage source et r2 comme seconde plage source, comme si on utilisait ranges:: begin ( r1 ) comme first1 , ranges:: end ( r1 ) comme last1 , ranges:: begin ( r2 ) comme first2 , et ranges:: end ( r2 ) comme last2 .

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids ), c'est-à-dire :

Les listes d'arguments de template explicites ne peuvent pas être spécifiées lors de l'appel de l'une d'entre elles.
Aucune d'entre elles n'est visible pour la recherche dépendante des arguments .
Lorsque l'une d'entre elles est trouvée par la recherche non qualifiée normale comme nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.

Table des matières

Paramètres

first1, last1	-	la paire itérateur-sentinelle définissant la plage d'éléments à examiner (appelée haystack )
first2, last2	-	la paire itérateur-sentinelle définissant la plage d'éléments à rechercher (appelée needle )
r1	-	la plage d'éléments à examiner (appelée haystack )
r2	-	la plage d'éléments à rechercher (appelée needle )
pred	-	prédicat binaire à appliquer aux éléments projetés
proj1	-	projection à appliquer aux éléments de la première plage
proj2	-	projection à appliquer aux éléments de la deuxième plage

Valeur de retour

1) Retourne une valeur ranges:: subrange qui représente la première occurrence de la séquence

first2

last2

(appelée needle ) dans la plage

first1

last1

(appelée haystack ), après application des projections proj1 et proj2 aux éléments des deux séquences respectivement, suivie de l'application du prédicat binaire pred pour comparer les éléments projetés.

Si aucune occurrence n'est trouvée, ranges:: subrange { last1, last1 } est retourné.

Si la plage à rechercher (appelée needle ) est vide, c'est-à-dire first2 == last2 , alors ranges:: subrange { first1, first1 } est retourné.

2) Identique à (1) mais le type de retour est ranges:: borrowed_subrange_t < R1 > .

Complexité

Au plus S * N applications du prédicat correspondant et de chaque projection, où
(1) S = ranges:: distance ( first2, last2 ) et N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) et N = ranges:: distance ( r1 ) .

Implémentation possible

struct search_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
    {
        for (;; ++first1)
        {
            I1 it1 = first1;
            for (I2 it2 = first2;; ++it1, ++it2)
            {
                if (it2 == last2)
                    return {first1, it1};
                if (it1 == last1)
                    return {it1, it1};
                if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2)))
                    break;
            }
        }
    }
    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 search_fn search {};

Exemple

Exécuter ce code

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string_view>
using namespace std::literals;
void print(int id, const auto& haystack, const auto& needle, const auto& found)
{
    std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); ";
    const auto first = std::distance(haystack.begin(), found.begin());
    const auto last = std::distance(haystack.begin(), found.end());
    if (found.empty())
        std::cout << "not found;";
    else
    {
        std::cout << "found: \"";
        for (const auto x : found)
            std::cout << x;
        std::cout << "\";";
    }
    std::cout << " subrange: {" << first << ", " << last << "}\n";
}
int main()
{
    constexpr auto haystack {"abcd abcd"sv};
    constexpr auto needle {"bcd"sv};
    // la recherche utilise des paires d'itérateurs begin()/end() :
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // la recherche utilise les plages r1, r2 :
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // la plage 'needle' est vide :
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' ne sera pas trouvé :
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // la recherche utilise un comparateur personnalisé et des projections :
    constexpr auto bodkin {"234"sv};
    auto found5 = std::ranges::search(haystack, bodkin,
        [](const int x, const int y) { return x == y; }, // pred
        [](const int x) { return std::toupper(x); }, // proj1
        [](const int y) { return y + 'A' - '1'; }); // proj2
    print(5, haystack, bodkin, found5);
}

Sortie :

1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}

Voir aussi

ranges::adjacent_find (C++20)	trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné) (objet fonction algorithme)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	trouve le premier élément satisfaisant des critères spécifiques (objet fonction algorithme)
ranges::find_end (C++20)	trouve la dernière séquence d'éléments dans une certaine plage (objet fonction algorithme)
ranges::find_first_of (C++20)	recherche l'un quelconque d'un ensemble d'éléments (objet fonction algorithme)
ranges::contains ranges::contains_subrange (C++23) (C++23)	vérifie si la plage contient l'élément ou la sous-plage donnée (objet fonction algorithme)
ranges::includes (C++20)	retourne true si une séquence est une sous-séquence d'une autre (objet fonction algorithme)
ranges::mismatch (C++20)	trouve la première position où deux plages diffèrent (objet fonction algorithme)
ranges::search_n (C++20)	recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (objet fonction algorithme)
search	recherche la première occurrence d'une plage d'éléments (modèle de fonction)

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