ADL does not find templated free function

Question

I tried to understand how ADL works, at least its basics, and created following piece of code:

#include <iostream>
#include <string>
#include <vector>  

using std::pair;
using std::string;
using std::vector;

namespace My {
    using std::to_string;

    /** With these forward declarations it works ...
    string to_string(char arg);
    const string& to_string(const string& str);
    template <typename T>
        string to_string(const vector<T>& rhs);
    template <typename T1, typename T2>
        string to_string(const pair<T1, T2>& rhs);
    struct A;
    string to_string(const A& rhs);
    */

    string to_string(char arg)
    {
        return string(1, arg);
    }

    const string& to_string(const string& str)
    {
        return str;
    }

    template <typename T>
    string to_string(const vector<T>& rhs)
    {
        string str("");
        for (const auto& e : rhs) {
            str += to_string(e) + " ";      //< this fails with `pair<..>`
            /// `(to_string)(e)` would fail even with `A`
        }
        return str;
    }

    template <typename T1, typename T2>
    string to_string(const pair<T1, T2>& rhs)
    {
        return to_string(rhs.first) + " " + to_string(rhs.second);
    }

    struct A {
        static int counter;
        string to_string() const
        {
            using My::to_string;    //< avoid using `A::to_string`
            return to_string("<A>[") + to_string(counter++) + to_string("]");
        }
    };
    int A::counter = 0;

    string to_string(const A& rhs)
    {
        return rhs.to_string();
    }
}

int main(int /*argc*/, const char* /*argv*/[])
{
    using My::to_string;
    using My::A;
    using std::cout;
    using std::endl;

    cout << to_string(3.1415) << endl;
    cout << to_string(pair<int, char>{5, 'a'}) << endl;
    cout << to_string(pair<double, pair<int, int>>{3.14, {1, 2}}) << endl;
    cout << to_string(vector<int>{1, 2, 3}) << endl;
    cout << to_string(pair<string, vector<int>>{"key", {1, 2, 3}}) << endl;
    cout << to_string(pair<string, A>{"key", {}}) << endl;
    cout << to_string(vector<A>{{}, {}, {}}) << endl;
    /// this will fail to compile
    cout << to_string(vector<pair<string, int>>{{"a", 1}, {"b", 2}}) << endl;

    return 0;
}

I figured out that, inside of My, using std::to_string will use std:: free function if it exists and will use My:: otherwise. Then, outside of namespace My, it is sufficient to do using My::to_string to cover both cases. Fine so far.

Then I used the same technique inside member function A::to_string to avoid preferring the function itself instead of free functions (the same will apply for any other member function).

Finally, I was a little surprised that to_string(vector<A>) compiles, although A is not forward-declared. That's where ADL kicks in, as I've understood. Disabling it (enclosing to_string into brackets) will cause compilation failure.

Now after the long story, here goes my question: why ADL does not work in this case for templated function, i.e. to_string(pair<T1, T2>)? And more importantly, how to fix it? I would be glad if it was not necessary to perform forward declarations, as in my use case the definition of to_string(vector<T>) is located in some base header file and the latter definitions are in different headers and are not supposed to be known at this time.

EDIT:

I tried to somehow "fake" needed forward declarations by some templates or even with some SFINAE, but it either led to ambiguities or to the same result. Finally, I came up with solution which uses member function to_string (but it could be any other name) of desired class. This requires to always implement this function if compatibility with to_string is desired, which in case of STL containers requires to inherit them and add the member function. But I believe that in this case ADL will never fail.

Here are modified parts of the code:

template <typename T,
          typename Fun = decltype(&T::to_string),
          typename = std::enable_if_t<
              std::is_member_function_pointer<Fun>::value>>
string to_string(const T& rhs)
{
    return rhs.to_string();
}

template <typename T>
struct Vector : public vector<T> {
    using vector<T>::vector;

    string to_string() const
    {
        using My::to_string;    //< avoid using `Vector::to_string`
        string str("");
        for (const auto& e : *this) {
            str += to_string(e) + " ";
        }
        return str;
    }
};

template <typename T1, typename T2>
struct Pair : public pair<T1, T2> {
    using pair<T1, T2>::pair;

    string to_string() const
    {
        using My::to_string;    //< avoid using `Pair::to_string`
        return to_string(this->first) + " " + to_string(this->second);
    }
};

However, one has to replace vectors and pairs with Vectors and Pairs. (Free function to_string(A) is not needed any more).

Other solutions, comments?

Answer 1

why ADL does not work in this case for templated function, i.e. to_string(pair<T1, T2>)?

ADL works by inspecting the namespaces associated with the types involved in a given call. It then will consider the appropriate overloads found in those namespaces and select the best one.

to_string(vector<pair<string, int>>{{"a", 1}, {"b", 2}})

This call will select the overload My::to_string(const vector<T>&) and this in turns calls to_string(std::pair<std::string, int>).

ADL inspect then the namespaces associated with std::pair, std::string and int to look for the overload to_string(std::pair<...>). Since no such overload is defined in the namespace std it needs to find the definition previous to the call, but the overload My::to_string(const pair<T1, T2>&) is defined after. That's why you need to forward declare it.

Notice that you need to forward declare it because you also have this:

to_string(pair<string, vector<int>>)

---

If, on the other hand, you had something like:

to_string(vector<pair<string, My::A>>{{"a", {}}, {"b", {}}})

Then, one of the associated namespaces for the call will be My itself and the overload to_string(std::pair<...>) will be found without the need to forward declare it.