c++ - examples - Pasando un lambda en una plantilla de función

lambda examples c++

Question

Estoy aprendiendo C ++, y estoy tratando de implementar una función de búsqueda binaria que encuentra el primer elemento para el que se mantiene un predicado. El primer argumento de la función es un vector y el segundo argumento es una función que evalúa el predicado para un elemento dado. La función de búsqueda binaria se ve así:

template <typename T> int binsearch(const std::vector<T> &ts, bool (*predicate)(T)) {
    ...
}

Esto funciona como se espera si se usa así:

bool gte(int x) {
    return x >= 5;
}

int main(int argc, char** argv) {
    std::vector<int> a = {1, 2, 3};
    binsearch(a, gte);
    return 0;
}

Pero si uso una función lambda como predicado, obtengo un error de compilación:

search-for-a-range.cpp:20:5: error: no matching function for call to ''binsearch''
    binsearch(a, [](int e) -> bool { return e >= 5; });
    ^~~~~~~~~
search-for-a-range.cpp:6:27: note: candidate template ignored: could not match ''bool (*)(T)'' against ''(lambda at
      search-for-a-range.cpp:20:18)''
template <typename T> int binsearch(const std::vector<T> &ts,
                          ^
1 error generated.

El error anterior es generado por

binsearch(a, [](int e) -> bool { return e >= 5; });

Que pasa ¿Por qué el compilador no está convencido de que mi lambda tiene el tipo correcto?

Answer 1

¿Por qué el compilador no está convencido de que mi lambda tiene el tipo correcto?

Las funciones de plantilla que se indican para deducir sus parámetros de plantilla no hacen conversión . Un lambda no es un puntero a función, por lo que no hay forma de deducir la T en ese argumento. Como todos los argumentos de función deducen de forma independiente sus parámetros de plantilla (a menos que se bloquee la deducción), esto produce un error.

Hay una serie de correcciones que puedes hacer.

Puedes arreglar la función de plantilla.

template <class T>
int binsearch(const std::vector<T> &ts, bool (*predicate)(T))

Reemplace el puntero de función con un Predicate predicate o Predicate&& predicate y deje el cuerpo sin cambios.

template <class T, class Predicate>
int binsearch(const std::vector<T> &ts, Predicate&& predicate)

Utilizar bloqueo de deducción:

template<class T>struct tag_t{using type=T;};
template<class T>using block_deduction=typename tag_t<T>::type;
template <class T>
int binsearch(const std::vector<T> &ts, block_deduction<bool (*)(T)> predicate)

opcionalmente, mientras reemplaza el puntero a la función con una std::function<bool(T)> .

Puedes arreglarlo en el sitio de la llamada.

Puede pasar T manualmente binsearch<T>(vec, [](int x){return x<0;}) .

Puede descomponer la lambda a un puntero de función poniendo un + delante de él +[](int x) ... o un static_cast<bool(*)(int)>( ... ) .

La mejor opción es Predicate uno. Esto es también lo que hace el código de la biblioteca estándar.

También podemos ir un paso más allá y hacer que su código sea aún más genérico:

template <class Range, class Predicate>
auto binsearch(const Range &ts, Predicate&& predicate)
-> typename std::decay< decltype(*std::begin(ts)) >::type

La parte del tipo de retorno final de -> typename std::decay ... se puede eliminar en C ++ 14.

Un beneficio de esto es que si el cuerpo también usa std::begin y std::end para encontrar iteradores de inicio / fin, binsearch ahora admite deque s, arreglos de estilo C, std::array s, std::string s , std::vector s, e incluso algunos tipos personalizados.

Answer 2

La lambda con la lista de captura vacía podría convertirse implícitamente en un puntero de función. Pero el predicate puntero de función está tomando T como su parámetro, que debe deducirse. La conversión de tipo no se considerará en la deducción de tipo de plantilla, no se puede deducir T ; al igual que el mensaje de error dice, la plantilla candidata (es decir, binsearch ) se ignora.

Puede usar operator+ para lograr esto, convertirá lambda en puntero de función, que se pasará a binsearch más tarde y luego se binsearch T con éxito ^[1] .

binsearch(a, +[](int e) -> bool { return e >= 5; });
//           ~

Por supuesto que podrías usar static_cast explícitamente:

binsearch(a, static_cast<bool(*)(int)>([](int e) -> bool { return e >= 5; }));

Tenga en cuenta que si cambia el tipo de predicate para que sea independiente de T , es decir, bool (*predicate)(int) , pasar lambda con la lista de captura vacía también funcionaría; La expresión lambda se convertirá implícitamente en puntero a función.

Otra solución es cambiar el tipo de parámetro de puntero a función a función std::function , que es más general para los functores:

template <typename T> int binsearch(const std::vector<T> &ts, std::function<bool (typename std::vector<T>::value_type)> predicate) {
    ...
}

entonces

binsearch(a, [](int e) -> bool { return e >= 5; });

^{[1] Un lambda positivo: ''+ [] {}'' - ¿Qué brujería es esta?}

Answer 3

Si tiene algún control sobre binsearch le sugiero que lo refactorice:

template <typename T, typename Predicate>
int binsearch(std::vector<T> const& vec, Predicate&& pred) {
    // This is just to illustrate how to call pred
    for (auto const& el : vec) {
        if (pred(el)) {
            // Do something
        }
    }
    return 0; // Or anything meaningful
}

Otra forma para usted es realizar el borrado de tipo en sus objetos de functor / punteros de función / lo que sea ... incrustándolos en una std::function<bool(T const&)> . Para hacerlo, simplemente reescriba la función anterior como:

template <typename T>
int binsearch(std::vector<T> const& vec, std::function<bool(T const&)> pred);

Pero como la deducción de argumentos de la plantilla no realiza ninguna conversión, debe alimentar explícitamente su función como la siguiente:

auto my_predicate = [](int x) { return true; }; // Replace with actual predicate
std::vector<int> my_vector = {1, 2, 3, 4};
binsearch(my_vector, std::function<bool (int const&)>(my_predicate));

Sin embargo, dada la descripción de su función, parece que hace el mismo trabajo que std::find_if .

std::vector<int> my_vector = {1, 12, 15, 13, 16};
auto it = std::find_if(std::begin(my_vector), std::end(my_vector),
                       [](int vec_el) { return !vec_el%5; });
// it holds the first element in my_vector that is a multiple of 5.
if (it != std::end(my_vector)) {
    std::cout << *it << std::endl; // prints 15 in this case
}

Tenga en cuenta que para realizar una búsqueda binaria, necesita algo más que un predicado: necesita un predicado que defina un orden en su rango Y un valor objetivo.

Answer 4

Su función binsearch toma un puntero a función como argumento. Un lambda y un puntero de función son tipos diferentes: un lambda puede considerarse como una instancia de un operator() implementador de estructura operator() .

Tenga en cuenta que las lambdas sin estado (lambdas que no capturan ninguna variable) se pueden convertir implícitamente en puntero de función. Aquí la conversión implícita no funciona debido a la sustitución de plantillas:

#include <iostream>

template <typename T>
void call_predicate(const T& v, void (*predicate)(T)) {
    std::cout << "template" << std::endl;
    predicate(v);
}

void call_predicate(const int& v, void (*predicate)(int)) {
    std::cout << "overload" << std::endl;
    predicate(v);
}

void foo(double v) {
    std::cout << v << std::endl;
}

int main() {
    // compiles and calls template function
    call_predicate(42.0, foo);

    // compiles and calls overload with implicit conversion
    call_predicate(42, [](int v){std::cout << v << std::endl;});

    // doesn''t compile because template substitution fails
    //call_predicate(42.0, [](double v){std::cout << v << std::endl;});

    // compiles and calls template function through explicit instantiation
    call_predicate<double>(42.0, [](double v){std::cout << v << std::endl;});
}

Debes hacer que tu función binsearch más genérica, algo como:

template <typename T, typename Predicate>
T binsearch(const std::vector<T> &ts, Predicate p) {

    // usage

    for(auto& t : ts)
    {
        if(p(t)) return t;
    }

    // default value if p always returned false

    return T{};
}

Tomar inspiración de la biblioteca de algoritmos estándar .

Answer 5

Un puntero de función y una función lambda no son lo mismo.

No se puede asignar un objeto t al predicado donde:

 bool (*predicate)(int)

y

auto t = [](int e) -> bool { return e >= 5; });

También podría usar std::function<bool(int)> . Tu firma se verá así:

template <typename T> 
int binsearch(const std::vector<T> &ts, std::function<bool(T)> predicate){
   // ...
}

Ahora que no es un puntero de función, tendrá que enlazar los punteros de su función si son necesarios (supongo que está bien solo con las lambdas)