Pick the right overload when passing function pointer to algorithm

Question

The Problem

Please bear with me, this is really just an example:

#include <algorithm>
#include <iterator>
struct foo {
    static int my_transform(int x) { return x;}
    static std::vector<int> my_transform(std::vector<int> x){
        std::vector<int> result;            
        std::transform(x.begin(),x.end(),std::back_inserter(result),my_transform);
        return result;
    }
};

What I expect to happen

There are two possible overloads for my_transform, but only one results in a well-formed template instantiation, while for the other the template instantiation is ill-formed. I would expect the ill-formed one to be discarded and the above to compile.

What really happens

 main.cpp:165:75: error: no matching function for call to
 ‘transform(std::vector<int>::iterator, std::vector<int>::iterator, 
 std::back_insert_iterator<std::vector<int> >, <unresolved overloaded function type>)’
   std::transform(x.begin(),x.end(),std::back_inserter(result),my_transform);
                                                               ^

How to fix it

Casting the function pointer to the right type resolves the ambiguity and it compiles:

static std::vector<int> foo::my_transform(std::vector<int> x){
    std::vector<int> result;
    typedef int (*my_transform_t)(int);     
    std::transform(x.begin(),
                   x.end(),
                   std::back_inserter(result),
                   static_cast<my_transform_t>(my_transform));
    return result;
}

The Question

What exactly prevents the compiler from choosing the "correct" overload? Considering that only one can result in a valid template instantiation there isnt really a ambiguity.

PS: Note that this is C++98. In C++11 and beyond, the problem can be easily avoided by using lambdas (thanks to @appleapple for pointing that out).

Answer 1

Considering that only one can result in a valid template instantiation there isn't really a ambiguity.

But there is! You are just too quick. std::transform takes a template parameter and that parameter needs to be deduced. But you are passing it an overload set and the the parameter can't be deduced.

You might think that SFINAE also applies here too, but this is not the case. SFINAE happens when substituting template parameters for functions, but nowhere else. Here there is no substitution, because the compiler can't even reach that point because of the overload set deduction failure. Also, SFINAE applies to function parameters, not to the body of the function.

Basically: the compiler will not instantiate multiple possible templates and look which one is the only one that compiles. That would get complicatd quickly.

This is described in [temp.deduct.type]p5:

A function parameter for which argument deduction cannot be done because the associated function argument is a function, or a set of overloaded functions ([over.over]), and one or more of the following apply: (5.5.1)

• more than one function matches the function parameter type (resulting in an ambiguous deduction), or

• [...]

And so we have a non-deduced context. What now? According to [temp.deduct]p4:

[...]. If a template parameter is used only in non-deduced contexts and is not explicitly specified, template argument deduction fails. [...]

And we're done!