The Visitor Pattern is one of the base implementation patterns in software development. It can solve a base use case which occurs in nearly all applications which use inheritance to implement a system of base classes and derived classes. But unfortunately, the Visitor Pattern comes with a big disadvantage: it is one of the most misunderstood and misused patterns I know. Therefore, I want to spend some time to analyze the pattern, explain its strength, look for the reasons for the misunderstandings and show some ways to implement the pattern. As these are large topics I will split it up into several articles. Within this article we will start with the basic ideas of the pattern and have a look at the technical background. Within the next articles we will continue with concrete implementation examples for different use cases, remove the misunderstandings by finding the real meaning of the pattern, compare it with other patterns and have a look at the pros and cons of the Visitor.

Motivation

Collections are widely used data type structures. In object oriented systems, these collections often contain objects of different types, stored as pointers to a common base type. Algorithms or queries which perform operations based on these data collections will on one hand use the common base data interface and on the other hand need to use the type specific interface. Furthermore, the data collections may have very different kinds of complexity: list, tree or other structure. Independent of the data structure and independent whether the elements are stored as base class pointer, we want to iterator over elements and execute some algorithms based on these elements.

Reasons for Misunderstandings

Before we look at the Visitor Pattern I want to explain why there are is so many confusion and misunderstanding regarding this pattern.

Many of the software design patterns are easy to understand. The patterns itself and the involved classes and functions have clear names telling us what they are used for. The pattern implementations have a simple structure and they use well known language specific features.

But the Visitor pattern is different. It hasn’t a simple structure but is more complex. It hasn’t a clear naming. The name Visitor may arouse expectations which can be totally wrong. The interface name and the function names are meaningless too. And finally, it isn’t based on language specific features but it is a workaround for language specific limitations.

You can see the confusion about the Visitor pattern if you read a couple of articles and compare their statements. You will find very different statements about the purpose of the pattern, the use cases it solves and the reasons why you should use the pattern. Please, don’t get me wrong, these articles are not incorrect at all but they use the Visitor pattern in a not suitable context. There are many use cases which can be solved better with other patterns ore oven with standard language features.  In these cases, the Visitor pattern is over-engineering which results in some big disadvantages like less understandable and less maintainable source code with higher chance for errors.

Within this and the future articles I want to analyze and explain the Visitor pattern in detail to clarify and remove all the sources for misunderstandings.

Basics

After the long foreword and introduction, we will now start get to know the Visitor pattern and its implementation. At first, we will try to find a definition for this pattern. As mentioned before, you will find a lot of different explanations and definitions which are not contrary but may contain too much details and facts which are true in general but not specific for the Visitor pattern. Therefore, I want to give this short definition:

The Visitor design pattern is a way to traverse over all elements of a data container and get the type specific element instances. It separates the algorithms from the object structure on which they operate.

The definition mentions three important points: traverse elements, get type specific instance and separation of concerns.

Let’s compare this definition with the definition of the Iterator pattern: The Iterator pattern is a design pattern which uses an iterator to traverse a container and access the container’s elements. It separates the algorithms from the object structure on which they operate.

So, the Visitor pattern and the Iterator pattern are very similar. They will both separate algorithms from the data structure. Therefore, this separation of concerns isn’t a criterion to choose this pattern. But unfortunately, you will find a lot of articles which use this criterion as the reason to choose the Visitor pattern.

But there are also some differences between the two patterns. They have a different way to traverse the elements and they will return different element instances. The Iterator pattern returns the element as it is. If the data container holds elements as pointers to the common base class, the base class element pointer is returned. In contrast, the Visitor pattern will return the specific element type instance. Therefore, it will not return the base class pointer, but will return the specific derived types. The way to traverse the elements and the way to return the elements are the real characteristics of the Visitor pattern.

The Visitor pattern is implemented by using “double dispatch”. This technique allows to access the specific element types without any workaround like casting. To understand the pattern, we must understand this implementation technique. Therefore, we will continue with a short analysis and comparison of “single dispatch” and “double dispatch”.

Single Dispatch

The decision of which version of a method to call based on a single object is called single dispatch. This is the standard way of calling a function and it is directly supported by common object-oriented languages. When you call a regular virtual function, it is a single dispatch. The code that gets executed depends on the runtime type of a single object.

The following code shows an example application which uses single dispatch. We have date elements with common virtual and object specific non-virtual functions. The element instances will be stored within a container as a reference to the base object. Furthermore, we have a printer algorithm which loops over the container elements and calls the common virtual and object specific non-virtual function to print the outputs.

//------------------------------
// elements
//------------------------------

class BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of Base was called" << std::endl; }; 
};

class DerivedElementA : public BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of A was called" << std::endl; };

  std::string GetName() { return "element a"; }
};

