<A NAME="auto1042"></A>
<LI><EM>Adding new ConcreteElement classes is hard.</EM>
The Visitor pattern makes it hard to add new subclasses of Element. Each
new ConcreteElement gives rise to a new abstract operation on Visitor and
a corresponding implementation in every ConcreteVisitor class. Sometimes a
default implementation can be provided in Visitor that can be inherited
by most of the ConcreteVisitors, but this is the exception rather than
the rule.

<A NAME="auto1043"></A>
<P>So the key consideration in applying the Visitor pattern is whether you
are mostly likely to change the algorithm applied over an object
structure or the classes of objects that make up the structure. The
Visitor class hierarchy can be difficult to maintain when new
ConcreteElement classes are added frequently. In such cases, it's
probably easier just to define operations on the classes that make up
the structure. If the Element class hierarchy is stable, but you are
continually adding operations or changing algorithms, then the Visitor
pattern will help you manage the changes.</P>

</LI>

<A NAME="trav-across-class"></A>
<LI><EM>Visiting across class hierarchies.</EM>
An iterator (see <A HREF="pat5dfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat5dfs.htm" TARGET="_mainDisplayFrame">Iterator (257)</A>) can visit the objects in a
structure as it traverses them by calling their operations. But an iterator
can't work across object structures with different types of elements. For
example, the Iterator interface defined on
<A HREF="pat5dfs-1.htm#class_Iterator_declaration" tppabs="http://ultra/development/DesignPatterns/lowres/pat5dfs.htm#class_Iterator_declaration" TARGET="_mainDisplayFrame">page 263</A> can access only objects of type <CODE>Item</CODE>:

<A NAME="auto1044"></A>
<PRE>
    template &lt;class Item>
    class Iterator {
        // ...
        Item CurrentItem() const;
    };
</PRE>

<A NAME="auto1045"></A>
<P>This implies that all elements the iterator can visit have a common parent
class <CODE>Item</CODE>.</P>

<A NAME="auto1046"></A>
<P>Visitor does not have this restriction.  It can visit objects that
don't have a common parent class. You can add any type of object to a
Visitor interface.  For example, in</P>

<A NAME="auto1047"></A>
<PRE>
    class Visitor {
    public:
        // ...
        void VisitMyType(MyType*);
        void VisitYourType(YourType*);
    };
</PRE>

<A NAME="auto1048"></A>
<P><CODE>MyType</CODE> and <CODE>YourType</CODE> do not have to be related through
inheritance at all.</P>

</LI>

<A NAME="auto1049"></A>
<P></P>

<A NAME="accumulatingstate"></A>
<LI><EM>Accumulating state.</EM>
Visitors can accumulate state as they visit each element in the object
structure.  Without a visitor, this state would be passed as extra
arguments to the operations that perform the traversal, or they
might appear as global variables.</LI>

<A NAME="auto1050"></A>
<P></P>

<A NAME="breakencap"></A>
<LI><EM>Breaking encapsulation.</EM>
Visitor's approach assumes that the ConcreteElement interface is powerful
enough to let visitors do their job.  As a result, the pattern often
forces you to provide public operations that access an element's
internal state, which may compromise its encapsulation.</LI>

</OL>

<A NAME="implementation"></A>
<H2><A HREF="#samplecode"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next: 
Sample Code"></A> Implementation</H2> 

<A NAME="auto1051"></A>
<P>Each object structure will have an associated Visitor class.  This
abstract visitor class declares a VisitConcreteElement operation for
each class of ConcreteElement defining the object structure.  Each
Visit operation on the Visitor declares its argument to be a
particular ConcreteElement, allowing the Visitor to access the
interface of the ConcreteElement directly.  ConcreteVisitor classes
override each Visit operation to implement visitor-specific behavior
for the corresponding ConcreteElement class.</P>

<A NAME="auto1052"></A>
<P>The Visitor class would be declared like this in C++:</P>

