What is Double Dispatch in C++?

Resolve a function call based on the runtime types of two objects, extending C++ virtual dispatch from one dimension to two.

What is the difficulty level of Double Dispatch?

Double Dispatch is considered Advanced-level C++ material.

Double Dispatch

Double Dispatchsince C++98

A technique that selects the concrete function to invoke based on the runtime types of two objects simultaneously, where a single virtual call on one object is insufficient to fully resolve the intended behaviour.

Overview

C++ virtual dispatch is single dispatch: a call to shape->draw() resolves to the correct override based on the runtime type of the one object pointed to by shape. The moment you need resolution on two objects, the language gives you nothing out of the box.

The canonical example is collision detection. collide(a, b) must behave differently for Circle–Circle, Circle–Rectangle, and Rectangle–Rectangle. A virtual call on a can branch on a's concrete type, but the resulting code still receives Shape& b — a pointer of static type, not concrete type. The second dimension is unresolved.

Three strategies address this problem with very different trade-offs.

Strategy 1: Brute-Force dynamic_cast Chain

The most direct solution nests dynamic_cast lookups. Each level resolves one type.

cpp

Godbolt

#include <stdexcept>

struct Shape    { virtual ~Shape() = default; };
struct Circle    : Shape { double radius; };
struct Rectangle : Shape { double width, height; };

void circle_circle(Circle&, Circle&)       { /* ... */ }
void circle_rect(Circle&, Rectangle&)      { /* ... */ }
void rect_circle(Rectangle&, Circle&)      { /* ... */ }
void rect_rect(Rectangle&, Rectangle&)     { /* ... */ }

void collide(Shape& a, Shape& b) {
    // dynamic_cast to pointer: returns nullptr on failure, no exception
    if (auto* ca = dynamic_cast<Circle*>(&a)) {
        if (auto* cb = dynamic_cast<Circle*>(&b))    { circle_circle(*ca, *cb); return; }
        if (auto* rb = dynamic_cast<Rectangle*>(&b)) { circle_rect(*ca, *rb);   return; }
    }
    if (auto* ra = dynamic_cast<Rectangle*>(&a)) {
        if (auto* cb = dynamic_cast<Circle*>(&b))    { rect_circle(*ra, *cb);   return; }
        if (auto* rb = dynamic_cast<Rectangle*>(&b)) { rect_rect(*ra, *rb);     return; }
    }
    throw std::logic_error{"unknown shape combination"};
}

With N concrete types there are N² branches and N² leaf functions. Adding a new type means editing collide and writing N new leaf functions. Failed dynamic_cast probes burn CPU proportional to the position in the chain. Use this only when N ≤ 3 and the type set is truly frozen.

Strategy 2: Visitor Pattern (two virtual calls)

The Visitor pattern achieves double dispatch through two sequential virtual calls. The first accept call resolves the left-hand type; inside that dispatch, a second accept call resolves the right-hand type.

cpp

Godbolt

#include <iostream>

class Circle;
class Rectangle;

// Abstract visitor — knows every concrete shape type
struct ShapeVisitor {
    virtual void visit(Circle&)    = 0;
    virtual void visit(Rectangle&) = 0;
    virtual ~ShapeVisitor()        = default;
};

struct Shape {
    virtual void accept(ShapeVisitor&) = 0;
    virtual ~Shape()                   = default;
};

struct Circle : Shape {
    explicit Circle(double r) : radius{r} {}
    void accept(ShapeVisitor& v) override { v.visit(*this); } // resolves to visit(Circle&)
    double radius;
};

struct Rectangle : Shape {
    Rectangle(double w, double h) : width{w}, height{h} {}
    void accept(ShapeVisitor& v) override { v.visit(*this); } // resolves to visit(Rectangle&)
    double width, height;
};

// Inner visitors — LHS concrete type is baked in at construction
struct CircleCollider : ShapeVisitor {
    Circle& lhs;
    explicit CircleCollider(Circle& c) : lhs{c} {}
    void visit(Circle& rhs)    override { std::cout << "Circle vs Circle\n"; }
    void visit(Rectangle& rhs) override { std::cout << "Circle vs Rectangle\n"; }
};