class DerivedElementB : public BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of B was called" << std::endl; };

  std::string Name() { return "element b"; }
};

//------------------------------
// data container
//------------------------------

class DataContainer
{
public:
  std::vector mElements;
};

//------------------------------
// algorithm
//------------------------------

class Printer
{
public:
  void ShowAll(DataContainer& data)
  {
    for (const auto& element : data.mElements)
    {
      element->DoSomething();

      DerivedElementA* elementA = dynamic_cast(element);
      if (elementA)
      {
        std::cout <GetName() << std::endl;
      }

      DerivedElementB* elementB = dynamic_cast(element);
      if (elementB)
      {
        std::cout <Name() << std::endl;
      }
    }
  }
};

//------------------------------
// application
//------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
  DerivedElementA* elementA = new DerivedElementA();
  DerivedElementB* elementB = new DerivedElementB();

  DataContainer container;
  container.mElements.push_back(elementA);
  container.mElements.push_back(elementB);

  Printer printer;
  printer.ShowAll(container);

  delete elementA;
  delete elementB;

	return 0;
}

The source code shows two examples for single dispatch function calls used to call the element functions. Based on the concrete instance we can call the object specific functions and based on the base class instance pointer we can call the virtual function and the according object specific function is executed.

C++ can do this run-time lookup dynamic dispatch for one type at a time, so it is a single dispatch. But c++ is not able to select a function based on two dynamic types, which would be a double dispatch. Another language specific limitation comes with the virtual function. We cannot add a virtual function to a class hierarchy without a modification of the base class which provides the interface.

Within the example we can see these limitations. It would not be possible to call the type specific functions of the derived classes without the use of any workaround, in our case the use of a dynamic cast. This workaround is necessary as c++ does not support double dispatch.

Double Dispatch

Double dispatch allows to call a method by a dynamic dispatch based on its runtime type. Furthermore, the decision of which version of a method is invoked based on a combination of two objects is also called double dispatch. Double dispatch is not directly supported by C++. Workaround for these limitations are dynamic casts, the Visitor pattern or the use of according third-party libraries.

We will now change the previous example a little bit. We will try to eliminate the need of the dynamic cast. This could be done if we implement an own double dispatch mechanism. Our goal is to get the runtime specific object by the base class pointer. So, we must add a virtual function to our base class to request the actual object instance. Each derived class can override the virtual function and returns its actual type specific instance. Furthermore, we need a receiver which can accept these different type specific instances. In the example, the receiver is the printer algorithm. Therefore, we will extend the printer with an interface to receive the object instances. And the element class will be extended by the virtual function to request the element instance.

//------------------------------
// forward declaration
//------------------------------

class DerivedElementA;
class DerivedElementB;

//------------------------------
// printer interface
//------------------------------

class IPrinter
{
public:
  virtual void ShowDerivedElement(DerivedElementA* elementA) = 0;
  virtual void ShowDerivedElement(DerivedElementB* elementB) = 0;  
};

//------------------------------
// elements
//------------------------------

class BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of Base was called" << std::endl; };

  virtual void GetElement(IPrinter* printer){};
};

class DerivedElementA : public BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of A was called" <ShowDerivedElement(this);
  };
};

class DerivedElementB : public BaseElement
{
public:
  virtual void DoSomething(){ std::cout << "DoSomething() of B was called" <ShowDerivedElement(this);
  };
};

//------------------------------
// data container
//------------------------------

class DataContainer
{
public:
  std::vector mElements;
};

The printer algorithm must implement the instance receiver functions and is now able to call the type specific element methods within these instance receivers.

//------------------------------
// algorithm
//------------------------------

class Printer : public IPrinter
{
public:
  void ShowAll(DataContainer& data)
  {
    for (const auto& element : data.mElements)
    {
      element->GetElement(this);
    }
  }

  void ShowDerivedElement(DerivedElementA* elementA)
  {
    elementA->DoSomething();
    std::cout <GetName() <DoSomething();
    std::cout <Name() << std::endl;
  }
};

//------------------------------
// application
//------------------------------

int _tmain(int argc, _TCHAR* argv[])
{
  DerivedElementA* elementA = new DerivedElementA();
  DerivedElementB* elementB = new DerivedElementB();

  DataContainer container;
  container.mElements.push_back(elementA);
  container.mElements.push_back(elementB);

  Printer printer;
  printer.ShowAll(container);

  delete elementA;
  delete elementB;

  return 0;
}

With this kind of implementation, we could successfully remove the dynamic cast. The algorithm instance has called an element method which has done a call to the algorithm method. We have executed two v-table calls to assign the operation to the data. The functionality is based on a combination of two objects and so we have implemented a double dispatch behavior.

