Double dispatch and template class

Question

I have a C++ code where I compare different class deriving from a common mother class, Foo. If the two class have not the same type, the comparison is always false. Otherwise, it compares some internal data specific to the class.

My code looks like this:

class Bar;
class Baz;

class Foo
{
public:
    virtual bool isSame( Foo* ) = 0;
    virtual bool isSameSpecific( Bar* ){ return false; }
    virtual bool isSameSpecific( Baz* ){ return false; }
};

class Bar : public Foo
{
public:
    bool isSame( Foo* foo){ return foo->isSameSpecific(this); }
    bool isSameSpecific( Bar* bar){ return bar->identifier == identifier; }

    int identifier;
};

// and the same for Baz...

This works great (I think that's a double dispatch), I can compare Bar and Baz with only pointers to Foo.

But now comes the problem. I have to add a template class:

template< typename T>
class Qux : public Foo
{
//...
};

The problem is that in Foo, I cannot declare the method isSameSpecific for Qux*, because it would be virtual and template.

Question: is there any neat way to overcome this problem?

Flowerdeluce

Only make Foo class template also, or write different overloads of isSameSpecific for all needed Qux<T>. – Tinsel

@Tinsel Thank you for your comment! The template argument does not make sense on Foo and futur classes might have other template arguments, so I don't want to end up with all the possible template arguments on Foo. For the different overloads, this could be an acceptable solution, but there can be many possibilites for T, so many overloads to write (not very neat). – Flowerdeluce

Have a look at Andrei Alexandrescu's Loki Library, in particular the Visitor pattern. – Lepine

@PeterWood Interesting, I'll have a look at it! – Flowerdeluce

Answer 1

There's not really a solution for this problem: you need a isSameSpecific function for each instantiation of the template you use. (In other words, in Foo:

template <typename T>
virtual bool isSameSpecific( Qux<T>* );

is illegal, but:

virtual bool isSameSpecific( Qux<int>* );
virtual bool isSameSpecific( Qux<double>* );
//  etc.

isn't.)

You might be able to get away with creating an abstract QuxBase, and having Qux<T> derive from it. Most likely, that will just move the problem to QuxBase, but if isSameSpecific doesn't depend on the type of T, for example because you can define some canonical encompassing type, it may be doable. Without knowing more about Qux and isSameSpecific, it's difficult to say. (If Qux<T>::isSameSpecific should always return false if the instantiation types are different, for example, you could type check in QuxBase::isSameSpecific, and forward to another virtual function if the types are identical.)

Note that similar issues affect all of the alternative ways of implementing multiple dispatch as well. In the end, you're asking for dispatch over an open set of types, which means a potentially infinit number of different functions.

EDIT:

Just to be clear: I am assuming that your isSame is simply an example, and that the actual operations may be more complex. The actual code you show clearly falls into what I suggest in the second paragraph; in fact, it can be implemented even without multiple dispatch. Just define a canonical "identifier" type, define a virtual getCanonicalIdentifier function, and use that in isSame:

bool Foo::isSame( Foo const* other ) const
{
    return getCanonicalIdentifier() 
        == other->getCanonicalIdentifier(); 
}

For that matter, if different types implies that isSame returns false (often the case, if isSame means what it looks like), all you don't need double dispatch either:

bool Foo::isSame( Foo const* other ) const
{
    return typeid( *this ) == typeid( *other )
        && isSameSpecific( other );
}

The derived isSameSpecific will have to convert the type of the pointer, but since they are guaranteed that it is the same as the type of this, that's a simple and safe operation.

Finally: if the classes don't have value semantics (and the almost certainly shouldn't if polymorphism is involved), something as simple as:

bool Foo::isSame( Foo const* other ) const
{
    return this == other;
}

may suffice.

All of this applies only to something like isSame, however. If you have other functions as which are affected, you're back to what I initially said.

Shanta

Thanks for the very interesting answer! You're right when you say that the implementation is quite more complex, but that's the heart of my problem. I think actually that your idea with the QuxBase solves my problem! Actually, the type T is usually a class (on which I have full control) with data in it. So, I can make all the potential T derive from one class and have a method (double dispatch again) to compare them. Then, in QuxBase, I can compare both the data specific from Qux and compare the type T throught the comparison method. – Flowerdeluce