struct RectangleCollider : ShapeVisitor {
    Rectangle& lhs;
    explicit RectangleCollider(Rectangle& r) : lhs{r} {}
    void visit(Circle& rhs)    override { std::cout << "Rectangle vs Circle\n"; }
    void visit(Rectangle& rhs) override { std::cout << "Rectangle vs Rectangle\n"; }
};

// Outer visitor — first dispatch selects inner visitor, then fires second dispatch
struct CollisionDispatcher : ShapeVisitor {
    Shape& rhs;
    explicit CollisionDispatcher(Shape& r) : rhs{r} {}

    void visit(Circle& lhs) override {
        CircleCollider inner{lhs};
        rhs.accept(inner);      // second virtual dispatch
    }
    void visit(Rectangle& lhs) override {
        RectangleCollider inner{lhs};
        rhs.accept(inner);      // second virtual dispatch
    }
};

void collide(Shape& a, Shape& b) {
    CollisionDispatcher d{b};
    a.accept(d);                // first virtual dispatch
}

The full dispatch chain: a.accept(d) → vtable → CollisionDispatcher::visit(Circle&) → construct CircleCollider → b.accept(inner) → vtable → CircleCollider::visit(Rectangle&). Two vtable lookups, one temporary object, no dynamic_cast.

Adding a Triangle type requires: a new class with accept, a new visit(Triangle&) overload in ShapeVisitor (which triggers a compile error on every existing concrete visitor that omits it), and a new inner collider. This forced-update property is a feature: you cannot add a type silently.

Strategy 3: std::variant + std::visit (C++17)

When the type set is closed and owned by you, std::variant eliminates runtime dispatch entirely. std::visit over two variants generates a compile-time jump table — no vtables, no heap, no dynamic_cast.

cpp

Godbolt

#include <variant>   // C++17
#include <iostream>

struct Circle    { double radius; };
struct Rectangle { double width, height; };

using Shape = std::variant<Circle, Rectangle>;  // C++17

// Fold over using-declarations — requires C++17
template<class... Ts>
struct overloads : Ts... { using Ts::operator()...; };

void collide(const Shape& a, const Shape& b) {
    std::visit([&b](const auto& lhs) {          // C++17
        std::visit([&lhs](const auto& rhs) {
            using L = std::decay_t<decltype(lhs)>;  // C++14 alias
            using R = std::decay_t<decltype(rhs)>;
            if constexpr (std::is_same_v<L, Circle> && std::is_same_v<R, Circle>) {        // C++17
                std::cout << "Circle vs Circle\n";
            } else if constexpr (std::is_same_v<L, Circle> && std::is_same_v<R, Rectangle>) {
                std::cout << "Circle vs Rectangle\n";
            } else if constexpr (std::is_same_v<L, Rectangle> && std::is_same_v<R, Circle>) {
                std::cout << "Rectangle vs Circle\n";
            } else {
                std::cout << "Rectangle vs Rectangle\n";
            }
        }, b);
    }, a);
}

// Symmetric variant: canonicalize pair so only N*(N+1)/2 cases need implementing
void collide_symmetric(Shape a, Shape b) {
    if (a.index() > b.index()) std::swap(a, b); // C++17: std::swap works on variants
    collide(a, b);
}

C++23 added variant::visit as a member function (var.visit(f)), which removes the need to repeat the variant name and composes more naturally with method chaining.

The optimizer can see through the entire dispatch and inline leaf handlers. Benchmarks consistently show the variant-based approach running 2–4× faster than the two-vtable Visitor for small type sets where the jump table fits in cache.

Best Practices

Match strategy to type-set openness. std::variant is optimal for closed sets you control. Visitor is the correct choice for open hierarchies where third-party code adds new types and you need compile-time enforcement that every visitor stays complete.

Keep inner visitors anonymous. In the Visitor strategy, CircleCollider and RectangleCollider are implementation details of CollisionDispatcher. Define them in an anonymous namespace or as private nested classes. Leaking them into a public header couples every translation unit to internal dispatch structure.

Enforce symmetry at the boundary, not inside handlers. If collide(A, B) ≡ collide(B, A), canonicalize by variant::index() or by a type-ordering trait before dispatch. Writing each case twice is a maintenance hazard; writing them once under a canonical ordering is not.

Never store a visitor by value in a hot loop. The Visitor strategy constructs a temporary CollisionDispatcher per call. If this appears inside a tight physics loop, hoist the dispatcher or switch to the variant strategy.

