Static Polymorphism

The previous lesson moved candidate elimination to compile time: a template that did not fit dropped out of the list without an error. This lesson applies the same idea to a class hierarchy. If a base class knows at compile time which derived class it works with, there is no need to choose the call while running. This is static polymorphism. Our question is who pays the cost of this selection: when the decision is made at compile time, what is added to the compiler, and what drops out of the run?

M11/K04 treated dynamic polymorphism with virtual functions: a single interface, a body chosen while running. The “separate body for every type” seen in Rust in M10/K03 is the same concept; this lesson does not compare the two languages. This lesson does not establish a superiority either. Both methods pay at a different place for a single call. On the static side a separate body is written for every derived type, and this cost is in the compile kind; on the dynamic side the compiler does not produce bodies per type, there are only as many bodies as derived classes written, and the selection is made while running.

CRTP: The Base Knowing the Derived Class

CRTP (Curiously Recurring Template Pattern) does the following: the base class is a class template, and its parameter is the derived class itself. Square derives from Shape<Square>. The base converts itself to the derived type with static_cast<const D&>(*this) and calls the derived class’s function. There is no virtual function: which body will be called is known at compile time.

// shape.hpp — CRTP base and two derived classes
#ifndef SHAPE_HPP
#define SHAPE_HPP

inline int bodies = 0;

template <typename D>
struct Shape {
    long area() const {
        static const bool record = (++bodies, true);
        (void)record;
        return static_cast<const D&>(*this).compute_area();
    }
};

struct Square : Shape<Square> {
    long side;
    explicit Square(long s) : side(s) {}
    long compute_area() const { return side * side; }
};

struct Rectangle : Shape<Rectangle> {
    long width;
    long height;
    Rectangle(long w, long h) : width(w), height(h) {}
    long compute_area() const { return width * height; }
};

#endif

// crtp.cpp — dispatch with crtp
#include <cstdio>

#include "shape.hpp"

int main() {
    Square a(3);
    Rectangle b(2, 5);
    Square c(4);
    long total = a.area() + b.area() + c.area();
    std::printf("total=%ld bodies=%d\n", total, bodies);
    return 0;
}

total=35 bodies=2

MT32. The total is 9 + 10 + 16 = 35. Because Shape<D>::area is instantiated for two different types, there are two bodies: Shape<Square>::area and Shape<Rectangle>::area. The third call (Square(4)) reuses the first body. The dispatch with crtp row in the core is this count: three calls, two bodies. The cost has moved to the compile kind and carries a product count beside it.

In this arrangement Shape<D> is not a single class but separate classes of a family; there is no derivation relation between Shape<Square> and Shape<Rectangle>. static_cast<const D&>(*this) is correct only if the object really is a D. If D does not derive from Shape<D> at all, the conversion is rejected at compile time. But if a class derives from Shape<B> and writes another derived class as B, the compiler cannot catch it: the object is not really that type, and the behavior is undefined. For this reason making the constructor of the base class protected and marking the derived class final are common defenses.

The Virtual Function Counterpart

We write the same computation with a virtual function. There is a single base class and two derived classes; the bodies are written once, and the call is chosen while running through a base reference. This selection is generally realized with a memory structure called the virtual function table; here we do not print its size or contents, because what we measure is the number of bodies and calls.

// virtual.cpp — the same computation with a virtual function
#include <cstdio>
#include <memory>
#include <vector>

inline int virtual_bodies = 0;
inline int indirect_calls = 0;

struct VirtualShape {
    virtual ~VirtualShape() = default;
    virtual long area() const = 0;
};

struct VirtualSquare : VirtualShape {
    long side;
    explicit VirtualSquare(long s) : side(s) {}
    long area() const override {
        static const bool record = (++virtual_bodies, true);
        (void)record;
        return side * side;
    }
};

struct VirtualRectangle : VirtualShape {
    long width;
    long height;
    VirtualRectangle(long w, long h) : width(w), height(h) {}
    long area() const override {
        static const bool record = (++virtual_bodies, true);
        (void)record;
        return width * height;
    }
};

int main() {
    std::vector<std::unique_ptr<VirtualShape>> v;
    v.push_back(std::make_unique<VirtualSquare>(3));
    v.push_back(std::make_unique<VirtualRectangle>(2, 5));
    v.push_back(std::make_unique<VirtualSquare>(4));
    long total = 0;
    for (const auto& s : v) {
        ++indirect_calls;
        total += s->area();
    }
    std::printf("total=%ld bodies=%d indirect=%d\n", total, virtual_bodies, indirect_calls);
    return 0;
}

