Patterns : Visitor

Today’s pattern is the Visitor, which is a way of packaging up a set of custom behaviors based on some criteria (often object type) into a single wrapper. The custom behaviors usually support some specific goal, like collecting information from a graph that holds different types of nodes or manipulating the objects in an array. Visitors are useful when you have a bunch of things that are different in a way that doesn’t allow you to access them using a single interface. Visitors are common when the elements being ‘visited’ are organized in a way that is not straightforward to traverse, like nodes in a graph. It’s not a useful pattern when you have a set of the same type of thing or just have one thing. Visitors can collect information about the elements they encounter, change the elements they visit, or generate new items based on what they see (like the old favorite the using visitors to create deep copies).

Example

First we declare a base called Visitable so that different types of classes can be marked as visitable. Each class that’s visited needs to implement an accept() method that takes the visitor base class. We need to forward declare the visitor’s base which I’ve called VisitorBase.

struct VisitorBase;

struct Visitable
{
 virtual void accept(VisitorBase &v) = 0;
};

Let’s say we are creating a module for some motor vehicle compliance software that checks a list of crafts and determines if they each meet some safety requirements that dramatically differ per craft. For starters lets create some classes for the crafts that someone might own, they will all inherit from a base Craft class which will be visitable.

struct Craft : Visitable
{
 int weight, color;
 virtual void accept(VisitorBase &v) = 0;
};

struct Car : Craft
{
 Car(int numberOfSeats, int numberOfSeatbelts) : 
   numberOfSeats(numberOfSeats),
   numberOfSeatbelts(numberOfSeatbelts){};
 int numberOfSeats, numberOfSeatbelts;
 virtual void accept(VisitorBase &v);
};

struct Plane : Craft
{
 Plane(int numberOfSeats, int numberOfParachutes) :
   numberOfSeats(numberOfSeats),
   numberOfParachutes(numberOfParachutes){};
 int numberOfSeats, numberOfParachutes;
 virtual void accept(VisitorBase &v);
};

struct Boat : Craft
{
 Boat(int numberOfLifeVests, int maxNumberOfPassengers) : 
   numberOfLifeVests(numberOfLifeVests),
   maxNumberOfPassengers(maxNumberOfPassengers){};

 int numberOfLifeVests, maxNumberOfPassengers;
 virtual void accept(VisitorBase &v);

};

struct AircraftCarrier : Boat
{
 AircraftCarrier(int maxNumberOfPlanes, std::vector<Plane*>* planes) :
   Boat(50,50), //lots of sailors
   maxNumberOfPlanes(maxNumberOfPlanes),
   planes(planes){};
 std::vector<Plane*>* planes;
 int maxNumberOfPlanes;
 virtual void accept(VisitorBase &v);
};

The accept methods are what you might expect, each one calls the visitor’s visit method and passes a pointer to itself as a parameter. This may seem a little inside out but it’s done because the this pointer is typed to the subclass, which the would not be available to the visitor any other way. If the visitor just tried to inspect each item in a collection of Crafts, it would think they are all typed as Crafts because it doesn’t know any better and the container doesn’t know any better. The only thing that knows what it really is are the crafts themselves, which is why we give them the responsibility of passing the pointer into the visitor.

void Car::accept(VisitorBase &v) {v.visit(*this);};

void Boat::accept(VisitorBase &v) {v.visit(*this);};

void Plane::accept(VisitorBase &v) {v.visit(*this);};

void AircraftCarrier::accept(VisitorBase &v){
  v.visit(*this);
  for(auto i = planes.begin(); i != planes.end(); i ++){
    v.visit(**i);
  }
};

The only noteworthy one of the accept implementations is for the AircraftCarrier since it passes the visitor to any planes it might be carrying. This could just as easily be moved into the visitor and that’s what I’ve done in attached zip of this project.

Since all of the crafts accept a VisitorBase, one needs to be available. We’ve put making this class off for long enough, luckily it doesn’t need to do anything aside from declare some abstract methods. Those abstract methods will need to be implemented in our subclasses. Here’s the abstract base class and done some forward declaring of the types that will be visited.