Common Pitfalls

Silently incomplete dynamic_cast chains. The brute-force approach falls through to throw for unknown pairs. In practice, the throw branch is often omitted, producing silent no-ops when a new type is added. Always cover the unhandled case explicitly.

Missing visit overloads evade the linker. If ShapeVisitor declares visit(Triangle&) = 0 but a concrete visitor omits it, you get a compile error — but only if that translation unit is compiled. With separate compilation and weak linkage configurations this can hide until link time on some platforms. Enable -Wall and use = 0 (pure virtual), not a default empty body.

Lifetime of the stored reference in CollisionDispatcher. The dispatcher stores Shape& rhs by reference. Constructing the dispatcher in one scope and firing it from another after rhs is destroyed is UB. Build and fire in the same full expression when the types allow it.

std::visit requires all branches to return the same type. If each branch returns a different unrelated type, the call fails to compile. Either return void, use a common base, or return std::variant of the possible return types.

Strategy 4: Type-Indexed Function Table (N-type open dispatch)

When the type set is not fully known at compile time — for example, a plugin system where third-party code registers new concrete types at startup — a std::unordered_map keyed by std::pair<std::type_index, std::type_index> provides O(1) dispatch after registration. This is the classical "multimethods" approach described by Andrei Alexandrescu in Modern C++ Design (chapter 11) and later by Eli Bendersky's multiple-dispatch series.

cpp

Godbolt

#include <functional>
#include <typeindex>
#include <unordered_map>
#include <stdexcept>

struct Shape { virtual ~Shape() = default; };
struct Circle    : Shape {};
struct Rectangle : Shape {};
struct Triangle  : Shape {};

// Custom hash for std::pair<std::type_index, std::type_index>
struct TypePairHash {
    std::size_t operator()(const std::pair<std::type_index, std::type_index>& p) const {
        auto h1 = std::hash<std::type_index>{}(p.first);
        auto h2 = std::hash<std::type_index>{}(p.second);
        return h1 ^ (h2 << 32 | h2 >> 32);  // interleave to reduce collisions
    }
};

using Handler = std::function<void(Shape&, Shape&)>;
using DispatchTable = std::unordered_map<
    std::pair<std::type_index, std::type_index>,
    Handler,
    TypePairHash
>;

DispatchTable& dispatch_table() {
    static DispatchTable table;
    return table;
}

// Registration helper — call this once per type pair (e.g. at program startup)
template<class A, class B>
void register_handler(Handler h) {
    dispatch_table()[{typeid(A), typeid(B)}] = std::move(h);
}

void collide(Shape& a, Shape& b) {
    auto key = std::make_pair(std::type_index(typeid(a)),
                              std::type_index(typeid(b)));
    auto it = dispatch_table().find(key);
    if (it == dispatch_table().end())
        throw std::runtime_error{"no handler registered for this type pair"};
    it->second(a, b);
}

// Registration at startup
void register_colliders() {
    register_handler<Circle, Circle>([](Shape& a, Shape& b) {
        auto& ca = static_cast<Circle&>(a);
        auto& cb = static_cast<Circle&>(b);
        (void)ca; (void)cb;
        // circle-circle collision logic
    });
    register_handler<Circle, Rectangle>([](Shape& a, Shape& b) {
        // circle-rectangle collision logic
        (void)a; (void)b;
    });
    // ... additional pairs registered by plugins at load time
}

The table grows at O(1) per registration. Lookup is a single hash probe; the handler itself is a direct std::function call. New concrete types added by plugins call register_handler without touching any existing code. The downside is that unregistered pairs throw at runtime rather than failing at compile time, so tests must cover all expected pairs.

Symmetric dispatch. To make collide(A, B) and collide(B, A) share one handler automatically, register both orderings pointing at the same lambda, or canonicalize the key before lookup:

cpp

Godbolt

void collide_symmetric(Shape& a, Shape& b) {
    auto ta = std::type_index(typeid(a));
    auto tb = std::type_index(typeid(b));
    if (ta > tb) { collide(b, a); return; }  // canonical order
    collide(a, b);
}

Strategy 5: Concepts-Constrained Overloads (C++20, compile-time only)