Of course, you may ask whether it makes sense to implement such a complex system of mutual method calls just to have something which behaves like double dispatch. We could use single dispatch instead and will have the same results. This is a very important fact! Such a double dispatch implementation is always complex, creates additional dependencies and makes the source code harder to understand and to maintain. But on the other hand, it can add some benefit, like the elimination of the dynamic cast, which helps to eliminate errors. I would suggest using single dispatch as default implementation technique. You should use double dispatch in use cases only, were the implementation leads to benefits which exceed the disadvantages of the complex source code.

Definition

Within the “Basics” chapter we already seen a short definition for the Visitor pattern. Based on this definition and based on the double dispatch technique I want to explain the Visitor pattern in more detail.

The Visitor pattern defines an infrastructure to access a complex and dynamic data structure.  It implements an enumeration over the data structure elements independent of the structure type or complexity. To access each element a double dispatch technique is used which requests the specific element type instance and provides these instance to a receiver. This allows to implement algorithms based on the data structure. These algorithms will use the enumeration feature to traverse all elements and the algorithms implement the element instance receiver functions. So, they get access to the type specific instances of all elements.

The visitor pattern allows a separation of the data structure, the traversing over the structure and the algorithms based on the data. Furthermore, it allows to access the specific object independent whether it is stored as specific object or a pointer to any of the base classes. So, the data structure can hold elements without knowing their real types. Unfortunately, the pattern can only be implemented by using double dispatch. As we learned, double dispatch is based on a combination of two objects. This unavoidable adds a dependency between these two objects, in this case between the data elements and the algorithms. Later on, we will see the issues and disadvantages of this dependency.

Structure of the Pattern

The definition and explanation above already names the components of the Visitor pattern. These are:

• Data Elements
• Data Container
• Enumerator
• Algorithm

If you look at the Visitor pattern definition, done by the “Gang of Four” you will not find an “Enumerator” component. In my opinion, the pattern should not be used in use cases where you don’t need to enumerate over elements. There are much better patterns available in these cases. I will explain this in more detail later.

Many of the examples and definitions out there also respect this aspect and contain a traversing over the data elements. But most of them will not explicitly separate the algorithms from the traversing. But as these are very different concerns, they should be separated into two different components. Therefore, my big picture of the pattern explicitly contains the “Enumerator” component.

Naming

As mentioned before I don’t like the name of the pattern and its components and functions. They are not bad at all but I think they are to general. They are suitable to describe a generic concept like double dispatch but they are not sufficiently concrete to describe such a specific design pattern.

AS we have seen in the double dispatch chapter, a client will not use the element object directly. Instead it will call an element function which should “accept” the client as receiver for the element instance. Within this element function the element instance is send back to the client so the client can “visit” the specific element instance. Therefore, the visitor pattern defines these two methods: “accept” and “visit”. And according to this visiting thought it is called “Visitor”. But you see, even within this attempt for a serious explanation, the naming sounds strange.

Within the article and the code examples I want to use a clear naming. Of course, I will continue to call the pattern “Visitor pattern”. Furthermore, I want to call the interfaces according to this pattern. This will ensure an explicit relation with the pattern and I think the source code will be easier to understand if common names are used. So, I want to call the interface which must be implemented by the data elements “Visitable” and the interface of the algorithms and enumerators “Visitor”. The function to get the element instance well be called “GetInstance” and not “accept”. The function to transfer the instance to the instance receiver will be called “InstanceReceiver” and not “visit”. This function could also be called “ProcessInstance” or something in this way, but as we don’t know whether the algorithm reads, writes or even uses the element I prefer such a general name like “InstanceReceiver”.

Example application

Within the further progress of the article I want to introduce a simple example application. This application should show use cases of a simple shop system. It contains some articles which get stored in simple lists or even complex structures. And we want to create some queries to access and analyze the data. The example will therefore contain the components we have seen so far: elements, data containers, enumerators and algorithms. Within the example we will call these components: elements, containers, enumerators and queries.

Summary and Outlook

This first article about the Visitor pattern was thought as short introduction into this topic. But the resulting size of the article is a good indicator for the complexity of the pattern. So far, we got an overview about the use cases which could be solved by the pattern. We have analyzed the technical background needed to implement the pattern. And we build up a detailed background knowledge to understand the purpose of the Visitor. Based on this knowledge you will not belong to the group of developers which misunderstands the pattern and therefore don’t use it or use it in a wrong way.

Within the next articles we will expand our knowledge and see some concrete implementations of the pattern. These implementations will cover the different use cases like enumeration and dispatching and they will show different techniques to implement the pattern, like inheritance, composition or templates. Furthermore, we will analyze the pros and cons of the pattern to get a better feeling whether a use case can be solved by the pattern or not.