total=35 bodies=2 indirect=3

MT33. The result is the same, a total of 35 and again two bodies, because two derived classes write two bodies. The difference is in how the bodies are chosen: here all three of the three calls are indirect through a base reference (indirect=3), and which body will run is determined while running. In the CRTP version none of the three calls is indirect. These two rows tell the kinds apart: the number of indirect calls is written to run, and a separate body per type is written to the compile kind. Both are a product count; which one is faster is not claimed in this lesson.

Splitting into Components: Policy and Mixin

The second use of CRTP is to add behavior to a class. In this use, called a mixin, the base class template adds a function to the derived class; the derived class builds its own interface by choosing the base. A policy class is a class given as a template parameter that determines a part of the behavior. Both make the selection at compile time.

// mixin.cpp — mixin and policy class
#include <cstdio>

template <typename D>
struct Printable {
    void print() const {
        std::printf("%s area=%ld\n", D::name(), static_cast<const D&>(*this).area());
    }
};

struct MeterUnit {
    static long convert(long v) { return v * 100; }
};

struct CentimeterUnit {
    static long convert(long v) { return v; }
};

template <typename Unit>
struct Square : Printable<Square<Unit>> {
    long side;
    explicit Square(long s) : side(s) {}
    static const char* name() { return "square"; }
    long area() const { return Unit::convert(side) * Unit::convert(side); }
};

int main() {
    Square<CentimeterUnit> a(3);
    Square<MeterUnit> b(3);
    a.print();
    b.print();
    return 0;
}

square area=9
square area=90000

MT34. Printable<D> adds the print function; Square<Unit> takes both the mixin base and the policy parameter. With CentimeterUnit the area is 9, and with MeterUnit it is 90000. Each Unit choice has a separate Square and a separate print body written. The more components a policy is split into, the more the number of bodies can multiply by the number of combinations used; the cost of this combination accumulates in the compile kind, and no selection is left while running.

A Static Interface Constrained by a Concept

In CRTP the interface is implicit: the base calls compute_area, but if the derived class does not have this function, the error arises inside the body of the base class, and compilers generally show it as a long instantiation message. C++20 concepts write the interface explicitly. The function below accepts every type for which the area() call is valid and whose result can convert to long, and checks the constraint at the call site.

// interface.cpp — static interface constrained by a concept
#include <concepts>
#include <cstdio>

#include "shape.hpp"

template <typename T>
concept AreaShape = requires(const T& t) {
    { t.area() } -> std::convertible_to<long>;
};

template <AreaShape T>
long doubled(const T& s) { return s.area() * 2; }

struct NoArea {};

static_assert(AreaShape<Square>);
static_assert(AreaShape<Rectangle>);
static_assert(!AreaShape<NoArea>);

int main() {
    Square k(3);
    Rectangle d(2, 5);
    std::printf("doubled %ld %ld\n", doubled(k), doubled(d));
    return 0;
}

doubled 18 20

MT35. Square and Rectangle satisfy the concept through the area member; NoArea does not, and static_assert verifies this at compile time. The concept gives the calling side a contract: if the constraint is not satisfied, the error arises at the call site, and compilers generally show the name of the constraint. In addition, the concept adds no product count; the check ends during compilation and writes nothing to the running code.

Default Behavior and Hiding

In a virtual function, the derived class redefines a function of the base class with the same signature; in CRTP the arrangement is different. A default body is written in the base, and if the derived class defines a function with the same name, it hides it, and because the base function redirects the call to the derived class, it sees the derived class’s body. Everything is resolved at compile time: whichever scope the called name comes from, that body is chosen. Below, the Describable base writes a default describe; Circle defines its own version and the call in the base goes to it.

// default.cpp — default in the base, hiding in the derived
#include <cstdio>

template <typename D>
struct Describable {
    const char* describe() const {
        return static_cast<const D&>(*this).name();
    }
    const char* name() const { return "shape"; }
};

struct Triangle : Describable<Triangle> {};

struct Circle : Describable<Circle> {
    const char* name() const { return "circle"; }
};

int main() {
    Triangle t;
    Circle c;
    std::printf("triangle %s\n", t.describe());
    std::printf("circle %s\n", c.describe());
    return 0;
}

triangle shape
circle circle

