Compiler chooses erroneous overload instead of valid overload

Question

Take a look at this code:

#include <vector>
#include <functional>

template<typename RandIt, typename T, typename Pred>
auto search_with(RandIt begin, RandIt end, const T& value, Pred&& pred) noexcept {
    //...
    return begin;
}

template<typename RandIt, typename T>
auto search_with(RandIt begin, RandIt end, const T& value) noexcept {
    return search_with(begin, end, value, std::less<T>{});
}

template<typename Array, typename T, typename Pred>
auto search_with(const Array& array, const T& value, Pred&& pred) noexcept {
    return search_with(std::begin(array), std::end(array), value, std::forward<Pred>(pred));
}

int main() {
    std::vector<int> v = { 1, 2, 3 };
    search_with(v, 10, std::less<int>{}); // ok
    search_with(v.begin(), v.end(), 10);  // fail!
}

I do not understand why in the second search_with call, the compiler selects the third overload. If I comment out the third overload, then the code compiles fine. This indicates that the second overload is not discarded as it does compile, and it should be a valid overload.

However, the third overload is chosen, which fails, as there is no specialization of std::begin (and std::end) for iterators:

main.cpp: In instantiation of 'auto search_with(const Array&, const T&, Pred&&) [with Array = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; T = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; Pred = int]':
main.cpp:23:39:   required from here
main.cpp:17:34: error: no matching function for call to 'begin(const __gnu_cxx::__normal_iterator<int*, std::vector<int> >&)'
     return search_with(std::begin(array), std::end(array), value, std::forward<Pred>(pred));
                        ~~~~~~~~~~^~~~~~~

I would have thought that the opposite happens: the third overload is discarded because it fails to compile, and the second one is chosen.

But that is obviously not the case, so what is happening here? Why is the wrong overload being chosen? Why is the third overload a better match then the second one?

Answer 1

It mostly has to do the third argument, which is an rvalue. Try the following to see why it matches the universal reference better.

#include <iostream>

template <typename T>
inline void f(T &)
{
    std::cout << "f2" << std::endl;
}

template <typename T>
inline void f(const T &)
{
    std::cout << "f3" << std::endl;
}

template <typename T>
inline void f(T &&)
{
    std::cout << "f4" << std::endl;
}

int main()
{
    int a = 0;
    const int b = 0;
    int &c = a;
    const int &d = b;
    f(1); // f4 : rvalue matched by universal reference
    f(a); // f2 : lvalue matched by reference, T& preferred to const T&
    f(b); // f3 : lvalue matched by reference, can only do const T&
    f(c); // f2 : lvalue reference matched by reference, T& preferred to const T&
    f(d); // f3 : lvalue const reference matched by reference, can only do const T&
    f(std::move(a)); // f4 : rvalue reference, matched by universal reference

}

If you throw one more overload,

 template <typename T>
 inline void f(T);

into the mix, you will get ambiguous errors, because it will also give you perfect match.

As to the first two rvalue arguments, consider the following example,

template <typename T>
inline void f(T)
{
}

template <typename T>
inline void f(const T &)
{
}

int main() { f(1); }

You will get an ambiguous error. That is, the two overloads match an rvalue equally well. So they do not determine which overload is selected in your example