Double Dispatch in C++
Double Dispatch in C++ is a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects. Learn more!
By
·
·
Analysis
Likes
(2)
Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!
Comment
Save
19.4K Views
Join the DZone community and get the full member experience.
Join For FreeDouble 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.
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:
C++
x
1
struct Animal {
2
virtual const char *name() = 0;
3
};
4
5
using AnimalList = vector<Animal*>;
- As you added your first few classes, your assumptions were validated; you never needed to know the actual type.
C++
xxxxxxxxxx
1
1
struct Cat : Animal {
2
const char *name() { return "Cat"; }
3
};
4
5
struct Dog : Animal {
6
const char *name() { return "Dog"; }
7
};
- 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:
C++
xxxxxxxxxx
1
13
1
struct Person {
2
void ReactTo(Animal *_animal) {
3
if (dynamic_cast<Dog *>(_animal))
4
RunAwayFrom(_animal);
5
else if (dynamic_cast<Cat *>(_animal))
6
TryToPet(_animal);
7
}
8
9
void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
10
11
void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
12
};
13
- Then the client said that if the
Animalwas aHorse, they wanted to try to ride it.
C++
xxxxxxxxxx
1
1
void Person::ReactTo(Animal *_animal) {
2
if (dynamic_cast<Dog *>(_animal))
3
RunAwayFrom(_animal);
4
else if (dynamic_cast<Cat *>(_animal))
5
TryToPet(_animal);
6
else if (dynamic_cast<Horse *>(_animal))
7
TryToRide(_animal);
8
}
- 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:
C++
xxxxxxxxxx
1
17
1
void Person::ReactTo(Animal *_animal) {
2
if (dynamic_cast<Dog *>(_animal) || dynamic_cast<Gerbil *>(_animal)){
3
if (dynamic_cast<Dog *>(_animal) and& dynamic_cast<Dog>()->GetBreed() == DogBreed.Daschund) // Daschund's are the exception
4
TryToPet(_animal);
5
else
6
RunAwayFrom(_animal);
7
}
8
else if (dynamic_cast<Cat *>(_animal) || dynamic_cast<Pig *>(_animal))
9
TryToPet(_animal);
10
else if (dynamic_cast<Horse *>(_animal))
11
TryToRide(_animal);
12
else if (dynamic_cast<Lizard *>(_animal))
13
TryToFeed(_animal);
14
else if (dynamic_cast<Mole *>(_animal))
15
Attack(_animal)
16
// etc.
17
}
- 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 and you wrote following code:
C++
xxxxxxxxxx
1
35
1
enum class AnimalType { Dog, Cat };
2
struct Animal {
3
virtual const char *name() = 0;
4
virtual AnimalType type() = 0;
5
};
6
7
struct Cat : Animal {
8
const char *name() { return "Cat"; }
9
AnimalType type() { return AnimalType::Cat; }
10
};
11
12
struct Dog : Animal {
13
const char *name() { return "Dog"; }
14
AnimalType type() { return AnimalType::Dog; }
15
};
16
17
struct Person {
18
void ReactTo(Animal *_animal) {
19
if (_animal->type() == AnimalType::Cat)
20
TryToPet(_animal);
21
else if (_animal->type() == AnimalType::Dog)
22
RunAwayFrom(_animal);
23
}
24
void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
25
void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
26
};
27
28
int main() {
29
Person p;
30
Animal *animal_0 = new Dog;
31
p.ReactTo(animal_0);
32
Animal *animal_1 = new Cat;
33
p.ReactTo(animal_1);
34
return 0;
35
}
- You may get the performance improvement, but still, you will be left with a long list of
if/else-if.
More Functional and Modular Approach
C++
xxxxxxxxxx
1
11
1
using PersonMethodPtr = void (Person::*)(Animal *);
2
using ReactionHash = unordered_map<AnimalType, PersonMethodPtr>;
3
4
void Person::ReactTo(Animal *_animal){
5
static const ReactionHash reactionFunctions{
6
{AnimalType::Cat, &TryToPet},
7
{AnimalType::Dog, &RunAwayFrom},
8
// etc.
9
};
10
reactionFunctions[_animal->type()](_animal);
11
}
- 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 and 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.
C++
xxxxxxxxxx
1
37
1
struct Animal {
2
virtual string name() = 0;
3
virtual void Visit(class ReactVisitor *visitor) = 0;
4
};
5
6
struct ReactVisitor {
7
class Person *person = nullptr;
8
};
9
10
struct Person {
11
void ReactTo(Animal *_animal) {
12
ReactVisitor visitor{this};
13
_animal->Visit(&visitor);
14
}
15
void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
16
void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
17
};
18
19
struct Cat : public Animal {
20
string name() { return "Cat"; }
21
void Visit(ReactVisitor *visitor) { visitor->person->TryToPet(this); }
22
};
23
24
struct Dog : public Animal {
25
string name() { return "Dog"; }
26
void Visit(ReactVisitor *visitor) { visitor->person->RunAwayFrom(this); }
27
};
28
29
int main() {
30
Person p;
31
vector<Animal*> animals = {new Dog, new Cat};
32
33
for(auto&& animal : animals)
34
p.ReactTo(animal);
35
36
return 0;
37
}
- To keep the middle man to a route function call, we have to add
visit(ReactVisitor *)method which accepts middle man i.e.ReactVisitoras a parameter. Then we add appropriate behaviour to each type ofAnimali.e.DogandCat.
Problems With the Single Dispatch Approach
- Why should the
Dogclass dictate how aPersonreacts to it? We have leaked implementation details of thePersonclass and therefore have violated encapsulation. - What if the
Personclass 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).
C++
xxxxxxxxxx
1
56
1
/* -------------------------------- Added Visitor Classes ------------------------------- */
2
struct AnimalVisitor {
3
virtual void Visit(struct Cat *) = 0;
4
virtual void Visit(struct Dog *) = 0;
5
};
6
7
struct ReactVisitor : AnimalVisitor {
8
ReactVisitor(struct Person *p) : person{p} {}
9
void Visit(struct Cat *c);
10
void Visit(struct Dog *d);
11
struct Person *person = nullptr;
12
};
13
/* --------------------------------------------------------------------------------------- */
14
15
16
struct Animal {
17
virtual string name() = 0;
18
virtual void Visit(struct AnimalVisitor *visitor) = 0;
19
};
20
21
struct Cat : Animal {
22
string name() { return "Cat"; }
23
void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
24
};
25
26
struct Dog : Animal {
27
string name() { return "Dog"; }
28
void Visit(AnimalVisitor *visitor) { visitor->Visit(this); } // 2nd dispatch <<---------
29
};
30
31
struct Person {
32
void ReactTo(Animal *_animal) {
33
ReactVisitor visitor{this};
34
_animal->Visit(&visitor); // 1st dispatch <<---------
35
}
36
void RunAwayFrom(Animal *_animal) { cout << "Run Away From " << _animal->name() << endl; }
37
void TryToPet(Animal *_animal) { cout << "Try To Pet " << _animal->name() << endl; }
38
};
39
40
41
/* -------------------------------- Added Visitor Methods ------------------------------- */
42
void ReactVisitor::Visit(Cat *c) { // Finally comes here <<-------------
43
person->TryToPet(c);
44
}
45
void ReactVisitor::Visit(Dog *d) { // Finally comes here <<-------------
46
person->RunAwayFrom(d);
47
}
48
/* --------------------------------------------------------------------------------------- */
49
50
51
int main() {
52
Person p;
53
for(auto&& animal : vector<Animal*>{new Dog, new Cat})
54
p.ReactTo(animal);
55
return 0;
56
}
- As you can see above, rather depending directly on
ReactVisitor, we have takenAnimalVisitoras one more layer of indirection. Andvisit(AnimalVisitor *)method inCatandDogclass acceptAnimalVisitoras a parameter. - This gives us two benefits, i). we do not have to write person's behaviour in
CatandDogclass, 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 and single image of function calling chain with code snippet will simplify it a lot.
- From
Person::ReactTo, we callAnimal::visit, which will dispatch to the appropriate overridden visit i.e. eitherCat::visitorDog::visit. - From the overridden
Cat::visit(AnimalVisitor*), we callAnimalVisitor::visit, which will again dispatch to the appropriate overridden i.e. eitherReactionVisitor::visit(Cat*)orReactionVisitor::visit(Dog*).
Alternate Approach to Double Dispatch in Modern C++ using std::variant and std::visit
C++
xxxxxxxxxx
1
32
1
struct Animal {
2
virtual string name() = 0;
3
};
4
5
struct Cat : Animal {
6
string name() { return "Cat"; }
7
};
8
9
struct Dog : Animal {
10
string name() { return "Dog"; }
11
};
12
13
struct Person {
14
void RunAwayFrom(Animal *animal) { cout << "Run Away From " << animal->name() << endl; }
15
void TryToPet(Animal *animal) { cout << "Try To Pet " << animal->name() << endl; }
16
};
17
18
struct ReactVisitor {
19
void operator()(Cat *c) { person->TryToPet(c); }
20
void operator()(Dog *d){ person->RunAwayFrom(d); }
21
Person *person = nullptr;
22
};
23
24
using animal_ptr = std::variant<Cat*, Dog*>;
25
26
int main() {
27
Person p;
28
ReactVisitor rv{&p};
29
for(auto&& animal : vector<animal_ptr>({new Dog, new Cat}))
30
std::visit(rv, animal);
31
return 0;
32
}
- So for those of you who are not familiar with the
std::variant, you can consider it as a union. And linestd::variant<Cat*, Dog*>, suggest that you can use/assign/access eitherCat*orDog*at a time. - And Modern C++ provide us
std::visitwhich accept callable i.e.ReactVisitorin our case having overloaded function operator for each type andstd::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,
ReactVisitoronly 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 addsound()method for each different Animal, you can createSoundVisitorand rest of the edit goes as sameReactVisitor. - 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 and wants to add new functionality.
- Performance over
dynamic_cast,typeid()and check forenum/stringcomparison.
Usecase of Double Dispatch Mechanism
- Sorting a mixed set of objects: You can implement filtering with double-dispatch. E.g., "Give me all the
Catsfrom avector<Animal*>". - You can add additional functionality to the whole inheritance hierarchy without modifying it over and over E.g. if you want to add
sound()method for each different Animal, you can createSoundVisitorand rest of the edit goes as sameReactVisitor. - 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.
Double dispatch
Published at DZone with permission of Vishal Chovatiya. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments