Namespaces
Variants

std::ranges::search

De es.cppreference.net
 
 
Biblioteca de algoritmos
Algoritmos restringidos y algoritmos sobre rangos (C++20)
Algoritmos restringidos, ej. ranges::copy, ranges::sort, ...
Operaciones de secuencia no modificadoras    
Operaciones por lotes
(C++17)
Operaciones de búsqueda
Operaciones de secuencia modificadoras
Operaciones de copia
(C++11)
(C++11)
Operaciones de intercambio
Operaciones de transformación
Operaciones de generación
Operaciones de eliminación
Operaciones de cambio de orden
(hasta C++17)(C++11)
(C++20)(C++20)
Operaciones de muestreo
(C++17)

Ordenamiento y operaciones relacionadas
Operaciones de particionado
(C++11)    

Operaciones de ordenamiento
Operaciones de búsqueda binaria
(en rangos particionados)
Operaciones de conjunto (en rangos ordenados)
Operaciones de fusión (en rangos ordenados)
Operaciones de montículo
Operaciones de mínimo/máximo
(C++11)
(C++17)
Operaciones de comparación lexicográfica
Operaciones de permutación


 
Algoritmos restringidos
Todos los nombres en este menú pertenecen al espacio de nombres std::ranges
Operaciones de secuencia no modificadoras
Operaciones de secuencia modificadoras
Operaciones de particionado
Operaciones de ordenamiento
Operaciones de búsqueda binaria (en rangos ordenados)
       
       
Operaciones de conjunto (en rangos ordenados)
Operaciones de montículo
Operaciones de mínimo/máximo
       
       
Operaciones de permutación
Operaciones de pliegue
Operaciones sobre almacenamiento no inicializado
Tipos de retorno
 
Definido en el encabezado <algorithm>
Firma de llamada
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) (desde 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) (desde C++20)
1) Busca la primera ocurrencia de la secuencia de elementos [first2, last2) en el rango [first1, last1). Los elementos se comparan usando el predicado binario pred después de ser proyectados con proj2 y proj1, respectivamente.
2) Igual que (1), pero usa r1 como el primer rango fuente y r2 como el segundo rango fuente, como si se usara ranges::begin(r1) como first1, ranges::end(r1) como last1, ranges::begin(r2) como first2 y ranges::end(r2) como last2.

Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (informalmente conocidos como niebloids), es decir:

Parámetros

first1, last1 - el par iterador-centinela que define el rango de elementos a examinar (también conocido como haystack )
first2, last2 - el par iterador-centinela que define el rango de elementos a buscar (también conocido como needle )
r1 - el rango de elementos a examinar (también conocido como haystack )
r2 - el rango de elementos a buscar (también conocido como needle )
pred - predicado binario para aplicar a los elementos proyectados
proj1 - proyección para aplicar a los elementos en el primer rango
proj2 - proyección para aplicar a los elementos en el segundo rango

Valor de retorno

1) Devuelve un valor ranges:: subrange que es la primera ocurrencia de la secuencia [ first2 , last2 ) (también conocida como needle ) en el rango [ first1 , last1 ) (también conocido como haystack ), después de aplicar las proyecciones proj1 y proj2 a los elementos de ambas secuencias respectivamente, con la aplicación consecuente del predicado binario pred para comparar los elementos proyectados.

Si no se encuentra dicha ocurrencia, se devuelve ranges:: subrange { last1, last1 } .

Si el rango a buscar (también conocido como needle ) está vacío, es decir, first2 == last2 , entonces se devuelve ranges:: subrange { first1, first1 } .
2) Igual que (1) pero el tipo de retorno es ranges:: borrowed_subrange_t < R1 > .

Complejidad

Como máximo S * N aplicaciones del predicado correspondiente y cada proyección, donde
(1) S = ranges:: distance ( first2, last2 ) y N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) y N = ranges:: distance ( r1 ) .

Implementación posible

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 {};

Ejemplo

#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 búsqueda utiliza pares de iteradores begin()/end():
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // la búsqueda utiliza rangos r1, r2:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // el rango 'needle' está vacío:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' no será encontrado:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // la búsqueda utiliza comparador personalizado y proyecciones:
    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);
}

Salida:

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}

Véase también

encuentra los primeros dos elementos adyacentes que son iguales (o que satisfacen un predicado dado)
(objeto función de algoritmo)
encuentra el primer elemento que satisface criterios específicos
(objeto función de algoritmo)
encuentra la última secuencia de elementos en un rango determinado
(objeto función de algoritmo)
busca cualquiera de un conjunto de elementos
(objeto función de algoritmo)
comprueba si el rango contiene el elemento o subrango dado
(objeto función de algoritmo)
determina si una secuencia es una subsecuencia de otra
(objeto función de algoritmo)
encuentra la primera posición donde dos rangos difieren
(objeto función de algoritmo)
busca la primera aparición de un número de copias consecutivas de un elemento en un rango
(objeto función de algoritmo)
busca la primera aparición de un rango de elementos
(plantilla de función)