Answer 2

The compiler must know the (finite) set of isSameSpecific virtuals at the time it parses the class Foo definition. The virtuals all have reserved entries in the vtable. The template Qux could be overridden an unlimited number of times, requiring an unlimited number of virtuals in Foo. Clearly that can't work, even without trying to describe a method of defining them all.

You can probably use typeinfo to do what you want, but it would not be with type polymorphism.

Moriah

Thank you for the answer! That's what I thought and that's the problem with every "template virtual" method. Typeinfo is my default solution but it do not consider it as neat. So, maybe the solution is indeed to change my definition of neat. – Flowerdeluce

Answer 3

You are right that this is double-dispatch, and you are right that unfortunately a method cannot be both virtual and template (the latter being an implementation issue).

I am afraid that there is no possibility to do so with a pure design; however you can cheat in Qux.

template <typename T>
class Qux: public Foo {
    virtual bool isSame( Foo* foo ) {
        if (Qux* q = dynamic_cast<Qux*>(foo)) {
            return *this == *q;
        }
        return false;
    }
}; // class Qux

Of course, dynamic_cast is cheating a bit (as are all casts toward children), but hey it works!

Nota Bene: the isSame methods should be probably be const and take const arguments, aka virtual bool isSame(Foo const* foo) const;

Kattegat

Thanks for the answer! Your solution is probably the one I'll implement (actually, I'll probably do that in all the isSame method and get rid of the isSameSpecific), unless some comes with a better idea. And yes, the cast is not in my neat defintition :-). For your NB: in my implementation, it's actually const, since it was not essential for the understanding of the problem, I got rid of it. Thank for the suggestion anyway! – Flowerdeluce

Not cheating one little bit. The cast here is not essential to the design, it is just to overcome a language limitation. – Qumran

If this is a sufficient solution, you can do the type check in the base class, and only forward to isSameSpecific if the two types are identical. And if isSame should always return false if they aren't, then doing the check in the base class is probably a better solution (even if it involves RTTI), since you enforce the post-condition in the base class. – Shanta

@JamesKanze: it would be slightly different though, as it is the solution I presented allows comparing Qux<int> against class K: public Qux<int> {}; (for better or worse). What would be the signature of isSameSpecific though in your case ? Foo* too ? – Kattegat

@MatthieuM. The signature would have to be with Foo*, since for overriding to work, the signatures all have to be the same. So each derived class would have to convert the argument to its type. Because this is a precondition of the function, however, it could use static_cast. (And of course, the virtual function should be private, to ensure that it is never called except from isSame in the base class.) – Shanta

Answer 4

How about using RTTI:

#include <typeinfo>

struct Foo
{
    virtual ~Foo() { }
    virtual bool compare_with_same(Foo const & rhs) = 0;
};

struct Bar : Foo
{
    int thing;

    virtual bool compare_with_same(Foo const & rhs)
    {
        assert(dynamic_cast<Bar const *>(&rhs) != nullptr);

        return static_cast<Bar const &>(rhs).thing == thing;
    }
}

bool operator==(Foo const & lhs Foo const & rhs)
{
    return typeid(lhs) == typeid(rhs) && lhs.compare_with_same(rhs);
}

Alternatively you can put the typeid code into each compare_with_same override. That might be a bit safer.

Outport

Thanks for your answer! RTTI does not meet my definition of neat, but I think that I'll have no choice... It's maybe more my definition of neat that is wrong :-) – Flowerdeluce

@Flowerdeluce It may be your definition of neat. If there is a post-condition typeid(lhs) != typeid(rhs) implies false, then this should be enforced in the base class; the proposed solution here, with typeid is actually cleaner than depending on every derived class doing this correctly (i.e. only overriding the isSameSpecific for its own class). – Shanta

@Flowerdeluce Note too that if you have an invariant that all instances have different identifiers, then bool Foo::isSame( Foo const* other ) const { return this == other; } is by far the simplest solution. – Shanta

@JamesKanze There's not identifier, unfortunately. For the comparison in the mother class, you're right! – Flowerdeluce