When all types are known at compile time and the dispatch is entirely static, C++20 concepts constrain free-function overloads so the compiler selects the most specific one without any virtual machinery. This is not runtime double dispatch — it is a zero-cost compile-time analogue useful in generic code that instantiates over closed type sets.

cpp

Godbolt

#include <concepts>
#include <iostream>

struct Circle    { double radius; };
struct Rectangle { double width, height; };
struct Triangle  { double base, height; };

// Concept: a "shape" type that we know about
template<class T>
concept KnownShape = std::same_as<T, Circle>
                  || std::same_as<T, Rectangle>
                  || std::same_as<T, Triangle>;

// Most-specific overloads selected at compile time
void dispatch(const Circle& a, const Circle& b) {
    std::cout << "Circle vs Circle\n";
    (void)a; (void)b;
}
void dispatch(const Circle& a, const Rectangle& b) {
    std::cout << "Circle vs Rectangle\n";
    (void)a; (void)b;
}
void dispatch(const Rectangle& a, const Rectangle& b) {
    std::cout << "Rectangle vs Rectangle\n";
    (void)a; (void)b;
}

// Generic fallback constrained to pairs of known shapes
template<KnownShape A, KnownShape B>
void dispatch(const A& a, const B& b) {
    std::cout << "Generic KnownShape pair\n";
    (void)a; (void)b;
}

// Caller template — both types resolved at instantiation
template<KnownShape A, KnownShape B>
void collide(const A& a, const B& b) {
    dispatch(a, b);  // overload resolution happens here, fully at compile time
}

Adding a new type means adding new overloads of dispatch; omitting a needed overload is a compile error (ambiguity or unsatisfied constraint), not a silent runtime bug. The requires clause form of the same pattern is equivalent but more composable when the constraint logic is shared across multiple functions.

Limitation. Because overload resolution operates on static types, this approach does not help when the concrete type is only known at runtime (e.g. objects arriving as Shape* from a factory). In that scenario, use Strategy 2 (Visitor) or Strategy 4 (type-indexed table).

Performance Comparison

Approach	Virtual calls per dispatch	Allocation	Extensibility	Best for
`dynamic_cast` chain	0 (but RTTI probe per branch)	None	Closed	N ≤ 3, frozen types
Classic Visitor (`accept`+`visit`)	2	Temporary visitor object	Open (forced update)	Open hierarchies, compiler ASTs
`std::variant` + `std::visit`	0 (compiler jump table)	None	Closed (compile error on gap)	Closed type sets, hot paths
Type-indexed function table	0 after O(1) hash lookup	Map + `std::function` overhead	Semi-open (register at runtime)	Plugin dispatch, extensible systems
Concepts-constrained overloads	0 (resolved at compile time)	None	Closed (compile-time only)	Generic code, all types known

The std::variant + std::visit path consistently outperforms the two-vtable Visitor in microbenchmarks (2–4x for small type sets that fit in cache), because the compiler can see through the entire dispatch and inline leaf handlers. The type-indexed table trades that inlineability for open extensibility: the std::function indirection and hash lookup add roughly 10–30 ns per call depending on cache state — acceptable for physics-engine plugin tiers but not for inner loops processing millions of pairs per frame.

Double Dispatch with std::variant and std::visit (C++17)

std::variant turns a runtime type question into a compile-time index lookup. When every participant in a dispatch is held as a std::variant, std::visit over two variants generates a complete N×M jump table at compile time — no vtables, no dynamic_cast, no manual branching.

cpp

Godbolt

// C++17
#include <variant>
#include <string_view>
#include <iostream>

struct Circle    { double radius; };
struct Rectangle { double w, h; };
struct Triangle  { double base, height; };

using Shape = std::variant<Circle, Rectangle, Triangle>;

