Composite Pattern

Overview

The Composite pattern formalises two roles:

• Component — the shared interface (abstract base or concept) that leaves and composites both satisfy.
• Leaf — a terminal node. Implements the interface directly.
• Composite — a container node. Implements the interface by delegating recursively to its children, each of which is itself a Component.

The key design tension is transparency vs safety. A transparent design puts add()/remove() on Component, giving every node a uniform interface — but leaves are forced into no-op stubs or runtime throws, violating LSP. A safe design confines add()/remove() to Composite, requiring callers to hold a concrete type reference to modify structure. Modern C++ favors safety: virtual dispatch for open hierarchies, std::variant for closed ones.

Ownership in a well-formed tree is singular: the root holds the entire structure via a unique_ptr chain introduced in C++11. Shared subtrees need shared_ptr and are rarely justified.

Examples

Classic Virtual Dispatch

The expression tree is a canonical Composite use case — evaluation is identical regardless of tree depth:

// Component: shared interface (C++11 override, pure virtual)
class Expr {
public:
    virtual double eval() const = 0;
    virtual ~Expr() = default;
};

// Leaf
class Number : public Expr {
    double val_;
public:
    explicit Number(double v) : val_{v} {}
    double eval() const override { return val_; }
};

// Composite: binary operation
class BinOp : public Expr {
public:
    enum class Op { Add, Sub, Mul, Div };

private:
    Op op_;
    std::unique_ptr<Expr> lhs_, rhs_;   // C++11 unique_ptr owns subtrees

public:
    BinOp(Op op, std::unique_ptr<Expr> l, std::unique_ptr<Expr> r)
        : op_{op}, lhs_{std::move(l)}, rhs_{std::move(r)} {}

    double eval() const override {
        const double l = lhs_->eval(), r = rhs_->eval();
        switch (op_) {
        case Op::Add: return l + r;
        case Op::Sub: return l - r;
        case Op::Mul: return l * r;
        case Op::Div: return l / r;
        }
        std::unreachable(); // C++23 <utility>; pre-C++23: __builtin_unreachable()
    }
};

Building and evaluating (3 + 4) * 2:

auto tree = std::make_unique<BinOp>(BinOp::Op::Mul,
    std::make_unique<BinOp>(BinOp::Op::Add,
        std::make_unique<Number>(3.0),
        std::make_unique<Number>(4.0)),
    std::make_unique<Number>(2.0));

std::cout << tree->eval() << "\n"; // 14

The caller never distinguishes Number from BinOp — both are Expr. Adding a new UnaryOp leaf is open to extension without modifying traversal code.

Type-Safe Composite with std::variant

For closed node hierarchies — where the full set of node types is known at compile time — std::variant (C++17) replaces virtual dispatch with exhaustive compile-time checking.

Recursive variants require heap indirection to break the type cycle. std::variant<File, Dir> where Dir contains std::vector<Node> is self-referential and ill-formed. std::shared_ptr resolves this: its destructor type-erases deletion and does not require the pointee type to be complete at declaration time:

// C++17: recursive variant via shared_ptr indirection
struct FileNode { std::string name; size_t size; };
struct Node;      // forward declaration — breaks the cyclic dependency

struct DirNode {
    std::string name;
    std::vector<std::shared_ptr<Node>> children; // shared_ptr tolerates incomplete Node
};

struct Node {
    std::variant<FileNode, DirNode> data;  // C++17; both types complete here
};

The overloaded aggregate (C++17 variadic base class inheritance) enables clean multi-lambda dispatch:

// Deduction guide required in C++17; implicit for aggregates in C++20
template<class... Ts>
struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>; // C++17 CTAD guide

size_t total_size(const Node& n) {
    return std::visit(overloaded{
        [](const FileNode& f) -> size_t { return f.size; },
        [](const DirNode& d) -> size_t {
            size_t s = 0;
            for (const auto& child : d.children)
                s += total_size(*child);
            return s;
        }
    }, n.data);
}

Building the tree:

auto file = [](std::string name, size_t size) {
    return std::make_shared<Node>(Node{FileNode{std::move(name), size}});
};

auto root = std::make_shared<Node>(Node{DirNode{"root", {
    std::make_shared<Node>(Node{DirNode{"src", {
        file("main.cpp",  1024),
        file("utils.cpp",  512),
    }}}),
    file("README.md", 256),
}}});

std::cout << total_size(*root) << "B\n"; // 1792B

Adding a new node type without updating every std::visit call site is a compilation error — the exhaustive check is enforced by the compiler, not by convention.

Best Practices

Keep the Component interface minimal. Only place operations that are semantically valid for all nodes on the base class. Putting add()/remove() on Component forces leaves to implement meaningless stubs — use dynamic_cast (C++11) or std::get_if (C++17) to reach composite-specific operations at the rare call sites that need them.

Prefer std::variant for closed hierarchies. If every node type is known at compile time, variant eliminates virtual dispatch overhead, avoids heap allocation per node, and gives exhaustive checking. Reserve virtual dispatch for open hierarchies where external code must extend the tree with new types.

Guard against deep recursion. Both virtual and variant traversals recurse naturally. Trees with thousands of levels risk stack overflow. Replace recursion with an explicit stack for production code traversing unbounded structures:

// Iterative pre-order traversal — no stack overflow risk
void walk(const Node& root, auto&& visitor) {
    std::stack<const Node*> stk;
    stk.push(&root);
    while (!stk.empty()) {
        const Node* n = stk.top(); stk.pop();
        visitor(*n);
        if (const auto* d = std::get_if<DirNode>(&n->data)) { // C++17 get_if
            for (auto it = d->children.rbegin(); it != d->children.rend(); ++it)
                stk.push(it->get());
        }
    }
}

Common Pitfalls

Recursive variant without indirection fails to compile. Writing using Node = std::variant<File, Dir> where Dir contains std::vector<Node> is a circular type definition — Node must be complete to instantiate std::variant, but Node depends on Dir which depends on Node. Break the cycle with a forward declaration and shared_ptr, or wrap Dir::children in std::vector<std::unique_ptr<Node>> with an out-of-line destructor defined where Node is complete.

unique_ptr<T> with an incomplete T in composite nodes. If a composite class stores std::unique_ptr<Base> and the destructor is defaulted in the header, the compiler generates it where Base may be incomplete, producing a hard error. Declare the destructor in the header and define it = default in the .cpp translation unit that includes Base's full definition. This is the same constraint as the pimpl idiom.

Cyclic references cause infinite recursion. The pattern assumes a strict tree or DAG. Inserting a node as a child of its own ancestor makes traversal loop until the stack exhausts. Enforce ownership with unique_ptr — a node cannot own its ancestor, making cycles structurally impossible.

Fat interface on Component. Any virtual method on Component that only makes sense for composites (child iteration, add, remove) forces leaves to either throw or silently no-op. Both are correctness hazards. Use std::variant's exhaustive dispatch or an explicit downcast at the call site that actually needs composite behaviour — do not pollute the shared interface.

Recursive Variant with box<T>

Why std::variant Cannot Be Self-Referential

std::variant stores its alternatives inline — its size equals sizeof(largest_alternative) + sizeof(discriminant). A self-referential definition like:

// Does NOT compile — infinite size
using Expr = std::variant<int, struct AddExpr>;
struct AddExpr { Expr lhs, rhs; };

is circular: sizeof(Expr) depends on sizeof(AddExpr), which depends on sizeof(Expr). The compiler correctly rejects this because no finite layout is possible.

Breaking the Cycle with unique_ptr

The immediate fix is wrapping composite alternatives in std::unique_ptr, which stores only a pointer (fixed size, 8 bytes on 64-bit) and tolerates incomplete types:

#include <memory>
#include <string>
#include <variant>

struct Expr;
using ExprPtr = std::unique_ptr<Expr>;

struct LiteralExpr { int value; };
struct AddExpr { ExprPtr lhs, rhs; };
struct MulExpr { ExprPtr lhs, rhs; };

struct Expr {
    std::variant<LiteralExpr, AddExpr, MulExpr> data;
};

This compiles and correctly heap-allocates each composite node. The drawback is that Expr loses copyability — std::unique_ptr is move-only, so const Expr& no longer propagates constness through the unique_ptr layer (const unique_ptr<Expr> gives a mutable Expr&).

Value-Semantic box<T> Wrapper

A thin wrapper that adds deep-copy and const-propagation produces a type with value semantics identical to T, but heap-allocated. Foonathan's technique (May 2022) names this box<T>, inspired by Rust's Box<T>:

template <typename T>
class box {
    std::unique_ptr<T> impl_;
public:
    // Implicit construction from T — heap-allocates a copy
    box(T&& obj) : impl_(new T(std::move(obj))) {}
    box(const T& obj) : impl_(new T(obj)) {}

    // Deep copy — allocates a new T
    box(const box& other) : box(*other.impl_) {}
    box& operator=(const box& other) {
        *impl_ = *other.impl_;
        return *this;
    }

    // unique_ptr handles destruction
    ~box() = default;

    // Const-propagating access
    T& operator*() { return *impl_; }
    const T& operator*() const { return *impl_; }
    T* operator->() { return impl_.get(); }
    const T* operator->() const { return impl_.get(); }
};

Now the recursive variant reads cleanly, is copyable, and const Expr& prevents mutation through box<AddExpr>:

struct LiteralExpr { int value; };

// Forward-declare composite types inside the variant declaration
using Expr = std::variant<
    LiteralExpr,
    box<struct AddExpr>,
    box<struct MulExpr>>;