<A NAME="auto1053"></A>
<PRE>
    class Visitor {
    public:
        virtual void VisitElementA(ElementA*);
        virtual void VisitElementB(ElementB*);
    
        // and so on for other concrete elements
    protected:
        Visitor();
    };
</PRE>

<A NAME="auto1054"></A>
<P>Each class of ConcreteElement implements an <CODE>Accept</CODE> operation
that calls the matching <CODE>Visit...</CODE> operation on the visitor
for that ConcreteElement.  Thus the operation that ends up getting
called depends on both the class of the element and the class of the
visitor.<A NAME="fn10"></A><SUP><A HREF="#footnote10">10</A></SUP></P>

<A NAME="auto1055"></A>
<P>The concrete elements are declared as</P>

<A NAME="auto1056"></A>
<PRE>
    class Element {
    public:
        virtual ~Element();
        virtual void Accept(Visitor&amp;) = 0;
    protected:
        Element();
    };
    
    class ElementA : public Element {
    public:
        ElementA();
        virtual void Accept(Visitor&amp; v) { v.VisitElementA(this); }
    };
    
    class ElementB : public Element {
    public:
        ElementB();
        virtual void Accept(Visitor&amp; v) { v.VisitElementB(this); }
    };
</PRE>

<A NAME="auto1057"></A>
<P>A <CODE>CompositeElement</CODE> class might implement <CODE>Accept</CODE>
like this:</P>

<A NAME="auto1058"></A>
<PRE>
    class CompositeElement : public Element {
    public:
        virtual void Accept(Visitor&amp;);
    private:
        List&lt;Element*>* _children;
    };
    
    void CompositeElement::Accept (Visitor&amp; v) {
        ListIterator&lt;Element*> i(_children);
    
        for (i.First(); !i.IsDone(); i.Next()) {
            i.CurrentItem()->Accept(v);
        }
        v.VisitCompositeElement(this);
    }
</PRE>

<A NAME="auto1059"></A>
<P>Here are two other implementation issues that arise when you apply the
Visitor pattern:</P>

<OL>

<A NAME="doubledispatch"></A>
<A NAME="singledispatch"></A>
<LI><EM>Double dispatch.</EM>
Effectively, the Visitor pattern lets you add operations to classes
without changing them.  Visitor achieves this by using a technique
called <STRONG>double-dispatch</STRONG>.  It's a well-known technique.  In
fact, some programming languages support it directly (CLOS, for
example).  Languages like C++ and Smalltalk support
<STRONG>single-dispatch</STRONG>.

<A NAME="auto1060"></A>
<P>In single-dispatch languages, two criteria determine which operation
will fulfill a request: the name of the request and the type of
receiver. For example, the operation that a GenerateCode request will
call depends on the type of node object you ask. In C++, calling
<CODE>GenerateCode</CODE> on an instance of <CODE>VariableRefNode</CODE> will
call <CODE>VariableRefNode::GenerateCode</CODE> (which generates code for a
variable reference). Calling <CODE>GenerateCode</CODE> on an
<CODE>AssignmentNode</CODE> will call
<CODE>AssignmentNode::GenerateCode</CODE> (which will generate code for an
assignment). The operation that gets executed depends both on the kind
of request and the type of the receiver.</P>

<A NAME="auto1061"></A>
<P>"Double-dispatch" simply means the operation that gets executed
depends on the kind of request and the types of <EM>two</EM> receivers.
<CODE>Accept</CODE> is a double-dispatch operation.  Its meaning depends
on two types: the Visitor's and the Element's.  Double-dispatching
lets visitors request different operations on each class of
element.<A NAME="fn11"></A><SUP><A HREF="#footnote11">11</A></SUP></P>

<A NAME="auto1062"></A>
<P>This is the key to the Visitor pattern: The operation that gets
executed depends on both the type of Visitor and the type of Element
it visits.  Instead of binding operations statically into the Element
interface, you can consolidate the operations in a Visitor and use
<CODE>Accept</CODE> to do the binding at run-time.  Extending the Element
interface amounts to defining one new Visitor subclass rather than many new
Element subclasses.</P>

</LI>