// std::visit over two variants — compiler emits a 3×3 jump table
std::string_view collide(const Shape& a, const Shape& b) {
    return std::visit([](const auto& lhs, const auto& rhs) -> std::string_view {
        using L = std::decay_t<decltype(lhs)>;
        using R = std::decay_t<decltype(rhs)>;
        if constexpr (std::is_same_v<L, Circle>    && std::is_same_v<R, Circle>)    return "Circle/Circle";
        if constexpr (std::is_same_v<L, Circle>    && std::is_same_v<R, Rectangle>) return "Circle/Rect";
        if constexpr (std::is_same_v<L, Circle>    && std::is_same_v<R, Triangle>)  return "Circle/Triangle";
        if constexpr (std::is_same_v<L, Rectangle> && std::is_same_v<R, Circle>)    return "Rect/Circle";
        if constexpr (std::is_same_v<L, Rectangle> && std::is_same_v<R, Rectangle>) return "Rect/Rect";
        if constexpr (std::is_same_v<L, Rectangle> && std::is_same_v<R, Triangle>)  return "Rect/Triangle";
        if constexpr (std::is_same_v<L, Triangle>  && std::is_same_v<R, Circle>)    return "Triangle/Circle";
        if constexpr (std::is_same_v<L, Triangle>  && std::is_same_v<R, Rectangle>) return "Triangle/Rect";
        else                                                                          return "Triangle/Triangle";
    }, a, b);
}

int main() {
    Shape c = Circle{1.0};
    Shape r = Rectangle{2.0, 3.0};
    std::cout << collide(c, r) << '\n';  // "Circle/Rect"
}

Forgetting to handle a combination is a compile error, not a silent runtime bug. C++23 added std::variant::visit as a member (a.visit(f)), letting you write a.visit([&](const auto& lhs){ b.visit([&](const auto& rhs){ ... }); }) without repeating the variant names.

Double Dispatch and Symmetric Binary Operations

Many binary operations are commutative, yet dispatch tables are inherently ordered. Collision detection is the canonical example: collide(circle, rect) and collide(rect, circle) represent the same physical event and should share logic. Encoding both orderings separately doubles the number of cases and creates a maintenance hazard when the shared logic changes.

The canonical solution is to canonicalize the pair before lookup. For std::variant, the active index gives a stable total order; for the Visitor strategy, a type-ordering trait achieves the same result:

cpp

Godbolt

// C++17
#include <variant>
#include <algorithm>  // std::swap

struct Circle    { double r; };
struct Rectangle { double w, h; };
using Shape = std::variant<Circle, Rectangle>;

// Forward declaration of the canonical (ordered) handler
void collide_ordered(const Shape& lo, const Shape& hi);

void collide(Shape a, Shape b) {
    // Canonicalize: lower index first so each unordered pair maps to one entry
    if (a.index() > b.index()) std::swap(a, b);
    collide_ordered(a, b);
}

void collide_ordered(const Shape& lo, const Shape& hi) {
    std::visit([](const auto& lhs, const auto& rhs) {
        using L = std::decay_t<decltype(lhs)>;
        using R = std::decay_t<decltype(rhs)>;
        // With canonicalization, only N*(N+1)/2 cases exist (upper triangle)
        if constexpr (std::is_same_v<L, Circle>    && std::is_same_v<R, Circle>)    { /* ... */ }
        if constexpr (std::is_same_v<L, Circle>    && std::is_same_v<R, Rectangle>) { /* ... */ }
        if constexpr (std::is_same_v<L, Rectangle> && std::is_same_v<R, Rectangle>) { /* ... */ }
    }, lo, hi);
}

For the type-indexed table approach (Strategy 4), the same canonicalization applies: sort the type_index pair before the hash lookup so only N*(N+1)/2 entries are registered. When a pair is genuinely asymmetric (e.g. a bullet hitting a wall behaves differently from a wall hitting a bullet), do not canonicalize — asymmetry is data, not a bug.

Performance: vtable Double Dispatch vs std::visit vs if/else Chains

The choice of dispatch mechanism has measurable throughput impact on hot paths. Understanding where the cycles go guides the right trade-off between extensibility and speed.

cpp

Godbolt

// C++17 — illustrating three dispatch paths in a benchmarkable form
#include <variant>
#include <typeinfo>

struct Circle    { double r; };
struct Rectangle { double w, h; };
struct Shape     { virtual ~Shape() = default; };
struct VCircle    : Shape { double r; };
struct VRectangle : Shape { double w, h; };

// Path A: two vtable calls (Visitor pattern)
// Cost: 2 indirect branches + temporary object construction per call.
// Branch predictor sees alternating targets in a mixed workload — frequent mispredicts.

