Visitor Pattern

  • Description: Separate an algorithm from the object structure it operates on by double dispatch — each element accepts a visitor and calls back the visit method matching its concrete type; lets you add operations without modifying the elements.
  • My Notion Note ID: K2C-2-22
  • Created: 2026-05-22
  • Updated: 2026-05-22
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Why It Exists

  • OO single-dispatch resolves only on the receiver's runtime type. node->print() works; print(node) for an arbitrary Node* doesn't pick a derived overload.
  • Visitor encodes double dispatch in two single-dispatch hops: node->accept(visitor) (dispatches on node type) → visitor->visit(SpecificNode&) (dispatches on visitor's overload set).
  • Decision axis: adding new operations vs adding new node types.
    • Inheritance with virtual methods on the node: easy to add nodes, hard to add operations (touch every node).
    • Visitor: easy to add operations (new visitor class), hard to add nodes (touch every visitor).
  • Used heavily in compilers / AST processing, IR transforms, document tree analysis, geometry-kernel queries.

2. Structure

  • Visitor (interface) — one visit(ConcreteElementX&) overload per concrete element type.
  • ConcreteVisitor — implements visit overloads for one operation (print, eval, type-check, ...).
  • Element (interface) — declares accept(Visitor&).
  • ConcreteElement — implements accept as v.visit(*this); (the only place where its concrete type is known statically).
  • ObjectStructure — composite of elements; iterates and calls accept on each.

3. Classic C++ Example

AST for a tiny expression language:

#include <memory>
#include <iostream>
#include <vector>

class IntLit;
class Add;
class Neg;

struct Visitor {
    virtual ~Visitor() = default;
    virtual void visit(IntLit&) = 0;
    virtual void visit(Add&)    = 0;
    virtual void visit(Neg&)    = 0;
};

struct Expr {
    virtual ~Expr() = default;
    virtual void accept(Visitor& v) = 0;
};

struct IntLit : Expr {
    int value;
    explicit IntLit(int v) : value(v) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

struct Add : Expr {
    std::unique_ptr<Expr> lhs, rhs;
    Add(std::unique_ptr<Expr> l, std::unique_ptr<Expr> r) : lhs(std::move(l)), rhs(std::move(r)) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

struct Neg : Expr {
    std::unique_ptr<Expr> e;
    explicit Neg(std::unique_ptr<Expr> x) : e(std::move(x)) {}
    void accept(Visitor& v) override { v.visit(*this); }
};

// Operation 1: pretty-print
struct Printer : Visitor {
    void visit(IntLit& n) override { std::cout << n.value; }
    void visit(Add& n)    override { std::cout << "("; n.lhs->accept(*this); std::cout << " + "; n.rhs->accept(*this); std::cout << ")"; }
    void visit(Neg& n)    override { std::cout << "-"; n.e->accept(*this); }
};

// Operation 2: eval — would require a separate visitor with a result field
struct Evaluator : Visitor {
    int result = 0;
    void visit(IntLit& n) override { result = n.value; }
    void visit(Add& n)    override { n.lhs->accept(*this); int l = result; n.rhs->accept(*this); result = l + result; }
    void visit(Neg& n)    override { n.e->accept(*this);  result = -result; }
};

Adding Mul: edit Visitor base + every concrete visitor. Adding a new operation: write TypeChecker : Visitor — no node edits.

4. Modern std::variant / std::visit

Closed set of node types → std::variant + std::visit is often a cleaner Visitor. No accept boilerplate, no virtual hierarchy, exhaustiveness via if constexpr or overload set:

#include <variant>
#include <memory>
#include <iostream>

struct IntLit;
struct Add;
struct Neg;
using ExprV = std::variant<IntLit, Add, Neg>;
using ExprPtr = std::unique_ptr<ExprV>;

struct IntLit { int value; };
struct Add    { ExprPtr lhs, rhs; };
struct Neg    { ExprPtr e; };

// Overload-set helper
template <class... Fs> struct overload : Fs... { using Fs::operator()...; };
template <class... Fs> overload(Fs...) -> overload<Fs...>;

int eval(const ExprV& e) {
    return std::visit(overload{
        [](const IntLit& n) { return n.value; },
        [&](const Add& n)   { return eval(*n.lhs) + eval(*n.rhs); },
        [&](const Neg& n)   { return -eval(*n.e); },
    }, e);
}

Trade-off:

  • Open vs closed — variant requires the full type list at compile time. Add a node = touch the variant declaration and every visitor (compiler enforces exhaustiveness, which is a feature).
  • No accept boilerplate — every node automatically participates.
  • Stack-allocated node objects; smaller for leaf-heavy trees.
  • Recursive types need unique_ptr<variant<...>> indirection (variants must have known size).

For an AST with a fixed grammar, variant is usually the better default in modern C++. Classic Visitor still wins when the node set must be open to clients.

5. When to Use / When Not To

Use when:

  • Object structure is stable (rare new node types) but operations grow over time.
  • Operations span multiple node types and don't belong on the nodes themselves.
  • You need double dispatch and the language doesn't natively support multimethods.

Avoid when:

  • Node types are added frequently — every visitor breaks.
  • There's only one operation per node — put the method on the node.
  • The node set is closed and known at compile time — prefer std::variant + std::visit.

6. Variants and Pitfalls

  • Default visit for new nodes — provide a non-pure base with a default (e.g., assert, log, no-op) so adding a node doesn't break every visitor at once. Trade-off: weakens compile-time check.
  • Returning a value — visit typically returns void in classic form. Workarounds: visitor holds a result member; template visitor returning R; or use std::variant/std::visit which natively returns the common type.
  • Acyclic Visitor (Martin) — avoids the cyclic dependency between visitor base and every node by using dynamic_cast inside accept. Slower, breaks compile-time exhaustiveness; rarely worth it.
  • Visitor + const-correctness — separate Visitor and ConstVisitor hierarchies; otherwise one or the other is awkward.
  • Mutation during traversal — visiting and modifying a tree concurrently is a footgun. Either gather changes and apply after, or define traversal order explicitly.
  • Performance — two virtual calls per node (accept + visit). std::variant collapses to one switch on the discriminator.

7. Related Patterns

  • Modern alternative — std::variant + std::visit — sum type + structural pattern match; see § 4. For closed AST-style hierarchies in modern C++ this is often the right default, not classic Visitor.
  • Double dispatch — Visitor is the textbook OO emulation. Languages with multimethods (CLOS, Julia, Dylan) don't need the pattern.
  • Iterator — orthogonal; combine to walk a structure and visit each element.
  • Composite — Visitor traverses a Composite. The AST in the example IS a Composite; Visitor adds operations without bloating the node interface.
  • Interpreter — Visitor is the standard way to add operations (eval, print, type-check) to an Interpreter's AST.

8. References