How c++ deduce the right overloaded function?

There was 5 different versions of pow, in C++98:

double pow (double base, double exponent);
float pow (float base, float exponent);
long double pow (long double base, long double exponent);
double pow (double base, int exponent);
long double pow (long double base, int exponent);

My teacher told me, that before c++11 (before adding template version of pow), there could be an error where c++ can't deduce which overloading to choose. That seemed reasonable to me. For example consider this code:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    cout << pow(4, 3);
    cin.get();
}

I'm calling pow() function with two integer arguments. I don't have such overloading of pow(), so maybe I should do some implicit conversions? Ok, but which one to choose? I can't choose how to convert since I have ambiguity in choosing of the overloading. But I tried to compile this piece of code (in std=c++98 mode) and it worked. Why?

Ok, maybe it's because of second argument being integer. Therefore I have to choose only between double pow (double base, int exponent) and long double pow (long double base, int exponent). But still which one compiler decides to choose? What if I called pow(4, 3ll)? It still compiles but type deducing for me is less obvious.

upd: Maybe it is a bad idea to see how deducing works here, because I may never know how pow really implemented. Or is it?

Solution

tl;dr:

std::pow is a difficult example due to compilers providing more overloads & the c version being considered a builtin in gcc, so your problem is rather hard to demonstrate with it.
yes the call will actually be ambigous if the 5 functions you listed are the only ones competing in overload resolution.

pow() is a rather tricky function to use for this, since there are a few gotchas:

In your godbolt example your actually calling std::pow<int, int>, i.e. a templated version of it. This is because you're using a rather new version of gcc that provides a templated overload of std::pow for better performance.

You can see this quite nicely in the generated assembly, line 6: (look at the end)
```
call    __gnu_cxx::__promote_2<int, int, __gnu_cxx::__promote<int, std::__is_integer<int>::__value>::__type, __gnu_cxx::__promote<int, std::__is_integer<int>::__value>::__type>::__type std::pow<int, int>(int, int)
```
So for testing this you could do a few things:
- switch to an older version of gcc that doesn't have the templated overload yet, i.e. gcc 4.1.2:
  godbolt example
- or test it with user-specified functions, like the example from @mch:
  godbolt example
Another problem is <cmath> itself - since it is the c++ equivalent of <math.h> in c, gcc and clang do expose the c pow function as well in it (without std:: prefix) - this is why your code works even when removing using namespace std;.
Since c doesn't allow function overloads there's only one version with double's. (the float version is powf, the long double one powl).
Additionally gcc considers them to be built-ins, so in this case it can just completely get rid of the pow call since it uses constants as arguments, even at -O0.
This is what happened in the example provided by @ Aanchal Sharma: godbolt example
```
mov     rax, QWORD PTR .LC0[rip]
movq    xmm0, rax
// calculated value (64 as a double)
.LC0:
      .long   0
      .long   1078984704
```
so gcc just calculated the result at compile-time and inlined it. (note there's no overload resolution problem at all here, since there's only one pow function in c - and the c++ functions aren't available because using namespace std; is not commented in)

You can suppress this by passing -fno-builtin as a compiler argument, in which case gcc will dutifully emit the call to double pow(double, double): godbolt example
```
movsd   xmm0, QWORD PTR .LC0[rip]
mov     rax, QWORD PTR .LC1[rip]
movapd  xmm1, xmm0
movq    xmm0, rax
call    pow

.LC0: // 3 as a double
   .long   0
   .long   1074266112
.LC1: // 4 as a double
   .long   0
   .long   1074790400
```

So to answer your questions:

1. Why does it work?

Because gcc actually provides a templated overload of std::pow that is a perfect match in this case:

template<typename _Tp, typename _Up>
inline typename __gnu_cxx::__promote_2<_Tp, _Up>::__type pow(_Tp __x, _Up __y);

2. Assuming there would be no template overload, how would the compiler decide which overload to use?

The rules for determining the best overload are rather complicated, so i'll simplify them a bit (i'll completely ignore user-defined conversion functions, templated functions, variadic functions and a few other things not relevant to the question)

If you want to get a more complete picture of the actual rules you can take a look at the c++98 standard, section 13.3 Overload resolution is what you're looking for.

Now to get into it:

First all functions are eliminated that don't have the right number of arguments. i.e. if there would be a pow function taking three arguments (and the third argument doesn't have a default value) - it would be directly eliminated.

13.3.2 Viable functions

(1) First, to be a viable function, a candidate function shall have enough parameters to agree in number with the arguments in the list.
Secondly the parameters you provided actually need to be convertible to the parameters of the overload in question. If there's no way to convert between them the overload would be eliminated.

13.3.2 Viable functions

(3) Second, for F to be a viable function, there shall exist for each argument an implicit conversion sequence (13.3.3.1) that converts that argument to the corresponding parameter of F.
After that the compiler has a set of overloads left - the standard calls them Viable functions - that could be called in the given context. Now the compiler needs to actually decide which of those is the best one, i.e. the Best Viable Function, that should end up being called.
Now we get to the fun part - rating overloads based on how good of a fit they are. There are basically three primary categories a parameter conversion can have:
Exact Match > Promotion > Conversion ¹
- Exact Match is the best one, this applies if the types match exactly or if it's just decaying an array to a pointer or function to a function pointer.
- Promotion is slightly worse, this applies if you e.g. convert from one integral type to a bigger one or from a floating point type to a bigger one (but not between integral and floating points, and not to smaller types)
- Conversion is the worst one and covers "downgrading" of int and float types (e.g. int -> char, double -> float) and conversion between integral and floating point types, e.g. int -> double.
The compiler doesn't care what the exact conversion is, only in which of the three categories it falls. ²

So you could think of it that way: ³
- Each function gets a score based on the conversions needed for the arguments
- Exact Match is worth 0 points
- Promotion is worth -1 points
- Conversion is worth -2 points
- the function with the highest score gets called
- it there's a draw, the call is ambigous

So now to actually rank the std::pow overloads:

// when called as pow(1, 1)

// 2x Conversion -> score -4
double pow (double base, double exponent);

// 2x Conversion -> score -4
float pow (float base, float exponent);

// 2x Conversion -> score -4
long double pow (long double base, long double exponent);

// 1x Conversion, 1x Exact -> score -2
double pow (double base, int exponent);

// 1x Conversion, 1x Exact -> score -2
long double pow (long double base, int exponent);

So the first 3 are already off the table, because their score is worse.
This leaves the last 2, but those actually have the same score, so it's a draw!
-> You'll get an ambigous function call error

Footnotes:
_{¹ there are a few more rules for user-defined conversion functions, vararg functions and templates

(see 13.3.3.1 Implicit conversion sequences)}
_{² In reality there are quite a few more things to consider

(see 13.3.3.2 Ranking implicit conversion sequences for a complete list)}
_{³ Extremely simplified version. This is not how an actual compiler would do it.}