C++ templates question

C08546fc4340f0be3109019ef869ac9e
0
lightxbulb 101 Jun 02, 2013 at 09:24 c++

Hi!
I’m learning to use templates and I would like some help. Can anybody tell me what is wrong with my logic in this case:

#include <iostream>
#include <typeinfo>
using namespace std;
template <typename T>
class someContainer
{
private:
    T val1;
    T val2;

public:
    someContainer(const T& in1, const T& in2)
        :val1(in1), val2(in2) {}
    template <typename Ret>
    void sort(Ret (*_comp)(const T&, const T&))
    {
        cout << "Comp is of type: " << typeid(_comp).name() << endl;
        cout << _comp(val1, val2) << endl;
        return;
    }
};

template <typename R>
bool compare(const R& a, const R& B)
{
    return a>b;
}

int main()
{
    someContainer<int> myCont(7,6);
    myCont.sort<bool>(compare<int>);
    /*
    I. myCont.sort<bool>(compare<int>);
    Both specilaizations(for sort and for compare) are explicitly stated
    */

    myCont.sort(compare<int>);
    /*II. myCont.sort(compare<int>);
    passes <int> as an argument to the template of compare(), so we get a int specialization for function compare(),
    from there the compiler gets("infers" - doesn't need to have sort<bool> explicitly stated)
    the return type of compare<int>, which is bool, and passes it as an argument for sort(so we get a sort<bool> specialization for sort)
    */

    myCont.sort<bool>(compare);
    /*
    III. myCont.sort<bool>(compare);
    passes <bool> as an argument to the template of sort(), so we get a bool specialization for function compare(),
    the compiler cannot infer what specialization to use for compare just from the fact that compare returns bool(sort<bool>).
    The compiler actually "infers" the specialization of compare() from the type for which myCont is an object (someContainer<int> myCont - basically int). From this we see that compare<int>() doesn't need to be explicitly stated
    as it can be inferred from the specialization of the template for someContainer. However from the previous example we know
    that sort<bool> doesn't need to be explicitly stated too, as it can be inferred from compare<int>.
    Basically if we take into account the previous two examples and try to use:
        myCont.sort(compare);
    the compiler "should" be able to infer the specialization for compare() from "the specialization of the template for someContainer."
    And bool can be inferred from the specialization we get for compare().
    Here's what "should" happen:
    1)myConst.sort(compare)
    2)use the type(<int>) for which the class of myConst (someContainer<int>) is a specialization of someContainer as an argument for the specialization of compare()
    3)we get compare<int>()
    4)from this get the return type of compare() for a specialization of type <int> - basically get the return type of compare<int>()
    5)pass this type as an argument for a specilaization of sort()
    6) you get sort<bool>(compare<int>)
    */
    //Well, seems it doesn't work tht way - as this doesn't work:
    //myCont.sort(compare);
    cin.ignore();
    return 0;
}

/*
Here's a code-like expression of the various points from 1-5:
1)
myConst.sort(compare)
2)
From: someContainer<int> myCont(7,6) -> T = int
From:
T = int
AND
void sort(Ret (*_comp)(const T&, const T&))
->
void sort(Ret (*_comp)(const int&, const int&))
From:
void sort(Ret (*_comp)(const int&, const int&))
AND
template <typename R>
bool compare(const R& a, const R& B)
{
    return a>b;
}
->
R=int
From:
R=int
->
bool compare(const int& a, const int& B)
{
    return a>b;
}
From:
bool compare(const int& a, const int& B)
{
    return a>b;
}
->
myCont.sort(compare) == myCont.sort(compare<int>)
From:
myCont.sort(compare) == myCont.sort(compare<int>)
AND
myCont.sort<bool>(compare) == myCont.sort<bool>(compare<int>) (III.)
->
myCont.sort(compare) == myCont.sort<bool>(compare<int>)
*/

I think I am missing something vital, or I have a really flawed understanding of how templates work.
Any help will be appreciated.

5 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 03, 2013 at 05:49

I’m not enough of a C++ guru to tell you exactly why it doesn’t work in terms of the rules of C++ - but speaking generally, I think you may simply be asking too much of the compiler to infer all of that. C++ compilers, although quite smart, aren’t designed for full-blown type inference in the way that some other languages are.

I’m actually surprised that even myCont.sort<bool>(compare) works; I definitely wouldn’t expect myCont.sort(compare) to work. I think template inference works best from “inside” to “outside” of a given expression (or, to put it another way, from leaf to root in the syntax tree). For instance, inferring sort<bool> from compare<int> goes inside-to-outside. I don’t generally expect the other direction, outside-to-inside, to work in C++.

In your fourth case, you require both directions of inference to be applied in the correct order to get everything totally solved, and that especially I would not expect to work. You can see that this sort of thing could be pushed further, and if unrestricted inference were required by the language, the compiler would have to solve arbitrarily complicated constraint problems to determine all the types.

C08546fc4340f0be3109019ef869ac9e
0
lightxbulb 101 Jun 03, 2013 at 07:59

Thanks a lot for this answer! :)
I thought it may be the order in which things go too, but I wasn’t really sure - I didn’t expect either sort<bool>(compare) to work as I knew that sort(compare) didn’t work,
I just found it “strange” that sort<bool>(compare) works and sort(compare) doesn’t. I’m just learning to use templates efficiently so I am “experimenting” with things and I am not quite sure what the compiler can and cannot do, so thanks a lot about the advice I’d have it in mind. Btw you mentioned that some other languages may fare better in this case, can you give some more concrete examples?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 03, 2013 at 16:46

Functional languages often include more powerful type inference, such as ML, OCaml and Haskell.

Fe8a5d0ee91f9db7f5b82b8fd4a4e1e6
0
JarkkoL 102 Jun 08, 2013 at 04:38

I didn’t find the exact reason this from the c++ standard, but my feeling is that either of the function pointer types must be completely specialized for the template argument deduction to work. In your case of myCont.sort(compare); for sort() the function pointer is not completely specialized since the return type is a template type, and compare function isn’t completely specialized since the arguments are a template type, so you have to specialize either one for the deduction to work. In theory it could work like you said, but I believe the c++ standard states that either type must be completely specialized.

B20d81438814b6ba7da7ff8eb502d039
0
Vilem_Otte 117 Jun 08, 2013 at 09:41

Rather than trying to explain myself - I’ll direct you to article describing this: http://accu.org/index.php/journals/409 … where template argument “inference” is described on several samples :)