Espacios de nombres
Variantes
Acciones

std::search

De cppreference.com
< cpp‎ | algorithm
 
 
Biblioteca de algoritmos
Políticas de ejecución (C++17)
Operaciones de secuencia no modificantes
(C++11)(C++11)(C++11)
(C++17)
Operaciones de secuencia modificantes
Operaciones en almacenamiento no inicializado
Operaciones de partición
Operaciones de ordenación
(C++11)
Operaciones de búsqueda binaria
Operaciones de conjuntos (en rangos ordenados)
Operaciones de pila
(C++11)
Operaciones mínimo/máximo
(C++11)
(C++17)
Permutaciones
Operaciones numéricas
Bibliotecas C
 
Definido en el archivo de encabezado <algorithm>
(1)
template< class ForwardIt1, class ForwardIt2 >

ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,

                   ForwardIt2 s_first, ForwardIt2 s_last );
(hasta C++20)
template< class ForwardIt1, class ForwardIt2 >

constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,

                             ForwardIt2 s_first, ForwardIt2 s_last );
(desde C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >

ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,

                   ForwardIt2 s_first, ForwardIt2 s_last );
(2) (desde C++17)
(3)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >

ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,

                   BinaryPredicate p );
(hasta C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >

constexpr ForwardIt1 search( ForwardIt1 first, ForwardIt1 last,
                             ForwardIt2 s_first, ForwardIt2 s_last,

                             BinaryPredicate p );
(desde C++20)
template< class ExecutionPolicy,

          class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 search( ExecutionPolicy&& policy,
                   ForwardIt1 first, ForwardIt1 last,
                   ForwardIt2 s_first, ForwardIt2 s_last,

                   BinaryPredicate p );
(4) (desde C++17)
(5)
template< class ForwardIt, class Searcher >

ForwardIt search( ForwardIt first, ForwardIt last,

                  const Searcher& searcher );
(desde C++17)
(hasta C++20)
template< class ForwardIt, class Searcher >

constexpr ForwardIt search( ForwardIt first, ForwardIt last,

                            const Searcher& searcher );
(desde C++20)
1-4) Busca la primera ocurrencia de la secuencia de elementos [s_firsts_last) en el rango [firstlast).
1) Los elementos se comparan usando operator==.
3) Los elementos se comparan usando el predicado binario dado p.
2,4) Igual que (1,3), pero ejecutado de acuerdo a la política de ejecución policy. Estas sobrecargas no participan en la resolución de sobrecarga a menos que std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> (hasta C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> (desde C++20) sea verdadera.
5) Busca la secuencia [firstlast) por el patrón especificado en el constructor de searcher. Efectivamente ejecuta return searcher(first, last).first;. Searcher no tiene que ser CopyConstructible.

La biblioteca estándar proporciona los siguientes buscadores:

Implementación del algoritmo de búsqueda de la biblioteca estándar de C++.
(plantilla de clase) [editar]
Implementación del algoritmo de búsqueda Boyer-Moore.
(plantilla de clase) [editar]
Implementación del algoritmo de búsqueda Boyer-Moore-Horspool.
(plantilla de clase) [editar]
(desde C++17)

Contenido

[editar] Parámetros

first, last - El rango de los elementos a examinar.
s_first, s_last - El rango de la secuencia de elementos a buscar.
policy - La política de ejecución a usar. Véase política de ejecución para más detalles.
searcher - El buscador que encapsula el algoritmo de búsqueda y el patrón a buscar.
p - Predicado binario que devuelve ​true si los elementos deben tratarse como iguales.

La signatura de la función predicado deberá ser equivalente a la siguiente:

 bool pred(const Tipo1 &a, const Tipo2 &b);

Mientras que la signatura no necesita tener const &, la función no debe modificar los objetos que se le han pasado y debe ser capaz de aceptar todos los valores de tipo (posiblemente const) Tipo1 y Tipo2 independientemente de la categoría de valor (por lo tanto, no se permite Tipo1 &, ni Tipo1 a menos que para Tipo1 un movimiento sea equivalente a una copia (desde C++11)).
Los tipos Tipo1 y Tipo2 deben ser tales que objetos de tipo ForwardIt1 y ForwardIt2 pueden ser desreferenciados y luego convertidos implícitamente a Tipo1 and Tipo2 respectively. ​