struct AddExpr { Expr lhs, rhs; };
struct MulExpr { Expr lhs, rhs; };

Building and evaluating an expression tree with std::visit:

template<class... Ts>
struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

int evaluate(const Expr& expr) {
    return std::visit(overloaded{
        [](const LiteralExpr& e) { return e.value; },
        [](const box<AddExpr>& e) {
            return evaluate(e->lhs) + evaluate(e->rhs);
        },
        [](const box<MulExpr>& e) {
            return evaluate(e->lhs) * evaluate(e->rhs);
        }
    }, expr);
}

// (3 + 4) * 2  →  14
auto tree = Expr(MulExpr{
    AddExpr{LiteralExpr{3}, LiteralExpr{4}},
    LiteralExpr{2}
});
// box<MulExpr> implicitly constructed; AddExpr implicitly boxed

Copying the entire tree is now a single Expr copy = tree; with no manual deep-copy logic.

std::polymorphic (proposed for C++26, P0201) aims to standardise this pattern as a library type, obsoleting hand-rolled box<T> in future code.

Virtual Dispatch vs. Variant: Performance Analysis

The two dispatch strategies impose different costs on the CPU microarchitecture. Understanding the breakdown determines which approach wins for a given workload.

Three Sources of Virtual Dispatch Overhead

