Templates: compile-time polymorphism

Lesson 10 gave us polymorphism — one piece of code, many types — but charged for it: a virtual call chases a pointer through a vtable, defeats inlining, and forces every participant to share a base class. Lesson 09 showed that a non-virtual call is free. The question this lesson answers is: can we have polymorphism without the vtable — write max or Stack once, use it for int, double, or your own type, and pay zero runtime cost? The answer is templates: polymorphism resolved entirely at compile time. The one new idea is instantiation — the compiler stamps out a separate concrete version of your code per type, so each call site sees code as tight as if you had hand-written it for that one type.

The thesis, here

Templates are the purest expression of zero overhead. A virtual call (Lesson 10) decides at runtime which code to run, and you pay for that decision on every call. A template moves the decision to compile time: by the time the program runs, the choice is already baked into the machine code, so there is nothing left to pay. The trade is visible in the bill too — the cost moves to compile time and binary size (code bloat), not run time. Ask the five questions of a template call and the runtime answers are all "free."

Linear position

Prerequisite: Lesson 09 (a non-virtual method is a plain function call — abstraction can be free) and Lesson 10 (the vtable — the one abstraction you do pay for, and why). This lesson is the third beat of that arc: 09 free, 10 paid, 12 free again by a different mechanism.
New capability: write one function or class that works for many types with full type safety and zero runtime overhead; explain what code the compiler generates for each type used (instantiation); and use a C++20 concept to give a template a readable, checkable interface.

The plan

Five moves. (1) State the problem precisely and rule out the three bad answers — macros, void*, and virtual dispatch. (2) Function templates and the syntax. (3) Instantiation: watch the compiler stamp out int and double versions, and prove they equal the hand-written non-generic code. (4) Class templates — a Stack<T>. (5) "Duck-typed at compile time," why the error messages are infamous, and how C++20 concepts fix it.

1 · The problem, and three answers that don't work

You want to write the maximum of two values exactly once and use it for int, double, std::string, and a user-defined type — with no copy of the logic per type, no runtime cost, and no loss of type safety (the compiler should still reject max(an_int, a_widget) if that comparison is meaningless). Three pre-template approaches each fail one of those three requirements.

Approach	How it works	What it loses
Macro `#define MAX(a,b)`	The preprocessor (Lesson 01) does blind text substitution before the compiler sees anything.	No type checking. It is text, not code — no types, no scope. `MAX(i++, j)` evaluates `i++` twice; `MAX(a, b)` with mismatched types substitutes silently. The compiler never sees a function.
*`void`** (a pointer to untyped memory)	Pass everything as a "pointer to anything," cast back inside, like C's `qsort`.	No type safety. You hand-cast on the way in and out; pass the wrong type and you get undefined behavior (Lesson 19), not a compile error. Also forces heap/indirection and defeats inlining.
Virtual dispatch (Lesson 10)	A common base class with a `virtual` compare; every type inherits and overrides.	Runtime cost + a forced base class. Every call chases the vptr through the vtable and can't inline; and `int` and `double` can't inherit from your base at all. You pay per call for a decision that is fixed at compile time.

The pattern: macros throw away the type system, void* throws away type safety, and virtual dispatch keeps both but charges runtime for them. A template keeps the type system and type safety and charges nothing at run time — because it makes the compiler do the work the other three pushed to either the preprocessor or the running program.

2 · Function templates

A template is not code; it is a pattern for generating code. You write it once with a type left as a parameter — by convention named T — and the compiler fills in T with a real type whenever you use it.

template <typename T>      // T is a type parameter, filled in at the call site
T max(T a, T b) {
    return (a < b) ? b : a; // the ONLY requirement on T: that a < b compiles
}

int    i = max(3, 7);        // compiler deduces T = int
double d = max(2.5, 1.5);    // compiler deduces T = double
// max(3, 2.5);              // ERROR: T can't be both int and double — type safety intact

Note the type safety the macro lacked: the compiler deduces T from the arguments and rejects the call if they disagree. Note the requirement on T is implicit — the body uses a < b, so any type with a working < works, and any type without one fails to compile. We will come back to that implicitness in §5; it is the source of both the power and the terrible error messages.

3 · Instantiation — the one idea that explains everything

When you call max(3, 7), the compiler performs template instantiation: it takes the pattern, substitutes T = int throughout, and generates a real, concrete function — call it max<int> — as if you had typed it out by hand. Call it with doubles and it generates a second concrete function, max<double>. Each distinct set of type arguments produces one instantiation; identical ones are generated once and shared.

template max<T> instantiations the compiler stamps out ---------------- --------------------------------------- T max(T a, T b) { ---> int max<int>(int a, int b) { return (a<b)?b:a; } return (a<b)?b:a; ---> double max<double>(double,double){ return (a<b)?b:a; } } (one concrete function per type actually used)

This single fact explains both sides of the template trade-off:

Why zero runtime overhead

max<int> is an ordinary function over int. There is no T left, no lookup, no indirection — the type was resolved before the program ran. The optimizer can even inline it (Lesson 09). It is the exact opposite of Lesson 10's vtable, where the choice survives into run time and costs a pointer chase per call.

Why code bloat is the price

Use the template with 8 different types and the compiler stamps out 8 copies of the machine code. The cost the others paid at run time, the template pays in binary size and compile time. Usually a good trade; occasionally (many types × a huge template) it matters.

Worked example — it compiles to the hand-written code

Compare what the template produces against a programmer who never heard of templates and just wrote two functions by hand:

// Hand-written, non-generic           // Template instantiations
int max_i(int a, int b)                int    max<int>(int a, int b)
    { return (a<b)?b:a; }                  { return (a<b)?b:a; }
double max_d(double a, double b)       double max<double>(double a, double b)
    { return (a<b)?b:a; }                  { return (a<b)?b:a; }

These are identical — same source, therefore same assembly (on x86-64, both max<int> and max_i compile to a cmp + a conditional move, no branch, no call). Drop the template and the non-generic versions into godbolt.org and the emitted instructions match line for line. That is the zero-overhead principle made literal: the abstraction did not cost a single instruction over what you would have hand-coded — the generality lives entirely at compile time and evaporates before run time.

4 · Class templates — a `Stack<T>`

The same mechanism generalizes a whole class. A class template parameterizes a type over T; Stack<int> and Stack<std::string> are two distinct, separately-instantiated classes that share one source. (This is exactly how std::vector<T> works — Lesson 13.)

template <typename T>
class Stack {
    std::vector<T> data_;            // a vector OF T — instantiated per T too
public:
    void push(T value) { data_.push_back(std::move(value)); } // move, Lesson 06
    T    pop()         { T top = std::move(data_.back());
                         data_.pop_back(); return top; }
    bool empty() const { return data_.empty(); }              // const, Lesson 16
};

Stack<int>         ints;     // instantiates a concrete Stack-of-int class
Stack<std::string> words;    // a second, unrelated concrete class
ints.push(42);               // type-checked: push(int) — pushing a string is an error

Each instantiation is a real class with real, concrete member layout — Stack<int> holds a vector<int>, full stop. There is no shared base, no vtable, no indirection: an ints.push(42) is just a non-virtual method call (Lesson 09) on a concrete type. Member functions are themselves instantiated lazily — the compiler only stamps out pop() for Stack<int> if you actually call it, which keeps the bloat to what you use.

5 · Duck-typed at compile time — and why the errors are infamous

Look again at max: the only thing it ever required of T was that a < b compile. That requirement is implicit — written nowhere in the signature, only discovered when the compiler tries to instantiate the body. This is "duck typing at compile time": if a type walks like something comparable (has a <), the template accepts it; the contract is structural and unstated, checked only at instantiation.

The upside is enormous flexibility — your type needs no base class, no interface declaration, just the right operations. The downside is the legendarily bad error messages. Instantiate Stack<Widget> where Widget has no <, and the failure surfaces deep inside the template body (or three levels into std::sort), as a wall of text about Widget not matching operator< — because the requirement was never stated up front for the compiler to check early.

C++20 concepts — make the implicit contract explicit

A concept is a named, compiler-checked predicate on types: it states the requirements a T must satisfy, up front, so violations are reported as a clean message at the call site instead of a cascade inside the body.

#include <concepts>

template <typename T>
concept LessThanComparable = requires(T a, T b) {
    { a < b } -> std::convertible_to<bool>;   // T must support a < b yielding bool-ish
};

template <LessThanComparable T>                // constrain T with the concept
T max(T a, T b) { return (a < b) ? b : a; }

max(3, 7);          // OK — int satisfies LessThanComparable
// max(w1, w2);     // ERROR, but now: "Widget does not satisfy LessThanComparable" —
                    //   stated at the call, not buried in the body