Requisitos de tipo
-
ForwardIt1, ForwardIt2 debe satisfacer los requisitos de ForwardIterator.
-
Searcher debe satisfacer los requisitos de Searcher.

[editar] Valor de retorno

1-4) Iterador al comienzo de la primera ocurrencia de la secuencia [s_firsts_last) en el rango [firstlast). Si no se encuentra tal ocurrencia, se devuelve last.
Si [s_firsts_last) está vacío, se devuelve first. (desde C++11)
5) Devuelve el resultado de searcher.operator(), es decir, un iterador a la ubicación en la que se encuentra la subcadena, o una copia de last si no se encontró.

[editar] Complejidad

1-4) A lo sumo S * N comparaciones, donde S = std::distance(s_first, s_last) y N = std::distance(first, last).
5) Depende del buscador.

[editar] Excepciones

Las sobrecargas con un parámetro de plantilla llamado ExecutionPolicy (política de ejecución) reportan errores tales que:

  • Si la ejecución de una función invocada como parte del algoritmo lanza una excepción y la política de ejecución es una de las tres políticas estándar, se llama a std::terminate. Para cualquier otra política de ejecución, el comportamiento está definido por la implementación.
  • Si el algoritmo falla al asignar memoria, se lanza std::bad_alloc.

[editar] Posible implementación

search (1)
template<class ForwardIt1, class ForwardIt2>
constexpr 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 BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last,
                            BinaryPredicate 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;
    }
}

[editar] Ejemplo

#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <vector>
using namespace std::literals;
 
bool contains(const auto& cont, std::string_view s)
{
    // str.find() (o str.contains(), desde C++23) también se puede usar
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}
 
int main()
{
    const auto str {"¿Por qué perder el tiempo aprendiendo, cuando la ignorancia es instantánea?"sv};
 
    std::cout << std::boolalpha
              << contains(str, "aprendiendo") << '\n'     // true
              << contains(str, "aprehendiendo")  << '\n'; // false
 
    const std::vector vec(str.begin(), str.end());
    std::cout << contains(vec, "aprendiendo") << '\n'     // true
              << contains(vec, "aprehendiendo")  << '\n'; // false
 
    // La sobrecarga de C++17 con demo de buscadores:
    constexpr auto pajar
    {
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
        "do eiusmod tempor incididunt ut labore et dolore magna aliqua"sv
    };
 
    for (const auto aguja : {"piscis"sv, "Piscis"sv})
    {
        const std::boyer_moore_searcher searcher(aguja.begin(), aguja.end());
        const auto it = std::search(pajar.begin(), pajar.end(), searcher);
        std::cout << "La cadena " << std::quoted(aguja) << ' ';
        if (it == pajar.end())
            std::cout << "no se encontró\n";
        else
            std::cout << "se encontró en el desplazamiento " << it - pajar.begin() << '\n';
    }
}

Salida:

true
false
true
false
La cadena "piscis" se encontró en el desplazamiento 43
La cadena "Piscis" no se encontró

[editar] Véase también

Encuentra la última secuencia de elementos en un cierto rango.
(plantilla de función) [editar]
Devuelve true si una secuencia es una subsecuencia de otra.
(plantilla de función) [editar]
Determina si dos conjuntos de elementos son iguales.
(plantilla de función) [editar]
Encuentra el primer elemento que satisfaga un criterio específico.
(plantilla de función) [editar]
Devuelve true si un rango es lexicográficamente menor que otro.
(plantilla de función) [editar]
Encuentra la primera posición donde dos rangos difieren.
(plantilla de función) [editar]
Busca un número de copias consecutivas de un elemento en un rango.
(plantilla de función) [editar]
Implementación del algoritmo de búsqueda de la biblioteca estándar de C++.
(plantilla de clase) [editar]
Implementación del algoritmo de búsqueda Boyer-Moore.
(plantilla de clase) [editar]
Implementación del algoritmo de búsqueda Boyer-Moore-Horspool.
(plantilla de clase) [editar]
Busca una subsecuencia de elementos en un rango.
(niebloid) [editar]