Vishal Chovatiya

Posted on Apr 20, 2020 • Originally published at vishalchovatiya.com

Double Dispatch in C++: Recover Original Type of the Object Pointed by Base Class Pointer

#cpp #tutorial #computerscience #programming

Double Dispatch in C++ is a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects involved in the call. In more simple words, its function calling using two different virtual tables of respective two objects. I know this sounds cryptic, but don't worry I will come to double dispatch solution after trying most of the naive solution so that you will come away with the full understanding of concept without having needless confusions.

/!\: Originally published @ www.vishalchovatiya.com.

Motivation

At first, a pointer to a base class made sense; you didn't need to know the actual derived class. So you decided to expose a single collection of base class pointers to your clients like so:

struct Animal {
    virtual const char *name() = 0;
};

using AnimalList = vector<Animal*>

As you added your first few classes, your assumptions were validated; you never needed to know the actual type.

struct Cat : Animal {
    const char *name() { return "Cat"; }
};

struct Dog : Animal {
    const char *name() { return "Dog"; }
};

But the requirements change.
One day the client came to you and said "I'm trying to model a person that is afraid of dogs, so they run away when they see one. But they love cats, so they try to pet them when they see them."
Dammit. Now your assumptions are wrong. You do need to know the type. And you're under pressure to meet a deadline.

Run-Time Type Identification

Then you thought "Well there's only two types of animals, this isn't so bad". So you wrote code like this:

struct Person {
    void ReactTo(Animal *_animal) {
        if (dynamic_cast<Dog *>(_animal))
            RunAwayFrom(_animal);
        else if (dynamic_cast<Cat *>(_animal))
            TryToPet(_animal);
    }

    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }

    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};

Then the client said that if the Animal was a Horse, they wanted to try to ride it.

void Person::ReactTo(Animal *_animal) {
    if (dynamic_cast<Dog *>(_animal))
        RunAwayFrom(_animal);
    else if (dynamic_cast<Cat *>(_animal))
        TryToPet(_animal);
    else if (dynamic_cast<Horse *>(_animal))
        TryToRide(_animal);
}

You see this is going crazy. At some point in future, you might not like working with your own code. We've all been there. Nonetheless, the trend continued for some time until you may found yourself with a mess like this:

void Person::ReactTo(Animal *_animal) {
    if (dynamic_cast<Dog *>(_animal) || dynamic_cast<Gerbil *>(_animal)){
        if (dynamic_cast<Dog *>(_animal) && dynamic_cast<Dog>()->GetBreed() == DogBreed.Daschund) // Daschund's are the exception
            TryToPet(_animal);
        else
            RunAwayFrom(_animal);    
    }
    else if (dynamic_cast<Cat *>(_animal) || dynamic_cast<Pig *>(_animal))
        TryToPet(_animal);
    else if (dynamic_cast<Horse *>(_animal))
        TryToRide(_animal);
    else if (dynamic_cast<Lizard *>(_animal))
        TryToFeed(_animal);
    else if (dynamic_cast<Mole *>(_animal))
        Attack(_animal)
    // etc.
}

This list is getting pretty long, you thought to yourself one day. All these dynamic_cast seem wrong, and they're kind of slow as well. So on a side note of refactorization, you come up with a solution which identifies typeid(), this is a bit faster than dynamic_cast but still, it's not optimum performance.

Exploiting Polymorphism

As someone from your senior/mentor suggests you to use an enum with polymorphic methods to identify type & you wrote following code:

enum class AnimalType { Dog, Cat };
struct Animal {
    virtual const char *name() = 0;
    virtual AnimalType type() = 0;
};

struct Cat : Animal {
    const char *name() { return "Cat"; }
    AnimalType type() { return AnimalType::Cat; }
};

struct Dog : Animal {
    const char *name() { return "Dog"; }
    AnimalType type() { return AnimalType::Dog; }
};

