Why we need accept() in Visitor pattern and why we cannot call visitor.visit() directly?

Question

I am revising the Visitor pattern I used some time ago. We have base class Element which has virtual method accept(Visitor) and this method is overridden in all classes inheriting from Element. And all that accept() does in any derived class is to call visitor->visit(*this). Now when the client runs the code, he/she does for example:

Visitor& theVisitor = *new ConcreteVisitor();    
for_each(elements.begin(), elements.end(), [](Element& e) { e.accept(theVisitor));})

Why the client cannot just call visitor->visit(element) like this:

Visitor& theVisitor = *new ConcreteVisitor();    
for_each(elements.begin(), elements.end(), [&theVisitor](Element& e) { theVisitor.visit(e); });

What useful information is in calling element.accept(visitor) which in turns calls visitor.visit(element)? This makes the usage of the Visitor pattern cumbersome and requires extra code in all the hierarchy of Element classes.

So can someone explain benefits of accept() here?

Answer 1

I've been long confused with the Visitor pattern and I've been trying to find explanations all over the Internet and these explanations confused me even more. Now I realised the reasons why Visitor pattern is needed and the way how it is implemented, so here it is:

Visitor pattern in needed to solve the Double Dispatch problem.

Single dispatch - when you have one class hierarchy and you have an instance of a concrete class in this hierarchy and you want to call an appropriate method for this instance. This is solved with function overriding (using virtual function table in C++).

Double dispatch is when you have two class hierarchies and you have one instance of concrete class from one hierarchy and one instance of concrete class from the other hierarchy and you want to call the appropriate method which will do the job for those two particular instances.

Let's look at an example.

First class hierarchy: animals. Base: Animal, derived: Fish, Mammal, Bird. Second class hierarchy: invokers. Base: Invoker, derived: MovementInvoker (move the animal), VoiceInvoker (makes the animal to sound), FeedingInvoker (feeds the animal).

Now for every specific animal and every specific invoker we want just one specific function to be called that will do the specific job (e.g. Feed the Bird or Sound the Fish). So altogether we have 3x3 = 9 functions to do the jobs.

Another important thing: the client who runs each of those 9 functions does not want to know what concrete Animal and what concrete Invoker he or she has got at hand.

So the client wants to do something like:

void act(Animal& animal, Invoker& invoker)
{
  // Do the job for this specific animal using this specific invoker
}

Or:

void act(vector<shared_ptr<Animal>>& animals, vector<shared_ptr<Invoker>>& invokers)
{
    for(auto& animal : animals)
    {
        for(auto& invoker : invokers)
        {
            // Do the job for this specific animal and invoker.
        }
    }
}

Now: how is it possible in RUN-TIME to call one of the 9 (or whatever) specific methods that deals with this specific Animal and this specific Invoker?

Here comes Double Dispatch. You absolutely need to call one virtual function from first class hierarchy and one virtual function from the second.

So you need to call a virtual method of Animal (using virtual function table this will find the concrete function of the concrete instance in the Animal class hierarchy) and you also need to call a virtual method of Invoker (which will find the concrete invoker).

YOU MUST CALL TWO VIRTUAL METHODS.

So here is the implementation (you can copy and run, I tested it with g++ compiler):

visitor.h:

#ifndef __VISITOR__
#define __VISITOR__

struct Invoker; // forward declaration;

// -----------------------------------------//

struct Animal
{
    // The name of the function can be anything of course.
    virtual void accept(Invoker& invoker) = 0;
};

struct Fish : public Animal
{
    void accept(Invoker& invoker) override;
};

struct Mammal : public Animal
{
    void accept(Invoker& invoker) override;
};

struct Bird : public Animal
{
    void accept(Invoker& invoker) override;
};

// -----------------------------------------//

struct Invoker
{
  virtual void doTheJob(Fish&   fish)   = 0;
  virtual void doTheJob(Mammal& Mammal) = 0;
  virtual void doTheJob(Bird&   Bird)   = 0;
};

