Double dispatch
Double dispatch is a technique in object-oriented programming (OOP) that enables the selection and execution of a method based on the runtime types of two objects involved in an operation, extending the standard single-dispatch mechanism where method selection depends solely on the receiver object's type.[1] This approach simulates limited multiple dispatch in languages that natively support only single dispatch, such as Java or C++, by chaining two method calls: the first dispatches on the receiver's type, and the second on the argument's type.[2] For instance, in handling binary arithmetic operations like addition between an Integer and a Float, the Integer object might invoke a type-specific method on the Float (e.g., sumFromInteger:), ensuring the correct behavior for that type pair without relying on runtime type checks.[1]
Originating in dynamically typed languages like Smalltalk, double dispatch addresses challenges in extending operations across class hierarchies without violating the open-closed principle, which advocates for software entities open to extension but closed to modification.[3] It is prominently featured in the Visitor design pattern, one of the 23 patterns outlined in the seminal Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, where it allows operations on object structures (e.g., abstract syntax trees) to be defined externally to the elements being visited, facilitating clean separation of concerns.[4] In practice, double dispatch is essential for scenarios involving polymorphic interactions, such as geometric computations (e.g., intersection between shapes) or UI component rendering, where the outcome depends on the combined types of interacting entities.[5]
While powerful for maintaining extensibility in single-dispatch environments, double dispatch requires careful implementation to avoid code duplication across classes; for each new type added to one hierarchy, corresponding methods must be defined in the other, potentially leading to a combinatorial explosion in larger systems.[2] Languages supporting native multiple dispatch, like Common Lisp or Julia, render double dispatch unnecessary by directly selecting methods based on all argument types at runtime.[2] Nonetheless, its elegance in bridging polymorphism gaps continues to influence modern OOP practices, including in frameworks for dependency injection and event handling.[5]
Overview
Definition
Double dispatch is a technique in object-oriented programming that selects the appropriate method implementation based on the runtime types of two arguments, rather than just one as in single dispatch. This mechanism allows for more flexible polymorphism by considering the dynamic types of both the receiver (typically the object on which the method is called) and the argument passed to it, enabling behavior that adapts to interactions between different object types.[6]
Key characteristics of double dispatch include its reliance on multiple parameters for polymorphic resolution, often implemented through method delegation—where the first dispatch selects a method based on the receiver's type, and the second dispatch occurs within that method based on the argument's type—or via explicit runtime type checks. This approach is particularly useful in languages with single-dispatch semantics, such as Java or C++, to simulate multi-argument polymorphism without native support.[7][8]
Unlike multiple dispatch, which generalizes the concept to select methods based on the runtime types of any number of arguments, double dispatch is limited to exactly two arguments, making it a specific instance of the broader multiple dispatch paradigm.[8]
The following pseudocode illustrates a simple double dispatch scenario for calculating the area of shapes in different contexts, such as rendering or analysis, where the dispatch depends on both the shape type and the context type:
abstract class Shape {
abstract double area(Context ctx);
}
class Circle extends Shape {
private double radius;
double area(Context ctx) {
return ctx.computeCircleArea(this);
}
}
class Rectangle extends Shape {
private double width, height;
double area(Context ctx) {
return ctx.computeRectangleArea(this);
}
}
abstract class Context {
abstract double computeCircleArea([Circle](/page/Circle) c);
abstract double computeRectangleArea([Rectangle](/page/Rectangle) r);
}
class RenderingContext extends Context {
double computeCircleArea([Circle](/page/Circle) c) {
return Math.PI * c.[radius](/page/Radius) * c.[radius](/page/Radius); // Standard area
}
double computeRectangleArea([Rectangle](/page/Rectangle) r) {
return r.width * r.[height](/page/Height); // Standard area
}
}
class AnalysisContext extends Context {
double computeCircleArea(Circle c) {
return Math.PI * c.radius * c.radius * 1.1; // Adjusted for analysis
}
double computeRectangleArea(Rectangle r) {
return r.width * r.height * 1.1; // Adjusted for analysis
}
}
abstract class Shape {
abstract double area(Context ctx);
}
class Circle extends Shape {
private double radius;
double area(Context ctx) {
return ctx.computeCircleArea(this);
}
}
class Rectangle extends Shape {
private double width, height;
double area(Context ctx) {
return ctx.computeRectangleArea(this);
}
}
abstract class Context {
abstract double computeCircleArea([Circle](/page/Circle) c);
abstract double computeRectangleArea([Rectangle](/page/Rectangle) r);
}
class RenderingContext extends Context {
double computeCircleArea([Circle](/page/Circle) c) {
return Math.PI * c.[radius](/page/Radius) * c.[radius](/page/Radius); // Standard area
}
double computeRectangleArea([Rectangle](/page/Rectangle) r) {
return r.width * r.[height](/page/Height); // Standard area
}
}
class AnalysisContext extends Context {
double computeCircleArea(Circle c) {
return Math.PI * c.radius * c.radius * 1.1; // Adjusted for analysis
}
double computeRectangleArea(Rectangle r) {
return r.width * r.height * 1.1; // Adjusted for analysis
}
}
In this example, calling shape.area(new [RenderingContext](/page/RenderingContext)()) dispatches first on the Shape type to invoke area, which then dispatches on the [Context](/page/Context) type to select the specific area computation method.[7]
Historical Development
The concept of double dispatch emerged in the late 1980s within early object-oriented programming languages, particularly Smalltalk, where it addressed the need for polymorphic operations involving multiple argument types, such as arithmetic expressions. Dan Ingalls introduced the technique in 1986, describing it as "multiple polymorphism" and demonstrating its use for handling operations like addition between different number types in Smalltalk-80, enabling more flexible and extensible code without relying solely on single dispatch.[9] Concurrently, the Lisp community advanced related ideas through the development of multiple dispatch mechanisms. Daniel G. Bobrow and colleagues pioneered this in CommonLoops (1983–1986) and formalized it in the Common Lisp Object System (CLOS) specification of 1988, where generic functions dispatch based on the types of multiple arguments, influencing subsequent implementations of double dispatch in dynamic languages.[10]
In the 1990s, as object-oriented programming matured and static languages like C++ gained prominence, double dispatch was adapted through design patterns to compensate for the lack of native multiple dispatch support. The influential book Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides (1994)—often called the "Gang of Four" book—popularized the Visitor pattern, which employs double dispatch to perform operations across class hierarchies without modifying existing classes, marking a key milestone in its adoption for C++ and similar languages. In Eiffel, developed by Bertrand Meyer during the same period, agent-based approaches and polymorphic routines were explored to simulate double dispatch, allowing decoupled interactions in statically typed environments while leveraging Eiffel's contract-based design principles.
By the early 2000s, double dispatch via the Visitor pattern had integrated into mainstream libraries and frameworks for Java and C++, such as tree traversal utilities and compiler components, establishing it as a standard tool for extensible designs in enterprise software. An empirical study in 2008 highlighted its practical use alongside alternatives like full multiple dispatch in languages such as CLOS, underscoring its enduring role in single-dispatch systems.[8] Post-2010, the technique stabilized as a mature pattern, with no substantial innovations altering its core principles, though native multiple dispatch in newer languages like Julia built upon its foundational ideas without supplanting double dispatch in legacy OOP contexts.[8]
Dispatch Mechanisms in OOP
Single Dispatch
Single dispatch is the standard method resolution mechanism in most object-oriented programming languages, where the implementation of a method call is determined at runtime based solely on the dynamic type of the receiver object, also known as the target or 'this/self' argument. This enables runtime polymorphism, allowing subclasses to provide specialized implementations of methods declared in their superclasses without altering the calling code. It forms the foundation of dynamic binding in languages like Java, C++, and Python, where method selection depends only on the receiver's type, not on the types of other arguments.[8]
The process operates through dynamic binding. In statically typed languages such as C++ and Java, this is commonly implemented using virtual method tables (vtables), which are data structures associated with each class in the inheritance hierarchy. A vtable is an array of pointers to the virtual functions for that class; each object contains a hidden pointer (vptr) to its class's vtable. Upon invocation of a virtual method, the runtime system uses the object's vptr to access the vtable and selects the function pointer corresponding to the method's offset, ensuring the correct overridden implementation is executed based on the object's actual runtime type. This mechanism supports efficient subtype polymorphism while resolving calls late, typically with a constant-time lookup cost.[11]
Consider a basic pseudocode example illustrating single dispatch in an inheritance hierarchy for drawing shapes:
[class](/page/Class) Shape {
[virtual](/page/Virtual) [method](/page/Method) [draw](/page/Draw!)() {
// [Generic](/page/Generic) shape drawing
}
}
[class](/page/Class) Circle extends Shape {
override [method](/page/Method) [draw](/page/Draw!)() {
// Specific circle drawing logic
}
}
Shape s = new Circle();
s.[draw](/page/Draw!)(); // Resolves to Circle's draw() at runtime via vtable lookup
[class](/page/Class) Shape {
[virtual](/page/Virtual) [method](/page/Method) [draw](/page/Draw!)() {
// [Generic](/page/Generic) shape drawing
}
}
[class](/page/Class) Circle extends Shape {
override [method](/page/Method) [draw](/page/Draw!)() {
// Specific circle drawing logic
}
}
Shape s = new Circle();
s.[draw](/page/Draw!)(); // Resolves to Circle's draw() at runtime via vtable lookup
In this setup, the call to draw() on the Shape reference dispatches to the Circle implementation because the receiver's dynamic type is Circle, demonstrating how single dispatch achieves polymorphic behavior without compile-time knowledge of the exact type.[8]
A key limitation of single dispatch arises when method behavior needs to vary based on the types of multiple arguments, such as in binary operations like shape intersection (e.g., determining how a circle and rectangle interact). Since dispatch considers only the receiver's type, it cannot automatically select implementations polymorphic on argument types, often requiring manual type checks (e.g., conditional statements) or auxiliary mechanisms, which can result in brittle, less extensible code that duplicates logic across classes.[12]
Double Dispatch
Double dispatch extends the single-dispatch mechanism of object-oriented programming, which selects a method based solely on the runtime type of the receiver, by incorporating the runtime type of an additional argument to determine the appropriate method implementation.[8] This enables polymorphic behavior dependent on the dynamic types of two objects, resolving limitations in scenarios requiring interactions between hierarchies.[13]
The core technique employs a double-dispatch idiom: the first object (the receiver) calls a delegating method on the second object (the argument), passing a reference to itself; the second object then invokes a callback method whose implementation is selected based on the type of the first object.[14] This creates a chain of delegations that achieves the dual-type resolution without native multiple-dispatch support. Implementation strategies vary, including delegation chains via virtual method calls for runtime polymorphism, explicit accept/visit method pairs to structure the dispatch explicitly, or runtime type identification (RTTI) for explicit type querying and casting in languages lacking built-in multimethods.[8][14]
A generic pseudocode illustration of this setup, using abstract classes and interfaces for the dispatch hierarchy, is as follows:
pseudocode
// Abstract base for elements
abstract class Element {
abstract accept(Visitor v);
}
// Concrete element subclass
class ConcreteElement extends Element {
void accept(Visitor v) {
v.visitConcreteElement(this);
}
}
// Visitor interface with type-specific methods
interface Visitor {
void visitConcreteElement(Element e);
// Overloads for other concrete types
}
// Concrete visitor implementation
class ConcreteVisitor implements Visitor {
void visitConcreteElement(Element e) {
// Type-specific operation based on e's runtime type and visitor's behavior
}
}
// Usage: Triggers double dispatch
Element elem = new ConcreteElement();
Visitor vis = new ConcreteVisitor();
elem.accept(vis); // Dispatches to vis.visitConcreteElement(elem)
// Abstract base for elements
abstract class Element {
abstract accept(Visitor v);
}
// Concrete element subclass
class ConcreteElement extends Element {
void accept(Visitor v) {
v.visitConcreteElement(this);
}
}
// Visitor interface with type-specific methods
interface Visitor {
void visitConcreteElement(Element e);
// Overloads for other concrete types
}
// Concrete visitor implementation
class ConcreteVisitor implements Visitor {
void visitConcreteElement(Element e) {
// Type-specific operation based on e's runtime type and visitor's behavior
}
}
// Usage: Triggers double dispatch
Element elem = new ConcreteElement();
Visitor vis = new ConcreteVisitor();
elem.accept(vis); // Dispatches to vis.visitConcreteElement(elem)
In statically typed languages, ensuring type safety poses challenges, as implementations must rely on abstract base classes to define polymorphic interfaces and abstract methods to enforce overrides, preventing type errors at compile time while allowing runtime dispatch.[14] Without such structures, reliance on RTTI or reflection can introduce fragility and undermine static guarantees.[8]
Applications
Visitor Pattern
The Visitor pattern is a behavioral design pattern introduced in the seminal work by Gamma et al., where operations on elements of an object structure are separated from the objects themselves, allowing algorithms to be defined independently of the classes they manipulate.[15] It represents an operation to be performed on the elements of an object structure, enabling some other object—the visitor—to carry out the work without altering the classes of those elements.[15] This pattern leverages double dispatch to route the operation to the correct implementation based on both the type of the element and the type of the visitor.
In its structure, the pattern centers on an Element hierarchy, where each element class declares an accept(Visitor v) method that takes a visitor as an argument.[15] The Visitor interface defines a visit() operation for each concrete element type in the hierarchy, ensuring that visitors can handle all possible element variants.[15] ConcreteVisitor subclasses implement these visit() methods to provide specific behaviors tailored to each element type.[15] When an element invokes accept(v), it calls v.visit(this), dispatching control to the visitor's appropriate visit() method based on the element's concrete type, thus realizing the double dispatch.[15]
An ObjectStructure—such as a composite or collection—maintains the elements and provides traversal methods that invoke accept() on each element in turn.[15] ConcreteElement classes implement the accept() method by forwarding to the visitor, while Client code instantiates a concrete visitor and initiates traversal via the object structure.[15] Textually, the key participants can be represented as follows:
- Visitor:
visitConcreteElementA(elementA: ConcreteElementA); visitConcreteElementB(elementB: ConcreteElementB)
- ConcreteVisitor: Implements Visitor operations with specific logic
- Element:
accept(visitor: Visitor)
- ConcreteElementA:
accept(visitor: Visitor) { visitor.visitConcreteElementA(this) }
- ObjectStructure:
traverse(visitor: Visitor) { for each element in structure: element.accept(visitor) }
This arrangement ensures that new operations can be introduced by subclassing Visitor without modifying the Element classes, thereby conforming to the open-closed principle by being open for extension but closed for modification.[15]
Polymorphic Operations
Double dispatch enables polymorphic operations that depend on the runtime types of two objects, allowing the selection of appropriate behavior for interactions between elements of a class hierarchy without relying on explicit type checking. This technique is particularly useful in scenarios where binary operations must vary based on both operands, such as computing interactions between geometric entities or handling events between game objects.[16]
One common idiom is collision detection in game development, where double dispatch determines the specific algorithm for detecting overlaps between two polymorphic objects, such as a ball and a wall or two vehicles. For instance, when two shapes potentially collide, the first object's method invokes a type-specific handler on the second object, ensuring the correct collision resolution—such as elastic bounce for spheres or inelastic for rectangles—is applied dynamically. This approach avoids cascading if-else statements based on type tags, which can become unwieldy as the number of shape types grows.[17]
Another application arises in serialization processes, where double dispatch facilitates the customization of how objects of different types are persisted or transmitted. In Java's serialization framework, for example, an ObjectOutputStream dispatches to a type-specific writeObject method on the target object, allowing each class to define its own serialization logic while remaining decoupled from the stream's implementation. This supports efficient handling of type pairs, such as serializing a complex graph involving mixed object types, without requiring the serializer to know every possible class detail upfront.[18]
A representative scenario involves mathematical operations between shapes, such as computing the intersection of a circle and a rectangle. Double dispatch selects the optimal algorithm—perhaps an analytic solution for circle-rectangle overlaps versus numerical methods for more complex pairs—by first dispatching on the first shape's type and then on the second's, enabling precise area calculations or overlap visualizations in graphics applications. This method ensures extensibility: adding a new shape type, like a polygon, requires only implementing intersection handlers for existing types, without modifying unrelated code.[19][20]
The advantages of double dispatch in these polymorphic operations include cleaner, more maintainable code compared to type-switch cascades, which proliferate with hierarchy expansion and risk missing cases. It promotes extensibility for new type combinations, as each class can independently define its interactions, fostering open-closed principle adherence in object-oriented design.[19][17]
Double dispatch serves as a lightweight subset of multiple dispatch tailored to binary operations, where the latter generalizes to more arguments by selecting methods based on all involved types' runtime characteristics. While multiple dispatch natively supports this in languages like Common Lisp, double dispatch emulates it in single-dispatch environments for pairwise interactions, such as the binary collisions or intersections described.[16]
Examples
Ruby
Ruby's dynamic typing and object model facilitate double dispatch primarily through the visitor pattern, leveraging duck typing and runtime method resolution rather than explicit type declarations or virtual tables. This approach allows methods to be selected based on the types of two objects at runtime, using mechanisms like respond_to? for type checking or method_missing for fallback dispatching, though the visitor pattern provides a clean, idiomatic implementation without requiring library extensions.[21]
A representative example of double dispatch in Ruby involves rendering shapes with different colors, where the rendering behavior depends on both the shape type (e.g., circle or square) and the color type (e.g., red or blue). Here, shapes act as elements that accept color visitors, dispatching to specific methods in the visitor based on the shape's class. The following code demonstrates this using the visitor pattern:
ruby
# Abstract Shape (Element)
class Shape
def accept(color_visitor)
raise NotImplementedError, "#{self.class} must implement accept"
end
end
# Concrete Shapes
class Circle < Shape
def accept(color_visitor)
color_visitor.visit_circle(self)
end
def draw
"Drawing a circle"
end
end
class Square < Shape
def accept(color_visitor)
color_visitor.visit_square(self)
end
def draw
"Drawing a square"
end
end
# Abstract Color Visitor
class ColorVisitor
def visit_circle(_circle)
raise NotImplementedError, "#{self.class} must implement visit_circle"
end
def visit_square(_square)
raise NotImplementedError, "#{self.class} must implement visit_square"
end
end
# Concrete Color Visitors
class Red < ColorVisitor
def visit_circle(circle)
puts "#{circle.draw} in red (e.g., with red outline)"
end
def visit_square(square)
puts "#{square.draw} in red (e.g., filled red)"
end
end
class Blue < ColorVisitor
def visit_circle(circle)
puts "#{circle.draw} in blue (e.g., filled blue)"
end
def visit_square(square)
puts "#{square.draw} in blue (e.g., with blue outline)"
end
end
# Client code to demonstrate
shapes = [Circle.new, Square.new]
red = Red.new
blue = Blue.new
puts "Rendering with red:"
shapes.each { |shape| shape.accept(red) }
puts "\nRendering with blue:"
shapes.each { |shape| shape.accept(blue) }
# Abstract Shape (Element)
class Shape
def accept(color_visitor)
raise NotImplementedError, "#{self.class} must implement accept"
end
end
# Concrete Shapes
class Circle < Shape
def accept(color_visitor)
color_visitor.visit_circle(self)
end
def draw
"Drawing a circle"
end
end
class Square < Shape
def accept(color_visitor)
color_visitor.visit_square(self)
end
def draw
"Drawing a square"
end
end
# Abstract Color Visitor
class ColorVisitor
def visit_circle(_circle)
raise NotImplementedError, "#{self.class} must implement visit_circle"
end
def visit_square(_square)
raise NotImplementedError, "#{self.class} must implement visit_square"
end
end
# Concrete Color Visitors
class Red < ColorVisitor
def visit_circle(circle)
puts "#{circle.draw} in red (e.g., with red outline)"
end
def visit_square(square)
puts "#{square.draw} in red (e.g., filled red)"
end
end
class Blue < ColorVisitor
def visit_circle(circle)
puts "#{circle.draw} in blue (e.g., filled blue)"
end
def visit_square(square)
puts "#{square.draw} in blue (e.g., with blue outline)"
end
end
# Client code to demonstrate
shapes = [Circle.new, Square.new]
red = Red.new
blue = Blue.new
puts "Rendering with red:"
shapes.each { |shape| shape.accept(red) }
puts "\nRendering with blue:"
shapes.each { |shape| shape.accept(blue) }
This code outputs:
Rendering with red:
Drawing a circle in red (e.g., with red outline)
Drawing a square in red (e.g., filled red)
Rendering with blue:
Drawing a circle in blue (e.g., filled blue)
Drawing a square in blue (e.g., with blue outline)
Rendering with red:
Drawing a circle in red (e.g., with red outline)
Drawing a square in red (e.g., filled red)
Rendering with blue:
Drawing a circle in blue (e.g., filled blue)
Drawing a square in blue (e.g., with blue outline)
In execution, double dispatch occurs as follows: When shape.accept(color_visitor) is called, Ruby first dispatches to the accept method on the specific shape instance (single dispatch on shape type). Inside accept, the shape invokes a type-specific method on the visitor (e.g., visit_circle for a Circle), enabling the second dispatch based on the color visitor's class. This runtime resolution ensures the appropriate rendering logic is selected without conditional checks, relying on Ruby's dynamic method lookup.[21]
Ruby's open classes further simplify this pattern, allowing methods to be added or modified at runtime to extend dispatch behavior across hierarchies without recompilation, contrasting with the static commitments in languages requiring virtual tables. This flexibility makes double dispatch feel more natural in Ruby, often requiring fewer boilerplate elements.
C++
In C++, double dispatch is typically implemented using the Visitor pattern, which relies on abstract base classes featuring pure virtual accept() methods in the element hierarchy and corresponding visit() methods in the visitor interface. This setup simulates double dispatch by leveraging C++'s virtual function mechanism: the accept() call dispatches dynamically based on the runtime type of the element, which then invokes the type-specific visit() method on the visitor object.[7]
The following example demonstrates double dispatch for geometric shapes, where a DrawingVisitor performs rendering operations on Rectangle and Circle objects without modifying their classes. The element hierarchy includes an abstract Shape base class with a pure virtual accept(Visitor&) method. Concrete shapes implement accept() to call the appropriate visitShape() overload on the visitor, passing this. The Visitor base class declares pure virtual visitRectangle() and visitCircle() methods, implemented in DrawingVisitor to output simple drawing commands. This achieves double dispatch by resolving the operation based on both the shape's dynamic type and the visitor's static type.
To illustrate compile-time type safety, forward declarations are used in headers to resolve cyclic dependencies between the visitor and element classes, ensuring the compiler can verify types without full definitions initially.[4]
Shape.h
cpp
#ifndef SHAPE_H
#define SHAPE_H
class Visitor; // [Forward declaration](/page/Forward_declaration)
class Shape {
public:
virtual void accept(Visitor& v) = 0;
virtual ~Shape() = default;
};
#endif
#ifndef SHAPE_H
#define SHAPE_H
class Visitor; // [Forward declaration](/page/Forward_declaration)
class Shape {
public:
virtual void accept(Visitor& v) = 0;
virtual ~Shape() = default;
};
#endif
Rectangle.h
cpp
#ifndef RECTANGLE_H
#define RECTANGLE_H
#include "Shape.h"
#include <iostream>
class [Visitor](/page/Visitor); // Forward declaration
class Rectangle : [public](/page/Public) [Shape](/page/Shape) {
public:
void accept([Visitor](/page/Visitor)& v) override;
};
#endif
#ifndef RECTANGLE_H
#define RECTANGLE_H
#include "Shape.h"
#include <iostream>
class [Visitor](/page/Visitor); // Forward declaration
class Rectangle : [public](/page/Public) [Shape](/page/Shape) {
public:
void accept([Visitor](/page/Visitor)& v) override;
};
#endif
Circle.h
cpp
#ifndef CIRCLE_H
#define CIRCLE_H
#include "Shape.h"
#include <iostream>
class [Visitor](/page/Visitor); // Forward declaration
class Circle : [public](/page/Public) [Shape](/page/Shape) {
public:
void accept([Visitor](/page/Visitor)& v) override;
};
#endif
#ifndef CIRCLE_H
#define CIRCLE_H
#include "Shape.h"
#include <iostream>
class [Visitor](/page/Visitor); // Forward declaration
class Circle : [public](/page/Public) [Shape](/page/Shape) {
public:
void accept([Visitor](/page/Visitor)& v) override;
};
#endif
Visitor.h
cpp
#ifndef VISITOR_H
#define VISITOR_H
class Shape;
class Rectangle;
class Circle; // Forward declarations
class Visitor {
public:
virtual void visitRectangle(Rectangle& r) = 0;
virtual void visitCircle([Circle](/page/Circle)& c) = 0;
virtual ~Visitor() = default;
};
#endif
#ifndef VISITOR_H
#define VISITOR_H
class Shape;
class Rectangle;
class Circle; // Forward declarations
class Visitor {
public:
virtual void visitRectangle(Rectangle& r) = 0;
virtual void visitCircle([Circle](/page/Circle)& c) = 0;
virtual ~Visitor() = default;
};
#endif
Rectangle.cpp
cpp
#include "Rectangle.h"
#include "Visitor.h"
void Rectangle::accept(Visitor& v) {
v.visitRectangle(*this);
}
#include "Rectangle.h"
#include "Visitor.h"
void Rectangle::accept(Visitor& v) {
v.visitRectangle(*this);
}
Circle.cpp
cpp
#include "Circle.h"
#include "Visitor.h"
void Circle::accept(Visitor& v) {
v.visitCircle(*this);
}
#include "Circle.h"
#include "Visitor.h"
void Circle::accept(Visitor& v) {
v.visitCircle(*this);
}
DrawingVisitor.h
cpp
#ifndef DRAWINGVISITOR_H
#define DRAWINGVISITOR_H
#include "Visitor.h"
#include <iostream>
class [Rectangle](/page/Rectangle);
class [Circle](/page/Circle);
class [DrawingVisitor](/page/Visitor) : [public](/page/Public) [Visitor](/page/Visitor) {
public:
void visitRectangle([Rectangle](/page/Rectangle)& r) override {
std::cout << "Drawing a [rectangle](/page/Rectangle)." << std::endl;
}
void visitCircle([Circle](/page/Circle)& c) override {
std::cout << "Drawing a [circle](/page/Circle)." << std::endl;
}
};
#endif
#ifndef DRAWINGVISITOR_H
#define DRAWINGVISITOR_H
#include "Visitor.h"
#include <iostream>
class [Rectangle](/page/Rectangle);
class [Circle](/page/Circle);
class [DrawingVisitor](/page/Visitor) : [public](/page/Public) [Visitor](/page/Visitor) {
public:
void visitRectangle([Rectangle](/page/Rectangle)& r) override {
std::cout << "Drawing a [rectangle](/page/Rectangle)." << std::endl;
}
void visitCircle([Circle](/page/Circle)& c) override {
std::cout << "Drawing a [circle](/page/Circle)." << std::endl;
}
};
#endif
main.cpp
cpp
#include "[Rectangle](/page/Rectangle).h"
#include "[Circle](/page/Circle).h"
#include "[DrawingVisitor](/page/Visitor).h"
#include <vector>
int main() {
std::vector<Shape*> shapes;
shapes.push_back(new [Rectangle](/page/Rectangle)());
shapes.push_back(new [Circle](/page/Circle)());
DrawingVisitor drawer;
for ([Shape](/page/Shape)* shape : shapes) {
shape->accept(drawer);
}
// Cleanup
for ([Shape](/page/Shape)* shape : shapes) {
delete shape;
}
return 0;
}
#include "[Rectangle](/page/Rectangle).h"
#include "[Circle](/page/Circle).h"
#include "[DrawingVisitor](/page/Visitor).h"
#include <vector>
int main() {
std::vector<Shape*> shapes;
shapes.push_back(new [Rectangle](/page/Rectangle)());
shapes.push_back(new [Circle](/page/Circle)());
DrawingVisitor drawer;
for ([Shape](/page/Shape)* shape : shapes) {
shape->accept(drawer);
}
// Cleanup
for ([Shape](/page/Shape)* shape : shapes) {
delete shape;
}
return 0;
}
When executed, this program outputs:
Drawing a rectangle.
Drawing a circle.
Drawing a rectangle.
Drawing a circle.
The double dispatch mechanism relies on C++'s virtual function tables (vtables): each concrete shape class has a vtable entry for accept(), which the runtime uses to invoke the correct overridden accept() based on the object's dynamic type during the initial call (e.g., shape->accept(drawer)). This resolves to the specific visitXXX(*this) call, enabling the visitor to handle the element type polymorphically without relying on run-time type information (RTTI), as the dispatch chain uses only virtual calls and overload resolution.[7][22]
A unique challenge in C++ arises from its static typing, which enforces strict compile-time checks and can lead to header cyclic dependencies between visitors and elements; forward declarations mitigate this by allowing incomplete types for parameter passing in virtual methods, preserving type safety without requiring mutual includes.[4]
C#
In C#, double dispatch is commonly implemented using the Visitor pattern, which leverages interfaces to define the element hierarchy and visitor operations, enabling runtime selection of methods based on the types of both the element and the visitor. This approach relies on C#'s support for virtual methods and interface implementations, where the Accept method in elements calls the appropriate Visit overload in the visitor, achieving the second level of polymorphism. Unlike C++, C# emphasizes interfaces (e.g., IVisitor and IElement) for loose coupling and explicit interface implementation to avoid boilerplate in base classes.[23]
A representative example demonstrates double dispatch in a file system context, where elements like File and Directory accept a PrintVisitor to perform type-specific printing operations. The following complete code uses .NET interfaces and virtual methods to traverse and print a simple directory structure.
csharp
using System;
using System.Collections.Generic;
// Interface for elements in the hierarchy
public interface IElement
{
void Accept(IVisitor visitor);
}
// Concrete element: File
public class File : IElement
{
public string Name { get; }
public long Size { get; }
public File(string name, long size)
{
Name = name;
Size = size;
}
public void Accept(IVisitor visitor)
{
visitor.Visit(this);
}
}
// Concrete element: Directory, which can contain other elements
public class Directory : IElement
{
public string Name { get; }
private List<IElement> Children { get; } = new List<IElement>();
public Directory(string name)
{
Name = name;
}
public void Add(IElement element)
{
Children.Add(element);
}
public void Accept(IVisitor visitor)
{
visitor.Visit(this);
foreach (var child in Children)
{
child.Accept(visitor);
}
}
}
// Interface for visitors
public interface IVisitor
{
void Visit(File file);
void Visit(Directory directory);
}
// Concrete visitor: Prints elements with type-specific formatting
public class PrintVisitor : IVisitor
{
public void Visit(File file)
{
Console.WriteLine($"File: {file.Name}, Size: {file.Size} bytes");
}
public void Visit(Directory directory)
{
Console.WriteLine($"Directory: {directory.Name}");
}
}
// Usage example
class Program
{
static void Main()
{
var root = new Directory("Root");
root.Add(new File("document.txt", 1024));
root.Add(new Directory("Subfolder"));
root.Add(new File("image.jpg", 2048));
var printVisitor = new PrintVisitor();
root.Accept(printVisitor);
}
}
using System;
using System.Collections.Generic;
// Interface for elements in the hierarchy
public interface IElement
{
void Accept(IVisitor visitor);
}
// Concrete element: File
public class File : IElement
{
public string Name { get; }
public long Size { get; }
public File(string name, long size)
{
Name = name;
Size = size;
}
public void Accept(IVisitor visitor)
{
visitor.Visit(this);
}
}
// Concrete element: Directory, which can contain other elements
public class Directory : IElement
{
public string Name { get; }
private List<IElement> Children { get; } = new List<IElement>();
public Directory(string name)
{
Name = name;
}
public void Add(IElement element)
{
Children.Add(element);
}
public void Accept(IVisitor visitor)
{
visitor.Visit(this);
foreach (var child in Children)
{
child.Accept(visitor);
}
}
}
// Interface for visitors
public interface IVisitor
{
void Visit(File file);
void Visit(Directory directory);
}
// Concrete visitor: Prints elements with type-specific formatting
public class PrintVisitor : IVisitor
{
public void Visit(File file)
{
Console.WriteLine($"File: {file.Name}, Size: {file.Size} bytes");
}
public void Visit(Directory directory)
{
Console.WriteLine($"Directory: {directory.Name}");
}
}
// Usage example
class Program
{
static void Main()
{
var root = new Directory("Root");
root.Add(new File("document.txt", 1024));
root.Add(new Directory("Subfolder"));
root.Add(new File("image.jpg", 2048));
var printVisitor = new PrintVisitor();
root.Accept(printVisitor);
}
}
When executed, this code produces output demonstrating double dispatch: the Accept call on a Directory invokes Visit(Directory), which prints the directory name and recursively dispatches to children, while File instances trigger Visit(File) for size-aware printing. The result is:
Directory: Root
File: document.txt, Size: 1024 bytes
Directory: Subfolder
File: image.jpg, Size: 2048 bytes
Directory: Root
File: document.txt, Size: 1024 bytes
Directory: Subfolder
File: image.jpg, Size: 2048 bytes
C#'s type system resolves virtual method calls at runtime via the virtual method table (vtable), ensuring dispatch based on the actual object types during the Accept invocation, which supports the double dispatch mechanism without compile-time type knowledge of the visitor. Garbage collection in the .NET runtime manages object lifetimes automatically, preventing dangling references during dispatch and allowing safe polymorphic operations across managed heaps, though it introduces minor overhead from generational collection pauses that do not directly alter dispatch logic.
For simpler cases, the dynamic keyword in C# 4.0 and later enables double dispatch by deferring method resolution to runtime, binding based on argument types without explicit hierarchies, as seen in currency conversion scenarios where operations like USDToEUR are selected dynamically. This avoids the Visitor pattern's structure but sacrifices compile-time safety.[24]
Unique to C#, the Visitor pattern integrates with LINQ for querying element collections (e.g., selecting directories via Where(e => e is Directory)) or delegates for flexible visitor composition, allowing lambda-based operations like Action<IElement> to extend dispatch without subclassing.
Eiffel
Eiffel implements double dispatch through its external dispatch mechanism, which extends single dispatch to multiple arguments via creation procedures on deferred classes. This approach utilizes polymorphism inherent in deferred classes—abstract classes that define interfaces without full implementations—and routines as agents to enable dynamic selection of effective routines based on the runtime types of multiple objects. Unlike languages requiring runtime type identification, Eiffel's static type system resolves the dispatch at compile time for type safety.[25]
A classic illustration of double dispatch in Eiffel involves simulating collisions in a space game, such as between spaceships and asteroids. The design defines a base deferred class for moving objects and a deferred external dispatch class for collisions, with effective subclasses providing type-specific behaviors. This setup allows modular extension: new object types can be added by inheriting from the base and defining corresponding collision handlers without altering existing code.
eiffel
-- Base deferred class for moving objects
deferred class MOVING_OBJECT
feature
x, y: REAL_64
-- Position attributes
move(dx, dy: REAL_64)
-- Update position
do
x := x + dx
y := y + dy
end
end
-- Effective class for spaceship
class SHIP
inherit
MOVING_OBJECT
feature
-- Ship-specific features, e.g., [thrust](/page/Thrust)
end
-- Effective class for asteroid
class ASTEROID
inherit
MOVING_OBJECT
feature
-- Asteroid-specific features, e.g., spin
end
-- Deferred external dispatch class for collisions
deferred class COLLISION(o1, o2: MOVING_OBJECT)
create
make
feature {NONE}
make(a_o1, a_o2: like o1)
-- Creation procedure for dispatch
require
valid_objects: a_o1 /= Void and a_o2 /= Void
do
o1 := a_o1
o2 := a_o2
ensure
objects_set: o1 = a_o1 and o2 = a_o2
end
feature
outcome: [STRING](/page/STRING)
-- Type-specific collision result
deferred
require
objects_valid: o1 /= Void and o2 /= Void
ensure
result_not_void: Result /= Void
end
end
-- Effective class for ship-asteroid collision
[class](/page/Class) SHIP_ASTEROID_COLLISION
inherit
COLLISION
create
make
[feature](/page/Feature) {NONE}
make(a_ship: SHIP; a_asteroid: [ASTEROID](/page/Asteroid))
do
Precursor(a_ship, a_asteroid)
end
[feature](/page/Feature)
outcome: [STRING](/page/String)
do
Result := "The ship is destroyed by the asteroid."
end
end
-- Additional effective classes for other combinations (e.g., SHIP_SHIP_COLLISION, ASTEROID_ASTEROID_COLLISION)
-- would be defined similarly for full coverage.
-- Base deferred class for moving objects
deferred class MOVING_OBJECT
feature
x, y: REAL_64
-- Position attributes
move(dx, dy: REAL_64)
-- Update position
do
x := x + dx
y := y + dy
end
end
-- Effective class for spaceship
class SHIP
inherit
MOVING_OBJECT
feature
-- Ship-specific features, e.g., [thrust](/page/Thrust)
end
-- Effective class for asteroid
class ASTEROID
inherit
MOVING_OBJECT
feature
-- Asteroid-specific features, e.g., spin
end
-- Deferred external dispatch class for collisions
deferred class COLLISION(o1, o2: MOVING_OBJECT)
create
make
feature {NONE}
make(a_o1, a_o2: like o1)
-- Creation procedure for dispatch
require
valid_objects: a_o1 /= Void and a_o2 /= Void
do
o1 := a_o1
o2 := a_o2
ensure
objects_set: o1 = a_o1 and o2 = a_o2
end
feature
outcome: [STRING](/page/STRING)
-- Type-specific collision result
deferred
require
objects_valid: o1 /= Void and o2 /= Void
ensure
result_not_void: Result /= Void
end
end
-- Effective class for ship-asteroid collision
[class](/page/Class) SHIP_ASTEROID_COLLISION
inherit
COLLISION
create
make
[feature](/page/Feature) {NONE}
make(a_ship: SHIP; a_asteroid: [ASTEROID](/page/Asteroid))
do
Precursor(a_ship, a_asteroid)
end
[feature](/page/Feature)
outcome: [STRING](/page/String)
do
Result := "The ship is destroyed by the asteroid."
end
end
-- Additional effective classes for other combinations (e.g., SHIP_SHIP_COLLISION, ASTEROID_ASTEROID_COLLISION)
-- would be defined similarly for full coverage.
To simulate a collision, the following setup creates instances and invokes the dispatched routine:
eiffel
-- Simulation setup
local
ship: SHIP
asteroid: ASTEROID
collision: COLLISION
do
create ship
create asteroid
ship.move(1.0, 2.0) -- Position ship
asteroid.move(1.0, 2.0) -- Position asteroid at same location
create collision.make(ship, asteroid) -- Dispatches to SHIP_ASTEROID_COLLISION
io.put_string(collision.outcome)
-- Output: The ship is destroyed by the asteroid.
end
-- Simulation setup
local
ship: SHIP
asteroid: ASTEROID
collision: COLLISION
do
create ship
create asteroid
ship.move(1.0, 2.0) -- Position ship
asteroid.move(1.0, 2.0) -- Position asteroid at same location
create collision.make(ship, asteroid) -- Dispatches to SHIP_ASTEROID_COLLISION
io.put_string(collision.outcome)
-- Output: The ship is destroyed by the asteroid.
end
In this example, the external dispatch on the make creation procedure selects the appropriate effective class (e.g., SHIP_ASTEROID_COLLISION) based on the actual types of o1 and o2, enabling the polymorphic call to outcome. Eiffel's Design by Contract integrates seamlessly, enforcing preconditions (e.g., non-null objects) and postconditions (e.g., non-void results) across the dispatch hierarchy to ensure reliable behavior and catch violations at runtime if assertions are enabled. This static resolution eliminates the need for runtime type information (RTTI), avoiding dynamic casts and potential exceptions.[25][26]
The mechanism's emphasis on reusability stems from its support for open extension: adding a new moving object type requires only new effective collision classes, preserving the purity of the original hierarchy. Its provability aligns with Eiffel's object-oriented principles, as the type-safe dispatch and contract verification facilitate formal proofs of correctness, making it ideal for safety-critical applications. This fits Eiffel's paradigm of disciplined, verifiable software construction, as advocated by its designer.[25][27]