Why does double dispatch not work in C++?

Question

#include<iostream.h>
#include<conio.h>

using namespace std;

class SpaceShip {};
class GiantSpaceShip : public SpaceShip {};

class Asteroid {
public:
  virtual void CollideWith(SpaceShip *) {
    cout << "Asteroid hit a SpaceShip" << endl;
  }
  virtual void CollideWith(GiantSpaceShip *) {
    cout << "Asteroid hit a GiantSpaceShip" << endl;
  }
};

class ExplodingAsteroid : public Asteroid {
public:
  virtual void CollideWith(SpaceShip *) {
    cout << "ExplodingAsteroid hit a SpaceShip" << endl;
  }
  virtual void CollideWith(GiantSpaceShip *) {
    cout << "ExplodingAsteroid hit a GiantSpaceShip" << endl;
  }
};



int main()
{
  SpaceShip * s = new GiantSpaceShip();    
  Asteroid * a = new ExplodingAsteroid();
  a->CollideWith(s);  
  getch();  

 return 0;   
}

How can I enable double dispatch in C++?

@Neil How do I modify the function call so that the compiler calls ExplodingAsteroid::CollideWith(GiantSpaceShip *) — Bruce, May 04 '10 at 09:26
See http://stackoverflow.com/questions/429849/double-dispatch-multimethods-in-c, http://stackoverflow.com/questions/1749534/multiple-dispatch-in-c and http://en.wikipedia.org/wiki/Double_dispatch. C++ does not directly support double dispatch. — , May 04 '10 at 09:32
Meyers' "More Effective C++" also has a good section on this. — , May 04 '10 at 09:35
Looks to me like you found the example on wikipedia: http://en.wikipedia.org/wiki/Double_dispatch. Please don't be impatient and follow it to the end, you are missing vital part which is under "Double dispatch in C++" heading. You are simply missing CollideWith methods in SpaceShip and GiantSpaceShip which delegate work to CollideWith methods of their arguments. — Tomek, May 04 '10 at 09:44

score 4 · Accepted Answer · answered May 04 '10 at 09:30

4

This is not single dispatch but double dispatch: you want the method to depend both on the actual/real type of the object it is invoked on, and on the actual/real type of the argument.

This issue can be solved by the Visitor design pattern.

answered May 04 '10 at 09:30

Luc Touraille

79,925
15
92
137

@Luc: You are right. I edited my question after Neil pointed out the mistake – Bruce May 04 '10 at 09:31
2

Although double dispatch can be solved using a technique similar to that used in common implementations of the visitor pattern, I don't think it's correct to say that the visitor pattern itself solves double dispatch. In fact, I'd go the other way and say that double dispatch is a common way of implementing the visitor pattern. – Rob Kennedy May 04 '10 at 12:40
You are right that the main objective of the visitor pattern is not to implement the double dispatch, it is useful for adding functionality to a set of classes used polymorphically, without modifying them (at least not to much). However, it needs double dispatch to work (and hence proposes a clean way to implement it.) – Luc Touraille May 04 '10 at 14:23
An example of how to apply the visitor pattern to do double dispatch would be great – naumcho Jul 13 '11 at 12:30

score 2 · Answer 2 · edited May 04 '10 at 15:16

2

Luc is right on with using the Visitor pattern, I'm just expanding on that by giving an example of how you could do it.

#include <iostream>
#include <conio.h>

using namespace std;

class SpaceObject;
class SpaceShip;
class GiantSpaceShip;
class Asteroid;
class ExplodingAsteroid;

class SpaceObject {
public:
  virtual void CollideWith(SpaceObject*)       {}
  virtual void CollideWith(SpaceShip*)         {}
  virtual void CollideWith(GiantSpaceShip*)    {}
  virtual void CollideWith(Asteroid*)          {}
  virtual void CollideWith(ExplodingAsteroid*) {}
};