struct MovementInvoker : public Invoker
{
  void doTheJob(Fish&   fish)   override;
  void doTheJob(Mammal& Mammal) override;
  void doTheJob(Bird&   Bird)   override;
};

struct VoiceInvoker : public Invoker
{
  void doTheJob(Fish&   fish)   override;
  void doTheJob(Mammal& Mammal) override;
  void doTheJob(Bird&   Bird)   override;
};

struct FeedingInvoker : public Invoker
{
  void doTheJob(Fish&   fish)   override;
  void doTheJob(Mammal& Mammal) override;
  void doTheJob(Bird&   Bird)   override;
};

#endif

visitor.cpp:

#include <iostream>
#include <memory>
#include <vector>
#include "visitor.h"
using namespace std;

// -----------------------------------------//

void Fish::accept(Invoker& invoker)
{
    invoker.doTheJob(*this);
}

void Mammal::accept(Invoker& invoker)
{
    invoker.doTheJob(*this);
}

void Bird::accept(Invoker& invoker)
{
    invoker.doTheJob(*this);
}

// -----------------------------------------//

void MovementInvoker::doTheJob(Fish& fish)
{
    cout << "Make the fish swim" << endl;
}

void MovementInvoker::doTheJob(Mammal& Mammal)
{
    cout << "Make the mammal run" << endl;
}

void MovementInvoker::doTheJob(Bird& Bird)
{
    cout << "Make the bird fly" << endl;
}

// -----------------------------------------//

void VoiceInvoker::doTheJob(Fish& fish)
{
    cout << "Make the fish keep silence" << endl;
}

void VoiceInvoker::doTheJob(Mammal& Mammal)
{
    cout << "Make the mammal howl" << endl;
}

void VoiceInvoker::doTheJob(Bird& Bird)
{
    cout << "Make the bird chirp" << endl;
}

// -----------------------------------------//

void FeedingInvoker::doTheJob(Fish& fish)
{
    cout << "Give the fish some worms" << endl;
}

void FeedingInvoker::doTheJob(Mammal& Mammal)
{
    cout << "Give the mammal some milk" << endl;
}

void FeedingInvoker::doTheJob(Bird& Bird)
{
    cout << "Give the bird some seed" << endl;
}

int main()
{
    vector<shared_ptr<Animal>> animals = { make_shared<Fish>   (),
                                           make_shared<Mammal> (),
                                           make_shared<Bird>   () };

    vector<shared_ptr<Invoker>> invokers = { make_shared<MovementInvoker> (),
                                             make_shared<VoiceInvoker>    (),
                                             make_shared<FeedingInvoker>  () };

    for(auto& animal : animals)
    {
        for(auto& invoker : invokers)
        {
            animal->accept(*invoker);
        }
    }
}

Output of the above code:

Make the fish swim
Make the fish keep silence
Give the fish some worms
Make the mammal run
Make the mammal howl
Give the mammal some milk
Make the bird fly
Make the bird chirp
Give the bird some seed

So what happens when the client has got an instance of Animal and an instance of Invoker and calls animal.accept(invoker)?

Suppose that the instance of Animal is Bird and the instance of Invoker is FeedingInvoker.

Then thanks to virtual function table Bird::accept(Invoker&) will be called which will in turn run invoker.doTheJob(Bird&). As Invoker instance is FeedingInvoker, virtual function table will use FeedingInvoker::accept(Bird&) for this call.

So we made the double dispatch and called the correct method (one of 9 possible methods) for Bird and FeedingInvoker.

Why is Visitor pattern good?

1. The client does not need to depend on both complex class hierarchies of Animals and Invokers.

2. If new concrete animal (say, Insect) needs to be added, no existing Animal hierarchy needs to be changed. We only need to add: doTheJob(Insect& insect) to Invoker and all derived invokers.

Visitor pattern elegantly implements the open/closed principle of object-oriented design: the system should be open to extensions and closed to modifications.

(In classic Visitor pattern Invoker would be replace by Visitor and doTheJob() by visit(), but to me these names don't actually reflect the fact that some job is done on elements).