28 Aug 2012
The other day I was developing a Java code and I needed to use
instanceof, but since I have read that this is a sign of bad design, I asked for help and was recommended the Visitor pattern.
In this post we’ll talk about this design pattern in Java, that is where my need began, but also in C++ because the implementation is related to vtables, which I’ve been wanting to read about.
Let us consider the following example, where we have the classes
Cat, which are specializations of
Animal and have methods to emit sound, respectively
meow(). We want to implement a method
emitSound() which receives an instance of
Animal and emits the sound according to the actual class of the instance. A first alternative using
instanceof is the following:
Here we can quote Scott Meyers, from Effective C++ book:
Anytime you find yourself writing code of the form “if the object is of type T1, then do something, but if it’s of type T2, then do something else,” slap yourself.
To get rid of
instanceof, we can add the method
Animal interface and replace
bark()/meow() for it. In our method
emitSound(), we let polymorphism choose the correct implementation.
Another possibility is to delegate the implementation of
emitSound() to another class through the use of the Visitor pattern. This pattern considers two types of classes: an element and a visitor. The element implements a method usually named
accept() while the visitor implements the method
accept() method receives a visitor as a parameter and calls the method
visit() from this visitor with itself as parameter. This way, the visitor can implement the
visit() method for each possible element.
We can implement like this:
The advantage of this approach is that
SoundEmissor may contain members and methods related to the way animals emit sounds. Otherwise, these methods would ended up being implemented in
Another advantage is that the visitor implementation can be chosen at runtime and, being a dependency injection, simplifies testing.
In C++ we don’t have
instanceof, but we can use the
typeid() operator instead. According to , if the argument to this operator is a reference or a dereferenced pointer to a polymorfic class,
typeid() will return a
type_info corresponding to the runtime object type.
Again, we can create
emitSound() in a interface and make use of polymorphism. In C++ we can implement an interface through a class containing only purely virtual function and no visible constructor like
Animal in the code below:
The Visitor pattern can be similarly implemented in the following way:
We just saw that the Visitor pattern relies on the use of virtual functions. So now, let’s analyse how C++ implements these kind of functions. Before that, we need to understand the concept of dynamic dispatch.
Dynamic dispatch is a technique used in cases where different classes (with a common ancestor) implement the same methods, but we can’t tell on compile time what is the type of a given instance, as in the cases above.
In C++ and Java, this type of dispatch is also known as single dispatch since it only considers the type of the object calling the method. In Lisp and other few languages, there is the multiple dispatch that also takes into account the type of the parameters.
As an example, take a look at the following code:
We’ll get a compile error since method/function matching for parameters is made at compile time. In this case we need to have an implementation for the Animal type.
Now, we’ll see how C++ implements dynamic dispatch.
Although the C++ standard does not specify how dynamic dispatch should be implemented, compilers in general use the a structure called the virtual method table, known for other names such as vtable, which is the one we’ll use henceforth. Actually, this table is an array of pointers to virtual methods.
Each class that defines or inherits at least one virtual method has its own vtable. This table points to the virtual methods defined by the nearest ancestral (including the class itself) that are visible for that class. Besides, each instance of these classes will have an additional member, a pointer that points to the table corresponding to the class used to instantiate that object.
As an example, if we were to instantiate a
Dog from Listing 5:
animal's pointer points to
Dog’s and not
Animal’s. Thus, when we do
the corresponding table is looked up to find exactly which
emitSound() to call. Note that virtual methods requires an extra indirection that may affect performance. Because of this dynamic dispatch is not performed by default unless some class defines a virtual method. On the other hand, in Java this is done by default.
Let’s see a final example,
We can analyse the vtables from class A and B compiling the code above with
gcc using the
-fdump-class-hierarch flag. A text file with extension .class will be generated like this:
Here we can see that function
A::bar appear in
A’s vtable, but
A::baz don’t, since it was not declared virtual. On
B’s vtable we have
A::foo, because it was not overridden in
B. We also have
B::bar, although it has not been declared virtual in
B, this property was inherited from
B::baz appears on the vtable because it was declared virtual in
We can also see the value that the instances of such classes will have:
vptr=((& A::_ZTV1A) + 8u) and
vptr=((& B::_ZTV1B) + 8u), which is the offset to the functions’ pointers on the respective tables. A nice reference for a understanding of vtables can be seen in .