Visitor pattern and double dispatch in C++.

In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.

In essence, the visitor allows one to add new virtual functions to a family of classes without modifying the classes themselves; instead, one creates a visitor class that implements all of the appropriate specializations of the virtual function. The visitor takes the instance reference as input, and implements the goal through double dispatch.

At first glance, double dispatch appears to be a natural result of function overloading. Function overloading allows the function called to depend on the type of the argument. Function overloading however is done at compile time using “name mangling” where the internal name of the function has the argument’s type encoded in it. So for example function foo(int) would internally be called __foo_i and function foo() would be called __foo_v (“v” for void). So there is no runtime overhead because there is no name collision and calling an overloaded function goes through at most one virtual table just like any other function. Dynamic dispatch is only based on the type of the calling object. Consider the following example:

#include <iostream>
class Tool {};
class Hammer : public Tool {};

class Person {
public:
  virtual void use(Tool&) {
    std::cout << "Person uses a Tool" << std::endl;
  }
  virtual void use(Hammer&) {
    std::cout << "Person uses an Hammer" << std::endl;
  }
};

class ycshao : public Person {
public:
  virtual void use(Tool&) {
    std::cout << "ycshao uses a Tool" << std::endl;
  }
  virtual void use(Hammer&) {
    std::cout << "ycshao uses an Hammer" << std::endl;
  }
};

int main ()
{
    Person thePerson;
    Tool theTool;
    Hammer theHammer;
    ycshao theycshao;
    Person& thePersonReference = theycshao;
    Tool& theToolReference = theHammer;

    theycshao.use(theTool);
    theycshao.use(theHammer);
    thePersonReference.use(theTool);
    thePersonReference.use(theHammer);
    //note the type of the pointer and the type of the object.
    thePerson.use(theToolReference);
    thePersonReference.use(theToolReference);
    return 0;
}

which will have output as:

ycshao uses a Tool
ycshao uses an Hammer
ycshao uses a Tool
ycshao uses an Hammer
Person uses a Tool
ycshao uses a Tool

The last two outputs are not what’s expected by us. We are expecting to see output as “Person uses an Hammer” and “ycshao uses an Hammer”. This happens because that while virtual functions are dispatched dynamically in C++, function overloading is done statically. This problem can be solved by double dispatch using a visitor pattern as follows.

#include <iostream>
class Tool;
class Hammer;
class Person {
public:
  virtual void use(Tool&) {
    std::cout << "Person uses a Tool" << std::endl;
  }
  virtual void use(Hammer&) {
    std::cout << "Person uses an Hammer" << std::endl;
  }
};

class ycshao : public Person {
public:
  virtual void use(Tool&) {
    std::cout << "ycshao uses a Tool" << std::endl;
  }
  virtual void use(Hammer&) {
    std::cout << "ycshao uses an Hammer" << std::endl;
  }
};

class Tool {
public:
    virtual void accept(Person& p)
    {
        p.use(*this);
    }
};
class Hammer : public Tool
{
public:
    virtual void accept(Person& p)
    {
        p.use(*this);
    }
};

int main ()
{
    Person thePerson;
    Tool theTool;
    Hammer theHammer;
    ycshao theycshao;
    Person& thePersonReference = theycshao;
    Tool& theToolReference = theHammer;

    theycshao.use(theTool);
    theycshao.use(theHammer);
    thePersonReference.use(theTool);
    thePersonReference.use(theHammer);
    //note the type of the pointer and the type of the object.
    thePerson.use(theToolReference);
    thePersonReference.use(theToolReference);
    //correct way to use
    theToolReference.accept(thePerson);
    theToolReference.accept(thePersonReference);
    return 0;
}

And the outputs will be what we expected:

ycshao uses a Tool
ycshao uses an Hammer
ycshao uses a Tool
ycshao uses an Hammer
Person uses a Tool
ycshao uses a Tool
Person uses an Hammer
ycshao uses an Hammer

References:
Visitor pattern
Double dispatch