Type deduction resullts in ambiguous call of overloaded function

While mixing type deduction with overloading, I stumbled upon a behavior of type deduction for lambda functions that I find difficult to understand.

When compiling this program:

#include <functional>
#include <cstdlib>
int case_0(int const& x) {
    return 2*x;
}
int case_1(int& x) {
    x += 2;
    return 2*x;
}
class Test {
    public:
        Test(int const n) : n(n) {}
        int apply_and_increment(std::function<int(int const&)> f) {
            n++;
            return f(n);
        }   
        int apply_and_increment(std::function<int(int&)> f) {
            return f(n);
        }   
    private:
        int n;
};
int main() {
    Test t(1);
    auto f = [](int const& x) -> int {
        return 3*x;
    };  
    
    t.apply_and_increment(case_0);                                 // Fails compilation
    t.apply_and_increment(std::function<int(int const&)>(case_0)); // Succeeds
    t.apply_and_increment(case_1);                                 // Succeeds
    t.apply_and_increment(f);                                      // Fails compilation
    return EXIT_SUCCESS;
}

The output of the compilation is:

$ g++ -std=c++20 different_coonstness.cpp -o test 
different_coonstness.cpp: In function ‘int main()’:
different_coonstness.cpp:34:30: error: call of overloaded ‘apply_and_increment(int (&)(const int&))’ is ambiguous
   34 |  t.apply_and_increment(case_0);
      |                              ^
different_coonstness.cpp:16:7: note: candidate: ‘int Test::apply_and_increment(std::function<int(const int&)>)’
   16 |   int apply_and_increment(std::function<int(int const&)> f) {
      |       ^~~~~~~~~~~~~~~~~~~
different_coonstness.cpp:20:7: note: candidate: ‘int Test::apply_and_increment(std::function<int(int&)>)’
   20 |   int apply_and_increment(std::function<int(int&)> f) {
      |       ^~~~~~~~~~~~~~~~~~~
different_coonstness.cpp:37:25: error: call of overloaded ‘apply_and_increment(main()::<lambda(const int&)>&)’ is ambiguous
   37 |  t.apply_and_increment(f);
      |                         ^
different_coonstness.cpp:16:7: note: candidate: ‘int Test::apply_and_increment(std::function<int(const int&)>)’
   16 |   int apply_and_increment(std::function<int(int const&)> f) {
      |       ^~~~~~~~~~~~~~~~~~~
different_coonstness.cpp:20:7: note: candidate: ‘int Test::apply_and_increment(std::function<int(int&)>)’
   20 |   int apply_and_increment(std::function<int(int&)> f) {
      |       ^~~~~~~~~~~~~~~~~~~

As far as I understand:

• case_0 is ambiguous because there are 2 valid type conversions, std::function<int(const int&)> and std::function<int(int&)>, and both overloaded functions apply_and_increment() can be applied. This is why the explicit type conversion std::function<int(int const&)>(case_0) is required.

• in case_1, the only valid conversion is std::function<int(int&)>, so there is no ambiguity.

I am not very familiar with type deduction and lambdas, so I am a bit surprised that t.apply_and_increment(f) fails to compile. I would expect that the type of the function would be deduced by the type signature, [](int const& x) -> int, in the lambda function.

Why is not f of type std::function<int(int const&)>?

Your understanding of overload resolution for case_0 and case_1 is correct:

• A reference-to-non-const can be assigned to a reference-to-const, hence case_0() is callable from both of the std::function types being used, thus overload resolution is ambiguous when an implicit conversion is used, requiring you to specify the desired std::function type explicitly.

• A reference-to-const cannot be assigned to a reference-to-non-const, hence case_1() is not callable from std::function<int(int const&)>, only from std::function<int(int&)>, thus overload resolution is not ambiguous when an implicit conversion is used.

A standalone function is not itself a std::function object, but can be assigned to a compatible std::function object.

Likewise, a lambda is not itself a std::function object, it is an instance of a compiler-defined functor type, which can be assigned to a compatible std::function object.

In both cases, std::function acts as a proxy, passing its own parameters to the function/lambda's parameters, and then returning whatever the function/lambda returns.

So, overload resolution fails for both case_0 and f for the exact same reason. When the compiler has to implicitly convert case_0/f into a std::function object, the conversion is ambiguous because case_0/f is callable from both of the std::function types being used.