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.

Semeiology

C++ doesn't support it directly but I'm sure you can somehow emulate this. I've never used MD or even saw a nice design in other languages that made me wanna have MD in C++. Dylan fanboys list it as one of Dylan's language features. But as far as I can tell it smells like a bad design because the number of functions you might have to write grows exponentially. I wouldn't want to write that many functions. – Muirhead

You have used MD anytime that you have used the Visitor pattern. – Holomorphic

A simple example using C++11: ideone.com/lTsc7M – Confessedly

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);

Pyrrhic

Thanks, this answer is pretty much what I needed to see. Now I just have to find out, why the hell somebody need such a thing.. Anyway, thank you for good example. – Semeiology

one application is physics, a cube colliding with another cube is one intersection, a cube colliding with a plane is a different intersection. Therefore you end up with quite a few different collision detection methods, and dispatching is pretty useful for that. heres a thread on double dispatch, gamedev.net/topic/453624-double-dispatch-in-c – Stu

Another application is in programming languages. Say you want the plus operator ('+') to compute an integer result when both arguments are integers, a float when either argument is a float, and a concatenated string when both arguments are strings. You have a hierarchy of types derived from "expression", so you want the function called when you say add(exp1,exp2) or expr1->add(expr2) to depend on the actual types of both exp1 and exp2. – Augite

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.

Tobolsk

A practical, often happening example is to treat different subclasses differently from an array of base class pointers. – Pilkington

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.

Casebound

Quite a large amount of spaces you got there. – Multiphase

@Multiphase 2 extra spaces :) It would be nice if Stack Overflow could format it to how many spaces the viewer prefers. – Dibri

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.

Towery