C++: template function taking function which takes another function which takes reference to template type as parameter

Question

Consider following code

struct S
{
    unsigned u;
    float f;

    S(unsigned u0, float f0) : u(u0), f(f0) {}
};

template<typename T> bool contains(std::vector<T> vec, T elem, bool equivalent(const T&, const T&))
{
    // some implementation
}

int main() {
    std::vector<S> vec{{15, 17.8}};

    std::cout << contains(vec, S(15,159.48), [](S& a, S& b) -> bool {return a.u == b.u;}) << std::endl;
}

Why this code does not compile and how to fix it? I believe that it is clear what the function contains should do from the context.

I get following error:

main.cpp:32:18: error: no matching function for call to 'contains'
    std::cout << contains(vec, S(15,159.48), [](S& a, S& b) -> bool {return a.u == b.u;}) << std::endl;
                 ^~~~~~~~
main.cpp:14:27: note: candidate template ignored: could not match 'bool (*)(const T &, const T &)' against '(lambda at main.cpp:32:46)'
template<typename T> bool contains(std::vector<T> vec, T elem, bool equivalent(const T&, const T&))

Answer 1

Why this code does not compile and how to fix it? I believe that it is clear what the function contains should do from the context.

The problem is that a lambda isn't a function; it's an object with a function (operator()) inside it.

In your case, given that the lambda doesn't capture, can be converted to a function pointer.

So why the compiler doesn't convert the lambda in a function pointer? There is another problem; a sort of chicken-and-egg problem: the deduction of the T template type.

The template contains()

template <typename T>
bool contains(std::vector<T> vec, T elem, bool equivalent(const T&, const T&))

use the T type for all the arguments: for vec, for elem and for equivalent. So the compiler try to deduce T from all the arguments.

Given that the compiler try to deduce T also form the third argument (chicken and egg problem) can't deduce T from the lambda because the lambda ins't a function pointer and can't convert the lambda in a function pointer because doesn't deduce T from the lambda.

I see four possible solutions.

1. The first one is the solution in the sklott answer: define contains(), using std::type_identity, as follows

template <typename T>
bool contains (std::vector<T> vec, T elem, std::type_identity_t<bool(*)(const T&, const T&)> equivalent) 

or also as follows

template<typename T>
bool contains (std::vector<T> vec, T elem, std::type_identity_t<bool(const T&, const T&)> equivalent)

This way you inhibit the T deduction from equivalent, T is deduced (as S) from vec and elem, so the compiler can convert the lambda to a function or to a function pointer.

2. Use another template typename (as suggested in a comment) for a the function or functional

template <typename T, typename F>
bool contains (std::vector<T> vec, T elem, F equivalent)

This way equivalent can be directly a lambda, without conversion. So you can also accept a capturing lambda (that can't be converted to a function). The disadvantage is that you can't force that equivalent receive two T const & arguments, but the use of equivalent should be enough to check inconsistencies

3. You can leave unmodified the contains() function but you can change the call, using the + operator in front of the lambda so forcing the conversion of the lambda to a function pointer

// .........................V  the '+' operator force the conversion
contains(vec, S(15,159.48), +[](S const & a, S const & b)... 

But remember to define the lambda receiving two S const &, as in function definition, not two S &, as in your example.

This way the compiler receive a function pointer correctly deduce S, for T, also from the third argument.

4. You can leave unmodified the contains() function and explicit the template type in the call

// .....VVV  S type is explicit, no type deduction take place
contains<S>(vec, S(15,159.48), [](S const & a, S const & b)... 

This way the call explicit the S type, for T. So no type deduction take place, so the compiler can convert the lambda to a function

Answer 2

It can be fixed by adding std::type_identity_t for 3rd parameter, so that it will not participate in deducing template parameters:

#include <iostream>
#include <vector>
#include <type_traits>

struct S
{
    unsigned u;
    float f;

    S(unsigned u0, float f0) : u(u0), f(f0) {}
};

template<typename T> bool contains(std::vector<T> vec, T elem, std::type_identity_t<bool (*)(const T&, const T&)> equivalent)
// Can also use following synaxis: std::type_identity_t<bool(const T&, const T&)> *equivalent
{
    // some implementation
}

int main() {
    std::vector<S> vec{{15, 17.8}};

    std::cout << contains(vec, S(15,159.48), [](const S& a, const S& b) -> bool {return a.u == b.u;}) << std::endl;
}

If you don't have C++20 you can easily define it youself:

template< class T >
struct type_identity {
    using type = T;
};

template< class T >
using type_identity_t = typename type_identity<T>::type;