rule for template deduction for overloaded recursive function in c++

Question

I have found a lot of information about template deduction (eg C++ templated function overloading rules) but it does not help me understand the behaviour of template deduction for an overloaded recursive function. In the following code, I do not really understand how the compiler managed to deduce that it should use the vector<T> function two times for vectvect and the pair<T,U> two times for pairpair - but it can. Thus, I do not understand why it can not deduce that it should use both vector<T> and pair<T,U> function for vectpair ?

Is this something to do with why the const keyword leads to increase the conversion and thus make the T function better ? (But how do the two other examples can work in this case ?)

Is the two first deduction only possible because the current function is tested first for the template deduction in a recursive call ?

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

template<class T> string print(const T& t){
    ostringstream s;
    s << t;
    return s.str();
}

template<class T> string print(const vector<T>& t){
    ostringstream s;
    s << '[';
    for(int i=0;i<(int)t.size();i++)
        s << print(t[i]) << ' ';
    s << ']';
    return s.str();
}

template<class T,class U> string print(const pair<T,U>& t){
    ostringstream s;
    s << '(' << print(t.first) << ',' << print(t.second) << ')';
    return s.str();
}

int main ( int argc, char **argv ) {
    vector<vector<double> > vectvect(4,vector<double>(4));
    for(int i=0;i<(int)4;i++)
        for(int j=0;j<(int)4;j++)
            vectvect[i][j] = i*4+j;
    pair<int,pair<string,double> > pairpair = make_pair(10, make_pair("foo",0.5));
    vector<pair<int,string> > vectpair(1,make_pair(42,"bar"));

    ///template deduction
    cout << print(vectvect) << endl;
    cout << print(pairpair) << endl;

    ///template deduction failure
    //====> here is the problem 
    //cout << print(vectpair) << endl;

    return 0;
}

Currently, I am just trying to understand, but if somebody knows how to do it without introducing large source overhead, I am interested.

Thank you.

Because the `print(const pair& t)` overload should be *at least* declared before the one calling it — Piotr Skotnicki, Sep 30 '15 at 19:47

score 2 · Accepted Answer · answered Sep 30 '15 at 20:01

The problem is not related to template argument deduction, neither to overload resolution. The print overload taking a pair is not picked by the compiler because it can't be found by unqualified name lookup, neither by ADL. You should either reorder the two definitions of your functions, so that the one taking a pair comes first:

template <class T,class U> string print(const pair<T,U>& t){
    /**/
}

template <class T> string print(const vector<T>& t){
    /**/
}

or declare all functions before you define and use them:

template <class T> string print(const T& t);
template <class T,class U> string print(const pair<T,U>& t);    
template <class T> string print(const vector<T>& t);

score 1 · Answer 2 · answered Sep 30 '15 at 20:03

Your problem is that when you're trying to print a vector<pair<X>>, this call with the vector overload:

s << print(t[i]) << ' ';

can't find the pair<T,U> overload because unqualified lookup happens at point of definition, not later. So it calls your generic print(const T&) not because of some break in template ordering rules but rather because the pair<T, U> overload simply isn't visible.

If only I could say Argument-Dependent Lookup in the Leeroy Jenkins voice. That would be awesome. Anyway, the cool thing about ADL is that lookup happens later. So you don't have to worry about making sure all your functions are predefined. Just throw in a extra argument and let ADL do its thing. At top-level, we just forward:

template <typename T>
string print(T const& val)
{
    return print(adl::helper{}, val);
}

And then we define all our same print functions within namespace adl:

namespace adl {
    struct helper{};

    template<class A, class T> string print(A, const T& t){
        ostringstream s;
        s << t;
        return s.str();
    }

    template<class A, class T> string print(A, const vector<T>& t){
        ostringstream s;
        s << '[';
        for(int i=0;i<(int)t.size();i++)
            s << print(helper{}, t[i]) << ' ';
        s << ']';
        return s.str();
    }

    template<class A, class T,class U> string print(A, const pair<T,U>& t){
        ostringstream s;
        s << '(' << print(helper{}, t.first) << ',' << print(helper{}, t.second) << ')';
        return s.str();
    }
}

No ordering issues anywhere. Now we can even print a vector of pair of vector of pair of ...

rule for template deduction for overloaded recursive function in c++

2 Answers2