Compiler cannot deduce type of template function?

Question

I have the following code sample:

template<typename T>
void print(T t) {
    std::cout << t << std::endl;
}

template<typename Key, typename Value, typename F>
void traverse(std::map<Key, Value>& m, F f) {
    for (auto&& [key, value] : m) {
        f(value);
    }
}

int main()
{
    std::map<int, std::string> M;
    // initializing the map
    traverse(M, print);
}

Here the compiler erred with the following message:

could not deduce template argument for 'F'

The explicit traverse(M, print<std::string>); solves the problem.
My question really is why compiler cannot deduce the template type for the print function?

As far as I understand, all the compile time information is available.

Answer 1

Template argument deduction works on the basis of the template parameters of the function, the signature of the function, and the types of the arguments provided. Nothing more. Even ignoring the fact that print is a template function (and therefore doesn't have a type that could be used for deduction), there is nothing in the signature of traverse that would give the compiler any idea that the type to deduce would be the type of print<std::string>. Any such information would be in the function's definition.

A definition that doesn't exist yet and cannot exist until traverse has been instantiated. And you can't instantiate a template until you have the template parameters. Which is what template argument deduction is intended to figure out.

Also, as previously mentioned, print is not a function; it is the name of a template. It has no type; it isn't even a function. It is a means for generating a function, based on template parameters. Even if you tried to pass print to a function that wasn't a template, the code still wouldn't work. The compiler can perform template argument deduction for functions only when you call them, not when you pass them as function arguments. In all non-deduced cases, you have to provide the template arguments directly.

Answer 2

Not all the necessary compile time information is available, specifically, not the print template instantiation arguments.

traverse is a function template, which accepts any argument type for the second argument, however the name print itself doesn't denote any specific type, only a template name, and the compiler cannot deduce which specific instantiation of that template you intend to pass to it.

Apparently you wish the compiler to deduce the print<std::string> instantiation of print, from the template argument of M's type. To achieve that, you can specify this in the traverse template, making the f parameter's type dependent on the m's type, removing the unrelated typename F, for example, like this:

template<typename Key, typename Value>
void traverse(std::map<Key, Value>& m, void (*f)(Value)) {
    for (auto&& [key, value] : m) {
        f(value);
    }
}

Answer 3

The compiler cannot deduce the type of print because it ignores the body of traverse and all unrelated arguments. When you call traverse(M, print) the compiler tries to determine the type of print as if you had just called this example:

template<typename F>
void example(F f);

example(print);

You can get your code to compile by changing the type of traverse with:

template<typename Key, typename Value>
void traverse(std::map<Key, Value>& m, void(*f)(Value));

or by specifying a specific print:

    traverse(M, print<std::string>);