struct AircraftCarrier;
struct Boat;
struct Plane;
struct Car;

struct VisitorBase
{
 virtual void visit(Car& c) = 0;
 virtual void visit(Plane& p) = 0;
 virtual void visit(Boat& b) = 0; 
 virtual void visit(AircraftCarrier& ac) = 0;
};

Whenever we subclass this we’ll provide implementations. Here’s the safety compliance visitor that does the safety checks and stores the result in a boolean. Notice how each craft gets a different set of checks, this is the power of the visitor.

struct CraftComplianceVisitor : VisitorBase
{
  bool compliant;

  CraftComplianceVisitor():compliant(true){};

 void CraftComplianceVisitor::visit(Car& car) {
  compliant &= car.numberOfSeatbelts >= car.numberOfSeats;
 }

 void CraftComplianceVisitor::visit(Boat& boat) {
  compliant &= boat.maxNumberOfPassengers >= boat.numberOfLifeVests;
 };

 void CraftComplianceVisitor::visit(AircraftCarrier& ac) {
  visit(static_cast<Boat&>(ac));
  compliant &= ac.maxNumberOfPlanes >= ac.planes->size();
 };

 void CraftComplianceVisitor::visit(Plane& p) {
  compliant &= p.numberOfParachutes>= p.numberOfSeats;
 };
};

The only thing left is some code that actually executes this program

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector<Craft*> crafts;
  crafts.push_back(new Boat(1,1));
  crafts.push_back(new Plane(1,1));
  crafts.push_back(new Car(1,1));

  auto planesOnAircraftCarrier = new std::vector<Plane*>();
  planesOnAircraftCarrier->push_back(new Plane(1,1));
  planesOnAircraftCarrier->push_back(new Plane(1,1));
  planesOnAircraftCarrier->push_back(new Plane(1,1));

  crafts.push_back(new AircraftCarrier(3, planesOnAircraftCarrier));
  
  CraftComplianceVisitor v;
  for(auto i = crafts.begin(); i != crafts.end(); i++)  {
    (*i)->accept(v);
  }
  
  std::cout << "\nthe crafts are " << (!v.compliant ? "not " : "") << "compliant." << std::endl;

  return 0;
};

Since all of these crafts are in compliance we shouldn’t have the “not” inserted into our output message at the bottom. Once most of the boilerplate code for accepting() and visiting() is in place, creating new visitors is easy and can be very handy. Other visitors that we might make in this same project are a diagnostic visitor to print the values of the parameters for each variation of craft, a compliance fixer visitor that would change the crafts to be in compliance with some rule, or a clone visitor which would provide a copy of each of the crafts (including sub-crafts in the case of the AircraftCarrier).

One thing we played fast and loose with in this introduction was const correctness. I’m of the mind that everything should be marked const that can be. Since our visitor doesn’t change the crafts it visits, it should have taken const inputs to its visit() method. If you take a look at the project linked to through the addendum, I’ve made that visitor const correct. You should always strive to put const everywhere, it’s a clear communication of intent to other programmers.

I’ve archived the code from this post (a Visual Studio 2012 project) into a zip which you can download. I’ve since updated the above to print some information to the console as the visitor explores each craft, so it’s not identical. You should download it and take a look, maybe even try creating one of those other visitors I mentioned above!

Addendum

  • If you are keen on templates you might have tried to make the crafts visitable using something like this
    struct Visitable
    {
      template <typename T>
      void accept(T &v){
        v.visit(*this);
      }
    };
    
    struct Craft : Visitable
    {
      int weight, color;
    };

    The problem is that the dereferenced this pointer is going to be of the Visitable base class and not the subclasses (there is no such thing as virtual method templates). There are some clever things that you could do with F-bound polymorphism but the syntax that that produces is more complex than just implementing some virtual functions. Most of the time it’s probably easier to just use virtual methods and no templating.