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?

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.

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.

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;

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.