// Path B: std::variant + std::visit
// Cost: 2 array-indexed indirect jumps through a compile-time table.
// The table is 4–9 entries for 2–3 types and fits in a single cache line.
// Leaf handlers are inlined by the optimizer; no heap allocation.
using VShape = std::variant<Circle, Rectangle>;
void bench_visit(const VShape& a, const VShape& b) {
    std::visit([](const auto&, const auto&) { /* leaf */ }, a, b);
}

// Path C: dynamic_cast chain
// Cost: RTTI probe per branch; each probe walks the type hierarchy.
// O(depth) per probe; worst case O(N) probes before the right handler.
void bench_cast(Shape& a, Shape& b) {
    if (auto* ca = dynamic_cast<VCircle*>(&a)) {
        if (auto* cb = dynamic_cast<VCircle*>(&b))    { (void)ca; (void)cb; return; }
        if (auto* rb = dynamic_cast<VRectangle*>(&b)) { (void)ca; (void)rb; return; }
    }
    if (auto* ra = dynamic_cast<VRectangle*>(&a)) {
        if (auto* cb = dynamic_cast<VCircle*>(&b))    { (void)ra; (void)cb; return; }
        if (auto* rb = dynamic_cast<VRectangle*>(&b)) { (void)ra; (void)rb; return; }
    }
}

Typical throughput ranking on x86-64 with GCC -O2, two concrete types, random pair distribution: std::visit ≈ 800 M calls/s, two-vtable Visitor ≈ 300–400 M calls/s, dynamic_cast chain ≈ 150–250 M calls/s. The gap widens as the type count grows because std::visit's jump table stays O(1) while the dynamic_cast chain degrades O(N) and the Visitor stays at exactly two indirect branches but each branch stresses the branch target buffer more. Profile before selecting a strategy; real workloads with sorted or predictable type distributions close the gap significantly.

Double Dispatch in Game Engines

Game engines exercise double dispatch under the most demanding conditions: thousands of entity pairs per frame, mixed type populations, and a type set that grows throughout development. Understanding how production engines solve this problem illustrates the full range of trade-offs.

The most common pattern separates the dispatch table from game logic through a component registry. Each entity carries a ComponentType tag (often an integer or string hash) assigned at construction; the collision system maintains a handler map keyed by tag pairs rather than std::type_index:

cpp

Godbolt

// C++11
#include <functional>
#include <unordered_map>
#include <cstdint>
#include <utility>

using EntityTag = std::uint32_t;  // assigned by a component registry, e.g. via FNV hash

struct Entity {
    EntityTag tag;
    // ... position, velocity, shape data
};

struct TagPairHash {
    std::size_t operator()(std::pair<EntityTag, EntityTag> p) const noexcept {
        // Cantor pairing for small integer tags; use a better mix for large ones
        uint64_t a = p.first, b = p.second;
        return std::hash<uint64_t>{}((a + b) * (a + b + 1) / 2 + b);
    }
};

using CollisionHandler = std::function<void(Entity&, Entity&)>;
using CollisionRegistry = std::unordered_map<
    std::pair<EntityTag, EntityTag>, CollisionHandler, TagPairHash>;

CollisionRegistry& collision_registry() {
    static CollisionRegistry reg;
    return reg;
}

// Register during level/scene initialisation, not per-frame
void register_collision(EntityTag a, EntityTag b, CollisionHandler h) {
    collision_registry()[{std::min(a,b), std::max(a,b)}] = std::move(h);
}

// Called from the broad-phase collision loop, typically after AABB filtering
void dispatch_collision(Entity& a, Entity& b) {
    auto key = std::make_pair(std::min(a.tag, b.tag), std::max(a.tag, b.tag));
    auto it = collision_registry().find(key);
    if (it != collision_registry().end())
        it->second(a, b);
    // unregistered pairs silently ignored — intended for ghost/trigger layers
}

The tag-based map canonicalizes symmetry automatically (std::min/std::max on tags) and allows modders or scripting layers to register new handlers at runtime. Damage calculation follows the same pattern: an AttackTag × DefenseTag table maps to a damage formula, enabling data-driven tuning without recompiling. For inner-loop performance, game engines often replace std::function with raw function pointers or a virtual dispatch on a thin handler struct to eliminate the type-erasure overhead of std::function. The hash lookup dominates at roughly 15–30 ns per call; engines that need sub-10 ns typically sort entities by tag before the collision step and use a sorted two-pointer sweep, reducing the lookup to a sequential scan over contiguous handler entries.