Multiple dispatch in C++

Question

I am trying to understand what multiple dispatch is. I read a lot of various texts but I still have no idea what multiple dispatch is and what it is good for. Maybe the thing I am missing is piece of code using multiple dispatch. Please, can you write a little piece of code in C++ using multiple dispatch so that I can see it cannot be compiled/runned properly because C++ has only single dispatch? I need to see the difference. Thanks.

Answer 1

Multi-dispatch is the ability to choose which version of a function to call based on the runtime type of the arguments passed to the function call.

Here's an example that won't work right in C++ (untested):

class A { };
class B : public A { };
class C : public A { }


class Foo
{
  virtual void MyFn(A* arg1, A* arg2) { printf("A,A\n"); }
  virtual void MyFn(B* arg1, B* arg2) { printf("B,B\n"); }
  virtual void MyFn(C* arg1, B* arg2) { printf("C,B\n"); }
  virtual void MyFn(B* arg1, C* arg2) { printf("B,C\n"); }
  virtual void MyFn(C* arg1, C* arg2) { printf("C,C\n"); }
};

void CallMyFn(A* arg1, A* arg2)
{
  // ideally, with multi-dispatch, at this point the correct MyFn() 
  // would be called, based on the RUNTIME type of arg1 and arg2
  pFoo->MyFn(arg1, arg2);
}

...

A* arg1 = new B();
A* arg2 = new C();
// Using multi-dispatch this would print "B,C"... but because C++ only
// uses single-dispatch it will print out "A,A"
CallMyFn(arg1, arg2);

Answer 2

Multiple dispatch is when the function that gets executed depends on the run time type of more than one object.

C++ has single dispatch because when you use virtual functions, the actual function that gets run depends only on the run-time type of the object to the left of the -> or . operator.

I'm struggling to think of a real programming case for multiple dispatch. Maybe in a game where various characters fight each other.

void Fight(Opponent& opponent1, Opponent& opponent2);

The winner of a fight may depend on the characteristics of both opponents, so you may want this call to dispatch to one of the following, depending on the run-time types of both arguments:

void Fight(Elephant& elephant, Mouse& mouse)
{
    mouse.Scare(elephant);
}

void Fight(Ninja& ninja, Mouse& mouse)
{
    ninja.KarateChop(mouse);
}

void Fight(Cat& cat, Mouse& mouse)
{
    cat.Catch(mouse);
}

void Fight(Ninja& ninja, Elephant& elephant)
{
    elephant.Trample(ninja);
}

// Etc.

What the function does depends on the types of both arguments, not just one. In C++ you might have to write this as some virtual functions. A virtual function would be selected depending on one argument (the this pointer). Then, the virtual function may need to contain a switch or something to do something particular to the other argument.

Answer 3

In single dispatch the function executed depends on just the object type. In double dispatch the function executed depends on the object type and a parameter.

In the following example, the function Area() is invoked using single dispatch, and Intersect() relies on double dispatch because it takes a Shape parameter.

class Circle;
class Rectangle;
class Shape
{
    virtual double Area() = 0; // Single dispatch

    // ...
    virtual double Intersect(const Shape& s) = 0; // double dispatch, take a Shape argument
    virtual double Intersect(const Circle& s) = 0; 
    virtual double Intersect(const Rectangle& s) = 0; 
};

struct Circle : public Shape
{
    virtual double Area() { return /* pi*r*r */; }

    virtual double Intersect(const Shape& s); 
    { return s.Intersect(*this)  ; }
    virtual double Intersect(const Circle& s); 
    { /*circle-circle*/ }
    virtual double Intersect(const Rectangle& s); 
    { /*circle-rectangle*/ }
};

The example is based on this article.

Answer 4

To put in perspective in 2022 there are quite a few techniques to do multi-dispatch in C++

This one with dynamic casting (already available at the time of this post): https://gist.github.com/jspahrsummers/0834f93cac6d5efa2418ddddf7244b16

And this one with more recent metaprogramming stuff: https://arne-mertz.de/2019/10/multiple-dispatch-over-covariant-functions/

If you compare this to julia or such it is more complex and one way or another it may have some performance overhead (to be clarified how much). This may vary depending on the C++ compiler, at the end of the day the LLVM of julia will also use some form of RTTI.

Not sure if in latest and greatest C++20 you can do better.