1. Vtable indirection and branch misprediction. Each virtual call follows two pointer dereferences (object → vptr → function address) and an indirect branch. Modern CPUs predict indirect branches using an Indirect Branch Predictor (IBP). When a heterogeneous container stores nodes in random type order, the predictor cannot learn a pattern. Benchmarks on 20 million nodes show unsorted type sequences run 2.5x slower than type-sorted sequences for short virtual functions (Bogosavljevic, Johnny's Software Lab, 2021).

2. Data cache pressure from pointer scatter. The classic composite implementation stores vector<unique_ptr<Base>> — a vector of heap pointers. After insertions, deletions, and moves, adjacent pointers no longer point to adjacent memory. Each node access triggers a potential cache-line miss. Measurements show that when 100% of pointers are out of order, throughput drops 7.5x compared to perfectly sequential access.

3. Instruction cache eviction. Large virtual functions with many unique implementations keep different code hot simultaneously. In a round-robin type sequence, each call displaces the previous function's instructions from the L1i cache. A 128-clause long_virtual_function across four types ran in 7.5 s sorted-by-type but 12.3 s in round-robin order — a 1.6x i-cache penalty on top of the branch misprediction cost.

For short, leaf-heavy trees with a stable type distribution, the base vtable overhead is modest: a short function suffers ~18% overhead versus a non-virtual call when nodes are contiguous and type-homogeneous.

When Each Strategy Wins

std::variant advantages for closed composites:

• Nodes stored by value — no per-node heap allocation, contiguous layout in a vector<Node> is possible.
• std::visit dispatches through a compile-time jump table (O(1), branch-predictor friendly) rather than a vtable lookup.
• Compiler can inline visitor lambdas and apply loop vectorisation across homogeneous subtrees.
• Adding a new alternative that is not handled in std::visit is a compile error, enforcing exhaustiveness at zero runtime cost.

Virtual dispatch advantages for open composites:

• Plugin architectures or library APIs where external translation units must provide new node types — the interface is fixed, the implementation is open.
• Node types that carry large polymorphic state already on the heap; the unique_ptr cost is already paid.
• When the number of node types exceeds the threshold where std::variant discriminant checking becomes slower than a predicted indirect branch (typically 8–16 alternatives on modern CPUs).

Practical Mitigation for Virtual Dispatch

When open hierarchies are required but performance matters:

1. Sort containers by type before iteration to maximise branch prediction and i-cache reuse.
2. Use a pool allocator for composite nodes so vector<Base*> pointers remain sequential in memory, recovering the 7.5x pointer-scatter penalty.
3. De-virtualise hot leaf calls — mark small accessors final on concrete classes to allow devirtualisation at call sites with known concrete types.

Visitor Integration with std::visit

The Visitor pattern and the Composite pattern are often discussed together. In the virtual-dispatch composite, adding a new traversal operation requires modifying every node class (or using a separate Visitor base class and accept() machinery). With a std::variant composite, new operations are free — add a new std::visit call site without touching node definitions.

overloaded Helper (C++17)

The overloaded aggregate is the standard idiom for composing multiple lambdas into a single visitor callable:

// Single-definition header helper — no library dependency
template<class... Ts>
struct overloaded : Ts... { using Ts::operator()...; };
// C++17 CTAD deduction guide (implicit in C++20 aggregates)
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

Multiple Independent Traversals Over One Tree

The real payoff is operating on the same tree with completely independent visitors — pretty-print, evaluate, count nodes — without the accept()/Visitor base class boilerplate:

// Reusing the FileSystem variant from the Type-Safe Composite section

// Traversal 1: total size
size_t total_size(const Node& n) {
    return std::visit(overloaded{
        [](const FileNode& f) -> size_t { return f.size; },
        [](const DirNode& d) -> size_t {
            size_t s = 0;
            for (const auto& c : d.children)
                s += total_size(*c);
            return s;
        }
    }, n.data);
}

// Traversal 2: count leaf files
size_t file_count(const Node& n) {
    return std::visit(overloaded{
        [](const FileNode&) -> size_t { return 1; },
        [](const DirNode& d) -> size_t {
            size_t count = 0;
            for (const auto& c : d.children)
                count += file_count(*c);
            return count;
        }
    }, n.data);
}

// Traversal 3: collect all names matching a predicate
void find_files(const Node& n, std::string_view suffix,
                std::vector<std::string>& out) {
    std::visit(overloaded{
        [&](const FileNode& f) {
            if (f.name.ends_with(suffix))  // C++20 ends_with
                out.push_back(f.name);
        },
        [&](const DirNode& d) {
            for (const auto& c : d.children)
                find_files(*c, suffix, out);
        }
    }, n.data);
}

Each traversal is self-contained and testable in isolation. Adding a SymlinkNode to the variant produces a compilation error at every std::visit call that does not handle it — the compiler enforces consistency across all three traversals simultaneously.

Comparison with Classic accept()/Visitor

// Virtual: adding a new traversal requires a new Visitor subclass
struct NodeVisitor {
    virtual void visit(const FileNode&) = 0;
    virtual void visit(const DirNode&) = 0;
    virtual ~NodeVisitor() = default;
};

struct SizeVisitor : NodeVisitor {
    size_t total = 0;
    void visit(const FileNode& f) override { total += f.size; }
    void visit(const DirNode& d) override {
        for (auto& c : d.children) c->accept(*this);
    }
};

The accept() approach requires Node to declare virtual void accept(NodeVisitor&) = 0;, coupling the composite interface to the visitor interface. Adding a SymlinkNode requires updating NodeVisitor, every NodeVisitor subclass, and every accept() override — a four-file change for one new type. The std::visit approach requires changing only the variant declaration and every existing visit site, and the compiler tells you exactly which sites to update.

Real-World Applications

GUI Widget Hierarchies

GUI frameworks organise widgets in a containment tree: a Window holds Panels, which hold Buttons and Labels. The Composite pattern lets layout and rendering recurse uniformly:

// Closed set — perfect for std::variant
struct Button { std::string label; Rect bounds; };
struct Label  { std::string text;  Rect bounds; };
struct Panel;   // forward declaration

struct Widget {
    std::variant<Button, Label, box<Panel>> node;
    Rect bounds;
};

struct Panel {
    std::vector<Widget> children;
    Padding padding;
};

// Render traversal — inlined by compiler for each arm
void render(const Widget& w, Canvas& canvas) {
    std::visit(overloaded{
        [&](const Button& b) { canvas.draw_button(b.label, b.bounds); },
        [&](const Label&  l) { canvas.draw_text(l.text, l.bounds);    },
        [&](const box<Panel>& p) {
            for (const auto& child : p->children)
                render(child, canvas);
        }
    }, w.node);
}

Widget objects are stored by value in a vector<Widget> — contiguous memory, no per-widget heap allocation, no vtable pointer overhead per node. Layout passes and render passes both reuse the same tree representation without allocating secondary visitor objects.

Scene Graphs in Game Engines

A 3D scene graph is a canonical Composite application: spatial transforms compose through the hierarchy, so moving a parent automatically repositions all descendants. The updateSelfAndChild() recursive pattern (LearnOpenGL, 2021) propagates model matrices down the tree:

class SceneNode {
public:
    Transform local;                                  // position/rotation/scale
    glm::mat4 world_matrix{1.0f};                    // computed, not stored by parent
    std::vector<std::unique_ptr<SceneNode>> children; // owns subtree

    void update(const glm::mat4& parent_world = glm::mat4{1.0f}) {
        world_matrix = parent_world * local.to_matrix();
        for (auto& child : children)
            child->update(world_matrix);
    }
};

An optimisation commonly added in production engines is a dirty flag — a boolean is_dirty_ set whenever local changes. update() skips recomputation and children propagation when the node is clean, cutting traversal cost on static geometry that makes up the majority of a typical scene.

The open-hierarchy virtual approach is appropriate here because game engines frequently extend the node hierarchy with new types (MeshNode, LightNode, CameraNode, ColliderNode) across separate compilation units or plugins.

See Also

• CRTP — static polymorphism as an alternative to virtual dispatch for leaf/composite roles
• Type Erasure — unifying heterogeneous types without a common base class
• std::variant — C++17 discriminated union underlying the type-safe composite approach