struct Person {
    void ReactTo(Animal *_animal) {
        if (_animal->type() == AnimalType::Cat)
            TryToPet(_animal);
        else if (_animal->type() == AnimalType::Dog)
            RunAwayFrom(_animal);
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};

int main() {
    Person p;
    Animal *animal_0 = new Dog;
    p.ReactTo(animal_0);
    Animal *animal_1 = new Cat;
    p.ReactTo(animal_1);
    return 0;
}

You may get the performance improvement, but still, you will be left with a long list of if/else-if.

More Functional & Modular Approach

using PersonMethodPtr = void (Person::*)(Animal *);
using ReactionHash = unordered_map<AnimalType, PersonMethodPtr>;

void Person::ReactTo(Animal *_animal){
    static const ReactionHash reactionFunctions{
        {AnimalType::Cat, &TryToPet},
        {AnimalType::Dog, &RunAwayFrom},
        // etc.
    };
    reactionFunctions[_animal->type()](_animal);
}

But here you are indirectly writing your own virtual table(a very bad virtual table) which may not provide any performance gain at all, thanks to the overhead of hashing & lookup. Moreover, you are paying a little extra in memory to store your lookup table.

Single-Dispatch

So rather than keeping any identifier for each type or RTTI, we can use a middle man to route function call to appropriate behaviour.

struct Animal {
    virtual string name() = 0;
    virtual void Visit(class ReactVisitor *visitor) = 0;
};

struct ReactVisitor {
    class Person *person = nullptr;
};

struct Person {
    void ReactTo(Animal *_animal) {
        ReactVisitor visitor{this};        
        _animal->Visit(&visitor);
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};

struct Cat : public Animal {
    string name() { return "Cat"; }
    void Visit(ReactVisitor *visitor) { visitor->person->TryToPet(this); }
};

struct Dog : public Animal {
    string name() { return "Dog"; }
    void Visit(ReactVisitor *visitor) { visitor->person->RunAwayFrom(this); }
};

int main() {
    Person p;
    vector<Animal*> animals = {new Dog, new Cat};

    for(auto&& animal : animals)
        p.ReactTo(animal);    

    return 0;
}

To keep the middle man to a route function call, we have to add visit(ReactVisitor *) method which accepts middle man i.e. ReactVisitor as a parameter. Then we add appropriate behaviour to each type of Animal i.e. Dog & Cat.

Problems With the Single Dispatch Approach

Why should the Dog class dictate how a Person reacts to it? We have leaked implementation details of the Person class and therefore have violated encapsulation.
What if the Person class has other behaviours they want to implement? Are we really going to add a new virtual method on the base class for each of them?

The solution to the above problem will lead us to use Double-Dispatch Mechanism.

Double Dispatch in C++

We can overcome the shortcoming of Single-Dispatch by adding one more layer of indirection(i.e. AnimalVisitor).

/* -------------------------------- Added Visitor Classes ------------------------------- */
struct AnimalVisitor {
    virtual void Visit(struct Cat *) = 0;
    virtual void Visit(struct Dog *) = 0;
};

struct ReactVisitor : AnimalVisitor {
    ReactVisitor(struct Person *p) : person{p} {}
    void Visit(struct Cat *c);
    void Visit(struct Dog *d);
    struct Person *person = nullptr;
};
/* --------------------------------------------------------------------------------------- */


struct Animal {
    virtual string name() = 0;
    virtual void Visit(struct AnimalVisitor *visitor) = 0;      
};

struct Cat : Animal {
    string name() { return "Cat"; }
    void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
};

struct Dog : Animal {
    string name() { return "Dog"; }
    void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
};

struct Person {
    void ReactTo(Animal *_animal) {
        ReactVisitor visitor{this};        
        _animal->Visit(&visitor);   // 1st dispatch <<---------
    }
    void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
    void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
};


/* -------------------------------- Added Visitor Methods ------------------------------- */
void ReactVisitor::Visit(Cat *c) { // Finally comes here <<-------------
    person->TryToPet(c);
}
void ReactVisitor::Visit(Dog *d) { // Finally comes here <<-------------
    person->RunAwayFrom(d);
}
/* --------------------------------------------------------------------------------------- */


int main() {
    Person p;
    for(auto&& animal : vector<Animal*>{new Dog, new Cat})
        p.ReactTo(animal);
    return 0;
}

As you can see above, rather depending directly on ReactVisitor, we have taken AnimalVisitor as one more layer of indirection. And visit(AnimalVisitor *) method in Cat & Dog class accept AnimalVisitor as a parameter.
This gives us two benefits, i). we do not have to write person's behaviour in Cat & Dog class, so we are not breaking the rule of encapsulation, and ii). we are clubbing the reaction of Person in a separate class(i.e. ReactVisitor), so we are encouraging the Single Responsibility Principle.

How does Double Dispatch Mechanism work?

I know so things are getting complex, but it is reasonably complex I would say. Function stack frame & single image of function calling chain with code snippet will simplify it a lot.

From Person::ReactTo, we call Animal::visit, which will dispatch to the appropriate overridden visit i.e. either Cat::visit or Dog::visit.
From the overridden Cat::visit(AnimalVisitor*), we call AnimalVisitor::visit, which will again dispatch to the appropriate overridden i.e. either ReactionVisitor::visit(Cat*) or ReactionVisitor::visit(Dog*).

Alternate Approach to Double Dispatch in Modern C++ using std::variant & std::visit

struct Animal {
    virtual string name() = 0;
};

struct Cat : Animal {
    string name() { return "Cat"; }
};

struct Dog : Animal {
    string name() { return "Dog"; }
};

struct Person {
    void RunAwayFrom(Animal *animal) { cout << "Run Away From " << animal->name() << endl; }
    void TryToPet(Animal *animal) { cout << "Try To Pet " << animal->name() << endl; }
};

struct ReactVisitor {
    void operator()(Cat *c) { person->TryToPet(c); }
    void operator()(Dog *d){ person->RunAwayFrom(d); }
    Person *person = nullptr;
};

using animal_ptr = std::variant<Cat*, Dog*>;

int main() {
    Person p;
    ReactVisitor rv{&p};
    for(auto&& animal : vector<animal_ptr>({new Dog, new Cat}))
        std::visit(rv, animal);
    return 0;
}

So for those of you who are not familiar with the std::variant, you can consider it as a union. And line std::variant<Cat*, Dog*>, suggest that you can use/assign/access either Cat* or Dog* at a time.
And Modern C++ provide us std::visit which accept callable i.e. ReactVisitor in our case having overloaded function operator for each type and std::variant. You also make use of lambda functions rather using functor i.e. ReactVisitor.

Benefits of Double Dispatch Mechanism

Adhering Single Responsibility Principle meaning separating type-specific logic in the separate entity/class. In our case, ReactVisitor only handles the reaction for different Animal types.
Adhering Open-Closed Principle meaning new functionality can be added without touching any class headers once we inserted visit() method for hierarchy, For example, if you want to add sound() method for each different Animal, you can create SoundVisitor & rest of the edit goes as same ReactVisitor.
This will be much useful when you already have done the unit-testing for your entire hierarchy, and now you do not want to touch that & wants to add new functionality.
Performance over dynamic_cast, typeid() and check for enum/string comparison.

Usecase of Double Dispatch Mechanism

Sorting a mixed set of objects: You can implement filtering with double-dispatch. E.g., "Give me all theCats from a vector<Animal*>".
You can add additional functionality to the whole inheritance hierarchy without modifying it over & over E.g. if you want to add sound() method for each different Animal, you can create SoundVisitor & rest of the edit goes as same ReactVisitor.
Event handling systems that use both the event type and the type of the receptor object in order to call the correct event handling routine.
Adaptive collision algorithms usually require that collisions between different objects be handled in different ways. A typical example is in a game environment where the collision between a spaceship and an asteroid is computed differently from the collision between a spaceship and a space station.

Conclusion

Each solution has its advantages and issues, and choosing one depends on the exact needs of your project. C++ presents unique challenges in designing such high-level abstractions because it's comparatively rigid and statically typed. Abstractions in C++ also tend to strive to be as cheap as possible in terms of runtime performance and memory consumption, which adds another dimension of complexity to the problem.

Reference

This article becomes by-product while I was writing about classic Visitor Design Pattern because without double dispatch mechanism in C++ classic visitor doesn't exist. Most of the credit for this article & images goes to Andy G. The code snippets you see in this article is simplified not sophisticated.

Have Any Suggestions, Query or Wants to Say Hi? Take the Pressure Off, You Are Just a Click Away.🖱️

DEV Community