<A NAME="trav-responsibility"></A>
<LI><EM>Who is responsible for traversing the object structure?</EM>
A visitor must visit each element of the object structure. The question
is, how does it get there? We can put responsibility for traversal in
any of three places: in the object structure, in the visitor, or in a
separate iterator object (see <A HREF="pat5dfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat5dfs.htm" TARGET="_mainDisplayFrame">Iterator (257)</A>).

<A NAME="auto1063"></A>
<P>Often the object structure is responsible for iteration. A collection
will simply iterate over its elements, calling the Accept operation on
each. A composite will commonly traverse itself by having each Accept
operation traverse the element's children and call Accept on each of
them recursively.</P>

<A NAME="iter-ext-int"></A>
<P>Another solution is to use an iterator to visit the elements. In C++,
you could use either an internal or external iterator, depending on what
is available and what is most efficient. In Smalltalk, you usually use
an internal iterator using <CODE>do:</CODE> and a block. Since internal
iterators are implemented by the object structure, using an internal
iterator is a lot like making the object structure responsible for
iteration. The main difference is that an internal iterator will not
cause double-dispatching&#151;it will call an operation on the <EM>visitor</EM> with an <EM>element</EM> as an argument as opposed to calling an
operation on the <EM>element</EM> with the <EM>visitor</EM> as an argument.
But it's easy to use the Visitor pattern with an internal iterator if
the operation on the visitor simply calls the operation on the element
without recursing.</P>

<A NAME="auto1064"></A>
<P>You could even put the traversal algorithm in the visitor, although you'll
end up duplicating the traversal code in each ConcreteVisitor for each
aggregate ConcreteElement. The main reason to put the traversal strategy
in the visitor is to implement a particularly complex traversal, one
that depends on the results of the operations on the object structure.
We'll give an example of such a case in the Sample Code.</P>

</LI>

</OL>

<A NAME="samplecode"><A>
<H2><A HREF="#knownuses"><IMG SRC="down3-1.gif" tppabs="http://ultra/development/DesignPatterns/lowres/gifsb/down3.gif" BORDER=0 ALT="next: 
Known Uses"></A> Sample Code</H2> 

<A NAME="auto1065"></A>
<P>Because visitors are usually associated with composites, we'll use the
<CODE>Equipment</CODE> classes defined in the Sample Code of
<A HREF="pat4cfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A> to illustrate the Visitor pattern.  We
will use Visitor to define operations for computing the
inventory of materials and the total cost for a piece of equipment.
The <CODE>Equipment</CODE> classes are so simple that using Visitor
isn't really necessary, but they make it easy to see what's
involved in implementing the pattern.</P>

<A NAME="equipment"></A>
<P>Here again is the <CODE>Equipment</CODE> class from
<A HREF="pat4cfs-1.htm" tppabs="http://ultra/development/DesignPatterns/lowres/pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>.  We've augmented it with an
<CODE>Accept</CODE> operation to let it work with a visitor.</P>

<A NAME="auto1066"></A>
<PRE>
    class Equipment {
    public:
        virtual ~Equipment();
    
        const char* Name() { return _name; }
    
        virtual Watt Power();
        virtual Currency NetPrice();
        virtual Currency DiscountPrice();
    
        virtual void Accept(EquipmentVisitor&amp;);
    protected:
        Equipment(const char*);
    private:
        const char* _name;
    };
</PRE>

<A NAME="auto1067"></A>
<P>The <CODE>Equipment</CODE> operations return the attributes of a piece of
equipment, such as its power consumption and cost.  Subclasses redefine
these operations appropriately for specific types of equipment (e.g.,
a chassis, drives, and planar boards).</P>

<A NAME="auto1068"></A>
<P>The abstract class for all visitors of equipment has a virtual
function for each subclass of equipment, as shown next.  All of the
virtual functions do nothing by default.</P>

<A NAME="equip-visit"></A>
<PRE>
    class EquipmentVisitor {
    public:
        virtual ~EquipmentVisitor();
    
        virtual void VisitFloppyDisk(FloppyDisk*);