std::ranges::find_end - cppreference.com

1) Busca la última ocurrencia de la secuencia [first2, last2) en el rango [first1, last1), después de la proyección con proj1 y proj2, respectivamente. Los elementos proyectados se comparan usando el predicado binario pred.

2) Igual que (1), pero usa r1 como el primer rango fuente y r2 como el segundo rango fuente, como si 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 niebloids, es decir:

• Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a cualquiera de ellas.
• Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
• Cuando alguna de ellas se encuentra mediante la búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.

En la práctica, pueden implementarse como objetos función o con extensiones de compilador especiales.

Parámetros

Valor de retorno

1) Un subrango de tipo ranges::subrange<I1>{} inicializado por valor con la expresión {i, i + (i == last1 ? 0 : ranges::distance(first2, last2))} que denota la última ocurrencia de la secuencia [first2, last2) en el rango [first1, last1) (después de las proyecciones con proj1 y proj2). Si [first2, last2) está vacío o si no se encuentra tal secuencia, el valor de retorno efectivamente se inicializa con {last1, last1}.

2) Igual que (1), excepto que el tipo de retorno es ranges::borrowed_subrange_t<R1>.

Complejidad

A lo sumo S·(N-S+1) aplicaciones del predicado correspondiente y cada proyección, donde S es ranges::distance(first2, last2) y N es ranges::distance(first1, last1) para (1), o S es ranges::distance(r2) y N es ranges::distance(r1) para (2).

Notas

Una implementación puede mejorar la eficiencia de la búsqueda si los iteradores de entrada modelan std::bidirectional_iterator buscando desde el final hacia el principio. Modelar std::random_access_iterator puede mejorar la velocidad de comparación. Sin embargo, todo esto no cambia la complejidad teórica del peor de los casos.

Posible implementación

struct find_end_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
  {
      if (first2 == last2) {
          auto last_it = ranges::next(first1, last1);
          return {last_it, last_it};
      }
      auto result = ranges::search(
          std::move(first1), last1, first2, last2, pred, proj1, proj2);

      if (result.empty()) return result;

      for (;;) {
          auto new_result = ranges::search(
              std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);
          if (new_result.empty())
              return result;
          else
              result = std::move(new_result);
      }
  }

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

Ejemplo

#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>

void imprimir(const auto pajar, const auto aguja)
{
    const auto pos = std::distance(pajar.begin(), aguja.begin());
    std::cout << "En \"";
    for (const auto c : pajar) { std::cout << c; }
    std::cout << "\" se encontró \"";
    for (const auto c : aguja) { std::cout << c; }
    std::cout << "\" en la posición [" << pos << ".." << pos + aguja.size() << ")\n"
        << std::string(4 + pos, ' ') << std::string(aguja.size(), '^') << '\n';
}

int main()
{
    using namespace std::literals;
    constexpr auto secreto{"contraseña contraseña seña..."sv};
    constexpr auto deseada{"contraseña"sv};

    constexpr auto encontrado1 = std::ranges::find_end(
        secreto.cbegin(), secreto.cend(), deseada.cbegin(), deseada.cend());
    imprimir(secreto, encontrado1);

    constexpr auto encontrado2 = std::ranges::find_end(secreto, "seña"sv);
    imprimir(secreto, encontrado2);

    const auto encontrado3 = std::ranges::find_end(secreto, "TRA"sv,
        [](const char x, const char y) { // usa un predicado binario
            return std::tolower(x) == std::tolower(y);
        });
    imprimir(secreto, encontrado3);

    const auto encontrado4 = std::ranges::find_end(secreto, "ASEÑA"sv, {}, {},
        [](char c) { return std::tolower(c); }); // proyecta el segundo rango
    imprimir(secreto, encontrado4);

    static_assert(std::ranges::find_end(secreto, "CLAVE"sv).empty()); // => no se encontró
}

En "contraseña contraseña contra..." se encontró "contraseña" en la posición [9..17)
               ^^^^^^^^^^
En "contraseña contraseña contra..." se encontró "seña" en la posición [18..22)
                          ^^^^^^
En "contraseña contraseña contra..." se encontró "tra" en la posición [19..22)
                             ^^^
En "contraseña contraseña contra..." se encontró "aseña" en la posición [12..17)
                    ^^^^^

Véase también