class Asteroid : public SpaceObject {
public:
  virtual void CollideWith(SpaceObject* o)       { o->CollideWith(this); }
  virtual void CollideWith(SpaceShip *)          { cout << "Asteroid hit a SpaceShip" << endl; }
  virtual void CollideWith(GiantSpaceShip *)     { cout << "Asteroid hit a GiantSpaceShip" << endl; }
};

class ExplodingAsteroid : public Asteroid {
public:
  virtual void CollideWith(SpaceObject* o)       { o->CollideWith(this); }
  virtual void CollideWith(SpaceShip *)          { cout << "ExplodingAsteroid hit a SpaceShip" << endl; }
  virtual void CollideWith(GiantSpaceShip *)     { cout << "ExplodingAsteroid hit a GiantSpaceShip" << endl; }
};

class SpaceShip : public SpaceObject {
public:
  virtual void CollideWith(SpaceObject* o)       { o->CollideWith(this); }
  virtual void CollideWith(Asteroid* o)          { o->Asteroid::CollideWith(this); }
  virtual void CollideWith(ExplodingAsteroid* o) { o->ExplodingAsteroid::CollideWith(this); }
};

class GiantSpaceShip : public SpaceShip {
public:
  virtual void CollideWith(SpaceObject* o)       { o->CollideWith(this); }
  virtual void CollideWith(Asteroid* o)          { o->Asteroid::CollideWith(this); }
  virtual void CollideWith(ExplodingAsteroid* o) { o->ExplodingAsteroid::CollideWith(this); }
};

int main()
{
  SpaceObject* s = new GiantSpaceShip();
  SpaceObject* a = new ExplodingAsteroid();
  a->CollideWith(s);
  getch();

 return 0;
}

edited May 04 '10 at 15:16

deft_code

57,255
29
141
224

answered May 04 '10 at 10:29

pdehaan

332
2
13

1

Can you explain why your example usage includes three dispatches instead of just two? (It's not called *triple dispatch*, after all.) – Rob Kennedy May 04 '10 at 12:44
Looks like pdehaan found a weakness of double dispatch. Where do you put the implementation? Since both objects are involved either class seems a valid location. Personally, I put the implementation in the heavier class even it creates 3 calls (2 for double dispatch and a 3rd to forward the invocation to the preferred class). My 3rd call is not virtual, but a direct call to minimize the overhead. If both classes are equally weighty I have left the implementations as free friend functions, though I've never needed to do this in production code. – deft_code May 04 '10 at 15:11
@Rob: Are you referring to the main call resulting in three calls before resolving, or the fact that I define CollideWith 3 times per sub-class? Passing 'this' as an argument passes as the type 'this' is when the function is defined. If I don't define the method inside each class, it reverts to the parent version, which only passes itself as the parent type. With each class having methods for both the base type and specific types they care about, I can make any two classes interact without knowing exactly which class they are. There's probably better ways for specific cases, but this works. – pdehaan May 04 '10 at 15:14
@pdehaan, I edited your answer to remove the extra dynamic calls. – deft_code May 04 '10 at 15:15
I'm referring to the former — *three* calls to `CollideWith` occur before there's any real work. Ideally, the work would occur in the second call. Caspin's edit reduced the effect a little, but there are still three `CollideWith` calls before anything really happens. The reason for this oddity is threefold: the asteroids and the space ships all descend from the same class, that class is allowed to collide with itself, and either object can initiate the collision. If you'd called `s->CollideWith(a)`, then there'd be just two dispatches because the asteroid classes do the work. – Rob Kennedy May 04 '10 at 16:15
If you can guarantee one of the objects is going to be of a particular class every time, optimize for that situation. I just went with the assumption that asteroids and ships might all be stored together and expected to possibly interact as well. Alternately, you could duplicate the meaningful code in all relevant classes. This would ensure only two calls either way, but add more code. – pdehaan May 04 '10 at 17:38

Why does double dispatch not work in C++?

2 Answers2