The generated code is identical — concepts add zero runtime cost; they are purely a compile-time check (Lesson 16's "push errors left" idea). They turn the template's silent duck-typed contract into a documented, enforced one.

Common mistakes / failure modes

Definition in a .cpp file

A template isn't code until instantiated, so the compiler needs the full definition visible at every use site. Put templates in headers — splitting declaration (.h) from definition (.cpp) gives "undefined reference" link errors.

Expecting one type, getting bloat

Instantiating a heavy template over dozens of types multiplies binary size. Real cost, real trade-off — sometimes a non-generic or type-erased version is the right call.

Mismatched deduction

max(3, 2.5) fails: one T can't be both int and double. The fix is explicit (max<double>(3, 2.5)) or two type parameters — not silent conversion like a macro would do.

Reading the error from the top

Template errors are deepest at the bottom. Without a concept, read the last "required from here" line to find your actual call. With a concept, the constraint failure is reported plainly — another reason to use them.

Checkpoint exercise

Try it

Write template <typename T> T sum(const std::vector<T>& v) that accumulates with +. (1) Call it with a vector<int> and a vector<double>; in godbolt, confirm two separate instantiations are emitted and that each matches a hand-written non-generic sum_int / sum_double instruction-for-instruction — proving zero overhead. (2) Now call it with a vector<std::string> (which does have +) and a vector<Widget> with no +; read the raw error. (3) Add a C++20 concept Addable and constrain T; re-run the Widget case and compare how much clearer the message is. Predict in each case which instantiations the compiler generates before you compile.

Where this points next

We now have a way to write one piece of code for many types at zero runtime cost — and the most important use of templates in all of C++ is the Standard Template Library. Lesson 13 turns the spotlight on STL containers: vector, array, map, unordered_map and friends are all class templates like our Stack<T>, but each encodes a different ownership and memory-layout decision with a different cost model. It is where this lesson's "templates are free" meets Lesson 08's "layout dominates performance" — and finally explains, with a cost table, why a contiguous vector almost always beats a pointer-chasing list.

Takeaway

Templates give you polymorphism — one algorithm or class for many types, with full type safety — at zero runtime cost, by moving the type decision from run time to compile time. They beat the three bad alternatives: macros (no type checking — blind text), void* (no type safety — manual casts and UB), and virtual dispatch (type-safe but charges a vtable lookup per call and forces a common base). The mechanism is instantiation: the compiler stamps out one concrete function or class per type actually used, so each is as tight as the hand-written non-generic version — which is exactly why the code is free at run time and why the price shows up instead as binary size and compile time (code bloat). Templates are "duck-typed at compile time": requirements on T are implicit, discovered only when the body is instantiated, which is why the error messages are so bad — and why C++20 concepts, a named compile-time predicate on types, exist to state that contract up front and report violations cleanly, all at no runtime cost.

Interview prompts

Why is a template call zero runtime overhead while a virtual call (Lesson 10) is not? (§3 — the template resolves T at compile time and emits an ordinary concrete function the optimizer can even inline; a virtual call defers the choice to run time and pays a vptr/vtable indirection per call.)
Contrast templates with macros and void*. (§1 — macros do blind text substitution with no type checking; void* erases the type so mistakes are UB not compile errors; templates keep the full type system and type safety while charging nothing at run time.)
What is template instantiation, and what trade-off does it create? (§3 — the compiler stamps out a concrete function/class per set of type arguments; zero runtime cost, but the cost reappears as larger binaries and longer compiles — code bloat.)
What does it mean that templates are "duck-typed at compile time"? (§5 — the requirements on T are implicit and structural, checked only when the body is instantiated, not declared in the signature — which is why errors surface deep inside the template.)
What problem do C++20 concepts solve, and do they cost anything at run time? (§5 — they name and enforce a template's type requirements up front so violations report cleanly at the call site; they are a pure compile-time check with zero runtime cost.)
Why must template definitions usually live in headers? (§Common mistakes — a template is uninstantiated until used, so the full definition must be visible at every instantiation point; hiding it in a .cpp yields link-time "undefined reference" errors.)
Argue that a templated max<int> compiles to the same machine code as a hand-written non-generic max_i. (§3 — after substitution they are character-for-character the same source over int, so they emit identical assembly; the generality existed only at compile time and is gone by run time.)