MT36. Because Triangle does not define its own name function, the base’s default is found and describe returns shape. Because Circle defines a function with the same name, circle is found through static_cast<const D&>. Both are resolved at compile time; that is, the default in the base causes a body to be written only for the place the derived class did not write. In place of a selection made while running, name lookup at compile time works here.

A Separate Static Member for Every Type

Every instantiation of a class template carries its own static member. In CRTP this is used to give each derived class its own counter: the counter sits inside the base, but because Counted<Square> and Counted<Rectangle> are separate classes, the counters are separate too. In a non-template base, a single counter would add up all the derived classes.

// counted.cpp — counter per type
#include <cstdio>

template <typename D>
struct Counted {
    static inline int count = 0;
    Counted() { ++count; }
    Counted(const Counted&) { ++count; }
    ~Counted() { --count; }
};

struct Square : Counted<Square> {};
struct Rectangle : Counted<Rectangle> {};

int main() {
    Square a;
    Square b;
    Rectangle c;
    std::printf("square=%d rectangle=%d\n", Counted<Square>::count, Counted<Rectangle>::count);
    {
        Square temp = a;
        std::printf("square=%d\n", Counted<Square>::count);
    }
    std::printf("square=%d\n", Counted<Square>::count);
    return 0;
}

square=2 rectangle=1
square=3
square=2

MT37. When two Square objects and one Rectangle are created, the counters count separately: two and one. The copy raises the counter to three on entering the scope, and it becomes two on leaving the scope. For a design that wants a shared counter, the base must not be a template; when separate counters are wanted, CRTP gives this in one line. This behavior means a separate counter object is written for every derived class, and the cost is written to the compile kind; at run time only the counter increment remains.

Which One When

This comparison is a guide, not a ranking. If the set of types is closed at compile time and the bodies for each type can be made to be written by the compiler, CRTP sets up dispatch without an indirect call; but it does not carry different types in a single collection. If the set of types grows while running, or different types are to be held in a single container, the virtual function version is needed; bodies are not produced per type but every call is chosen while running. For a closed but mixed set, std::variant stands between the two: it gives a single collection and leaves the selection to run time. All three methods gave the same area total (35); the difference is in which kind the number is paid.

The Bounding Measurement

The limit of CRTP is that the derived classes have no common base. Shape<Square> and Shape<Rectangle> are separate types; a pointer to one does not convert to a pointer to the other. For this reason Square and Rectangle cannot be put into a single collection with CRTP. If a single collection is needed, for a closed set of types std::variant<Square, Rectangle> and std::visit are used. Which alternative is held sits in an index while running, that is, the selection returns to run time.

// variant.cpp — single collection with variant
#include <cstdio>
#include <variant>
#include <vector>

#include "shape.hpp"

int main() {
    std::vector<std::variant<Square, Rectangle>> v;
    v.emplace_back(Square(3));
    v.emplace_back(Rectangle(2, 5));
    v.emplace_back(Square(4));
    int choice = 0;
    long area = 0;
    for (const auto& s : v) {
        ++choice;
        area += std::visit([](const auto& x) { return x.area(); }, s);
    }
    std::printf("choice=%d area=%ld\n", choice, area);
    return 0;
}

choice=3 area=35

MT38. Three elements, three std::visit calls: choice=3, total area=35. The bodies are again compiled as Shape<Square>::area and Shape<Rectangle>::area, but which one will be called is now chosen for every element by looking at an index while running. That is, variant gives back to run time the decision CRTP took at compile time; in this version the cost has moved to the run kind. A single collection, a closed set of types, and the payment of the selection come together. If the set must be open (if new types will be added later), the virtual function version is suitable.

Summary

• The mechanism measured in this lesson moves the cost to the compile kind: with CRTP three calls are made with two bodies (total=35 bodies=2) and none of them is indirect.
• In CRTP the base class template knows the derived class; the call goes to the derived class with static_cast.
• The virtual function version gives the same total, but all three of the three calls are chosen while running (indirect=3); the two methods pay in different kinds, and no superiority is established.
• Mixins and policy classes split behavior into components at compile time; each combination causes a separate body to be written. A concept checks the static interface explicitly and at the call site.
• Different CRTP classes cannot be put in one collection through a common base; with variant the selection returns to run time (choice=3 area=35).

Next Step

In this lesson static dispatch moved the question of which body will run to compile time; the cost showed up in the number of bodies and in the code written. But there is no need to stay in a single thread: how many synchronization points does a counter protected by a lock add on every update?