Understanding double dispatch C++

Question

I try to understand how double dispatch works. I created an example where a monster and a warrior derived from the abstract class Creature could fight. The class Creature has method "fight", which is defined in derived classes, and in each derived class is defined what happens if warrior fights with warrior or with monster etc. I wrote the following code:

#include<iostream>
using namespace std;

class Monster;
class Warrior;

class Creature{
public:
    virtual void fight(Creature&) =0;
};

class Monster: public Creature{
    void fightwho(Warrior& w) {cout<<"Monster versus Warrior"<<endl; }
    void fightwho(Monster& m) {cout<<"Monster versus Monster"<<endl; }
public:
    void fight(Creature& c)  {c.fightwho(*this);}
};

class Warrior: public Creature{
    void fightwho(Warrior& w) {cout<<"Warrior versus Warrior"<<endl; }
    void fightwho(Monster& m) {cout<<"Monster versus Warrior"<<endl; }
public:
    void fight(Creature& c) {c.fightwho(*this);}
};

int main()
{
Warrior w;
Monster m;
w.fight(m);
}

This results in compiler error, which I foresee:

ex12_10.cpp: In member function ‘virtual void Monster::fight(Creature&)’: ex12_10.cpp:17:30: error: ‘class Creature’ has no member named ‘fightwho’

ex12_10.cpp: In member function ‘virtual void Warrior::fight(Creature&)’: ex12_10.cpp:24:29: error: ‘class Creature’ has no member named ‘fightwho’

But I don't know how to proceed from here... Please help.

Answer 1

Well, obviously, you really don't have fightwho declared in your Creature class, so you need to declare it there, and declare it as virtual.

Double dispatch works in a way that for call (this assumes Warrior& w = ..., not Warrior w):

w.fight(m);

First the virtual mechanism will chose Warrior::fight instead of Monster::fight and then the overloading mechanism will pick Monster::fightwho(Warrior& m) instead of Warrior::fightwho(Warrior& m). Note that it would make more sense if you would have:

Warrior w;
Monster m;
Creature& c1 = w;
Creature& c2 = m;
c1.fight(c2); // not w.fight(m)

Therefore, the method which will eventually be called will be dispatched according to type of the object on which you call it and type of the object sent as argument, i.e. double dispatch

Additionally, please note that this might not be the best example as your types are members of the same hierarchy. Visitor design pattern is a good example of double dispatch implementations in languages which don't support it as first class citizens (i.e. C++ and derivatives: Java, C#...)

As @CrazyCasta correctly notes, when your class hierarchy starts to grow, this approach becomes much harder to maintain and can result in explosion of number of methods, so choose carefully...

Answer 2

My contribution to above answers is providing well-tested example in order to clarify double dispatch concept in reality. If you review the below code you will find the answer of how can I implement by myself.

#include <iostream>

using namespace std;

class A;
class A1;
class A2;
class B1;
class B2;

class B {
    public:
        // dispatcher function to A
        virtual void collide(const A& a) const = 0;

        // actual collision logic B with types of A
        virtual void collide(const A1& a) const = 0;
        virtual void collide(const A2& a) const = 0;
};

class A {
    public:
        // dispatcher function to B
        virtual void collide(const B& b) const = 0;

        // actual collision logic A with types of B
        virtual void collide(const B1& b) const = 0;
        virtual void collide(const B2& b) const = 0;
};

class A1 : public A {
    public:
        void collide(const B& b) const {
            // dispatch to b
            b.collide(*this);
        }
        void collide(const B1& b) const {
            cout << "collision with B1 and A1" << endl;
        }
        void collide(const B2& b) const {
            cout << "collision with B2 and A1" << endl;
        }
};

class A2 : public A {
    public:
        void collide(const B& b) const {
            // dispatch to a
            b.collide(*this);
        }
        void collide(const B1& b) const {
            cout << "collision with B1 and A2" << endl;
        }
        void collide(const B2& b) const {
            cout << "collision with B2 and A2" << endl;
        }
};

class B1 : public B {
    public:
        void collide(const A& b) const {
            b.collide(*this);
        }
        void collide(const A1& b) const {
            cout << "collision with A1 Bnd B1" << endl;
        }
        void collide(const A2& b) const {
            cout << "collision with A2 Bnd B1" << endl;
        }
};

class B2 : public B {
    public:
        void collide(const A& a) const {
            a.collide(*this);
        }
        void collide(const A1& a) const {
            cout << "collision with A1 Bnd B2" << endl;
        }
        void collide(const A2& a) const {
            cout << "collision with A2 Bnd B2" << endl;
        }
};

int main() {

    A* a = new A1();
    B* b = new B2();

    // first dispatch is done by polymorphism ( a is resolved as a A1 )
    // second dispatch is done in collide function by the function overloading
    // ( in collide function we are sending A1 to collide function of B )
    a->collide(*b);

}

Answer 3

Consider using a templated function to determine the type of the second object (RTTI) so that most code duplicating can be avoided, like this:

#include <iostream>
#include <vector>
    
struct Unit // abstract Unit superclass 
{
    virtual void interact(Unit *u2)=0;
};

template<typename U1,typename U2>
void interact(U1 u1,U2 u2);       

struct UnitA : public Unit
{
    void interact(Unit *u2) { ::interact(this, u2); }
};
        
struct UnitB : public Unit
{
    void interact(Unit *u2) { ::interact(this, u2); }
};

int main()
{
    std::vector<Unit*> units={new UnitA(), new UnitB(), new UnitA(), new UnitB()}; // all the units
    
    // make each pair of units interact with eachother once
    for (int i1=0; i1<units.size(); i1++)
        for (int i2=i1+1; i2<units.size(); i2++) 
            units[i1]->interact( units[i2] ); 
}

template<typename U1,typename U2>
void interact(U1 u1,U2 u2) // takes care of the RTTI work
{
         if (auto dc=dynamic_cast<UnitA*>(u2)) interact(*u1, *dc); 
    else if (auto dc=dynamic_cast<UnitB*>(u2)) interact(*u1, *dc);
    else { std::cerr<< "Unkown subclass\n"; exit(1); }
}
 
// now we can handle the interaction for each subclass permutation:
void interact(UnitA& u1,UnitA& u2) { std::cout<<"UnitA-UnitA\n"; }
void interact(UnitA& u1,UnitB& u2) { std::cout<<"UnitA-UnitB\n"; }
void interact(UnitB& u1,UnitA& u2) { std::cout<<"UnitB-UnitA\n"; }   
void interact(UnitB& u1,UnitB& u2) { std::cout<<"UnitB-UnitB\n"; }

The output is a print for the interaction between each pair of units in the vector:

UnitA-UnitB
UnitA-UnitA
UnitA-UnitB
UnitB-UnitA
UnitB-UnitB
UnitA-UnitB

However, this approach is slow because of run-time type checks and because a vector of pointers results in poor caching. For high-performance games consider a more "data oriented design".