Namespaces
Variants

std::ranges::search

Depuis fr.cppreference.net
 
 
Bibliothèque d'algorithmes
Algorithmes contraints et algorithmes sur plages (C++20)
Algorithmes contraints, par ex. ranges::copy, ranges::sort, ...
Opérations de séquence non modificatrices    
Opérations par lots
(C++17)
Opérations de recherche
Opérations de séquence modificatrices
Opérations de copie
(C++11)
(C++11)
Opérations d'échange
Opérations de transformation
Opérations de génération
Opérations de suppression
Opérations de changement d'ordre
(jusqu'à C++17)(C++11)
(C++20)(C++20)
Opérations d'échantillonnage
(C++17)

Opérations de tri et connexes
Opérations de partitionnement
(C++11)    

Opérations de tri
Opérations de recherche binaire
(sur plages partitionnées)
Opérations d'ensemble (sur plages triées)
Opérations de fusion (sur plages triées)
Opérations de tas
Opérations minimum/maximum
(C++11)
(C++17)
Opérations de comparaison lexicographique
Opérations de permutation


 
Algorithmes contraints
Tous les noms de ce menu appartiennent à l'espace de noms std::ranges
Opérations de séquence non modificatrices
Opérations de séquence modificatrices
Opérations de partitionnement
Opérations de tri
Opérations de recherche binaire (sur plages triées)
       
       
Opérations d'ensemble (sur plages triées)
Opérations de tas
Opérations minimum/maximum
       
       
Opérations de permutation
Opérations de pliage
Opérations sur le stockage non initialisé
Types de retour
 
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 [first2last2) dans l'intervalle [first1last1). 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 premier intervalle source et r2 comme second intervalle source, comme si en utilisant 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 fonctions d'algorithme (informellement appelés niebloids), c'est-à-dire :

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

#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

trouve les deux premiers éléments adjacents qui sont égaux (ou satisfont un prédicat donné)
(objet fonction d'algorithme)
trouve le premier élément satisfaisant des critères spécifiques
(objet fonction d'algorithme)
trouve la dernière séquence d'éléments dans un certain intervalle
(objet fonction d'algorithme)
recherche l'un quelconque d'un ensemble d'éléments
(objet fonction d'algorithme)
vérifie si l'intervalle contient l'élément ou le sous-intervalle donné
(objet fonction d'algorithme)
détermine si une séquence est une sous-séquence d'une autre
(objet fonction d'algorithme)
trouve la première position où deux intervalles diffèrent
(objet fonction d'algorithme)
recherche la première occurrence d'un nombre de copies consécutives d'un élément dans un intervalle
(objet fonction d'algorithme)
recherche la première occurrence d'un intervalle d'éléments
(fonction template)