The Problem Templates Solve

Part I · Module 18 · Chapter 18.1 · The Problem Templates Solve

1. The Function

Return the smaller of two values. For int:

    int smallerInt(int a, int b) { return b < a ? b : a; }

Nothing about that body mentions int except the types. The logic is compare, return one of them, and it is identical for every type that can be compared.

2. Alternative One: Write It Once Per Type

    static int         smallerInt   (int a, int b)                 { return b < a ? b : a; }
    static double      smallerDouble(double a, double b)           { return b < a ? b : a; }
    static const char* smallerStr   (const char* a, const char* b) { return std::strcmp(b,a) < 0 ? b : a; }

A. one function per type:
     3  1.5  apple

It works. And three things are wrong with it, in increasing order of seriousness.

The caller has to pick. smallerInt or smallerDouble — a decision the compiler could make and the programmer must.

It does not scale. A fourth type is a fourth function; a second generic operation across five types is ten functions.

And the copies drift. This is the real cost, and Chapter 15.3 §2 measured its general form: two functions meant to agree, written separately, disagreed 12,273 times out of 19,425 with no diagnostic. Five copies of one algorithm is five places a fix must be applied and four places it can be forgotten.

3. Alternative Two: One Function Against void*

The C answer: erase the type, pass the behaviour as a function pointer.

    static const void* smallerVoid(const void* a, const void* b,
                                   int (*less)(const void*, const void*))
    { return less(b, a) ? b : a; }

    static int lessInt(const void* a, const void* b) { return *(const int*)a < *(const int*)b; }

One function, any type. Used correctly:

B. one function against void*:
     3

Now used slightly incorrectly — two doubles with the int comparator:

     and the same call with the WRONG comparator still compiles:
     smallerVoid(&2.5, &1.5, lessInt) -> 2.5  (expected 1.5)

It compiled, ran, and returned the wrong value. 2.5 is not the smaller of 2.5 and 1.5. The comparator read the first four bytes of each double as an int, compared those, and the function faithfully returned what it was told.

Zero warnings. There is nothing for the compiler to object to: &dx converts to const void* because everything does, and lessInt has exactly the required signature. The type information the caller had was discarded at the boundary, and nothing downstream can recover it.

That is the defining weakness of the approach: the genericity is bought by throwing away the types, and the types were what made the code checkable.

And the interface is unpleasant on top of that: pointers in, pointers out, casts at every use.

A correction to the claim I expected to make here. The obvious second objection is that a call through a function pointer cannot be inlined — Chapter 15.6 §10 measured a functor beating a function pointer 0 indirect calls to 87 in one std::sort. Measured on this code, that objection does not hold as stated:

same translation unit, comparator visible:
  viaTemplate : 5 instr, 0 indirect calls   ldr | ldr | cmp | csel | ret
  viaVoid     : 5 instr, 0 indirect calls   (identical)

Byte-identical. lessInt was static and visible, so the compiler could see exactly which function the pointer held, devirtualise the indirect call, and inline the whole thing. The void* version paid nothing.

It is only across a translation-unit boundary — where the comparator is a real external symbol — that the cost appears:

comparator defined in another TU:
  viaTemplateXTU  : 5 instr, 0 calls
  viaVoidCrossTU  : 8 instr, 1 call
      stp | mov | adrp …lessIntExternal@GOTPAGE | ldr | bl …smallerVoid… | ldr | ldp | ret

Eight instructions and a real call, with the function pointer's address loaded through the global offset table — while the template is 5 instructions in both cases.

So the honest version of the performance objection is narrower than the usual one: the void* approach is inlinable exactly when the compiler can see the comparator, and the template is inlinable always. Chapter 17.7 §6's point generalises — the cost of indirection is almost never the branch, it is the optimisation the branch prevents, and here the compiler recovered it whenever it could prove what the pointer held.

4. Alternative Three: The Template

    template <typename T>
    const T& smaller(const T& a, const T& b) { return b < a ? b : a; }

C. one template:
     3  1.5

One definition, written once, and the types are kept. smaller(3, 7) compares ints with int's <; smaller(2.5, 1.5) compares doubles with double's. §3's mismatch is not merely detected — it is not expressible, because there is no separate comparator to get wrong.

The syntax is Chapter 18.2's subject. What matters here is the shape of what it bought: §2's safety with §3's single definition.

5. What It Costs at Run Time

Nothing. Measured at -O2:

    int viaTemplate(const int& a, const int& b) { return smaller(a, b); }
    int viaHand    (const int& a, const int& b) { return smallerInt(a, b); }

viaTemplate : 5 instr   ldr w8,[x1] | ldr w9,[x0] | cmp w8,w9 | csel w0,w8,w9,lt | ret
viaHand     : 5 instr   (identical)
identical: True

Byte-identical. Not similar — the same five instructions in the same order. The template produced exactly the code the hand-written function produced, which is the property Chapter 1.1 described as abstraction that costs nothing when used as intended, and which Chapters 14.2 §5 and 15.1 §4 measured for other mechanisms.

So the comparison with §3 is lopsided: the template is safer than the void* version and faster, because a < on a known type can be inlined and a call through a function pointer cannot.

6. What It Costs You Instead

The cost is real and it is not speed. A template with a non-trivial body, instantiated for one, three and eight types:

instantiations   __text bytes   process symbols
1 type(s)        180            1
3 type(s)        413            3
8 type(s)        843            8

And the eight symbols are eight separate functions:

__Z7processIcET_PKS0_m   __Z7processIdET_PKS0_m   __Z7processIfET_PKS0_m
__Z7processIiET_PKS0_m   __Z7processIjET_PKS0_m   __Z7processIlET_PKS0_m
__Z7processImET_PKS0_m   __Z7processIsET_PKS0_m

One template, eight functions, roughly linear growth in code size. That is the honest trade and it is the opposite of Module 17's: a virtual interface gives you one function and pays an indirection; a template gives you no indirection and pays a function per type.

Two things follow. Code size is the metric to watch, not speed — relevant for firmware and anything size-constrained. And the growth is per distinct type, so a template instantiated for one type costs nothing extra at all.

(There is a second cost this chapter will not pretend away: when a type does not satisfy what a template requires, the diagnostic can be enormous. Chapter 18.7 measures one at 370 lines and shows how to read it; Chapter 18.10 measures reducing the same failure to 7 lines. C++20's concepts address this directly and are outside this curriculum's C++17 baseline.)

7. The One-Line Model

Everything in this module rests on one fact, stated here and measured in Chapter 18.6:

A template is not code. It is instructions for generating code, and nothing is generated until a type is supplied.

template <typename T> const T& smaller(...) produces no machine code at all. smaller(3, 7) causes the compiler to generate smaller<int> — a real function, with real instructions, as §5's measurement showed.

That single fact explains the rest of the module: why an error can appear at a call site far from the template (Chapter 18.6), why definitions go in headers (Chapter 18.7), why the error messages are long (Chapter 18.7 again), and why §6's code size grows per type.

8. Which Problem Each Approach Solves

The template column is better in every row that matters and worse in exactly one, which is why the standard library is built this way: Chapter 19's containers and Chapter 20's algorithms are templates, not hierarchies.

9. Templates or Runtime Polymorphism?

Both solve one piece of code, many types, and the condition that separates them is the one Chapter 17.1 §7 stated.

That last row is underrated. A template works with int, which cannot derive from anything — Chapter 17.1 §6's table pointer requires a class. A template imposes no requirement on the type's inheritance at all, only on the operations it supports.

And the capability templates do not have is the one Chapter 17.1 §5 measured: a byte-identical client.o driving an implementation added afterwards. A template must see the type to instantiate, so a type supplied after compilation is out of reach. Open set means polymorphism; closed set means templates.

10. What to Actually Do

Reach for a template when one algorithm applies to several types and the types are known at compile time.

Do not write per-type copies — they drift, and Chapter 15.3 §2 measured what drift costs.

Do not erase types to void* — measured, a mismatch compiles and returns a wrong answer.

Expect no runtime cost — measured byte-identical to hand-written code.

Watch code size, not speed — measured 180 → 843 bytes across eight types.

Use a hierarchy instead when the type set is open — Chapter 17.1 §7's condition.

And remember a template needs nothing from the type's inheritance — only its operations.

11. Mistakes Worth Making Once

Copying a function per type. Five places to fix, four to forget.

Erasing types to void* for genericity. Measured: a mismatched comparator returned 2.5 instead of 1.5, 0 warnings.

Assuming a template is slower. Measured byte-identical, and faster than the function-pointer alternative.

Assuming a template is free. Measured 843 bytes for eight types against 180 for one.

Using a hierarchy for a closed type set. You pay the indirection and lost inlining for openness you never use.

Using a template where the type arrives at run time. It cannot — the type must be visible to instantiate.

Expecting a template to work only on your own classes. It works on int.

Treating a template as code. It is instructions for generating code — §7.

12. Interview Relevance

"Why do templates exist?" One algorithm, several types, with the types kept and checked. The strong answer leads with the alternatives: per-type copies drift, and void* discards the type information that made the code checkable.

"What is wrong with the void* approach?" Measured: a mismatched comparator compiled and returned the wrong value, with no diagnostic. And nothing can be inlined through a function pointer.

"Do templates cost anything at run time?" No — measured byte-identical to hand-written code at -O2.

"What do they cost?" Code size, per distinct instantiation — measured 180, 413 and 843 bytes for one, three and eight types.

"Templates or virtual functions?" Compile-time known set versus open set. The strong answer notes the cost profiles are duals: one trades space for openness, the other the reverse.

"What can a template do that a hierarchy cannot?" Work with types that cannot derive from anything — int, double, a vendor struct.

"And what can a hierarchy do that a template cannot?" Work with a type supplied after your code is compiled.

13. What You Should Be Able to Say Now

1. The problem is one algorithm across several types, with the types kept.
2. Per-type copies work and drift — Chapter 15.3 §2 measured 12,273 disagreements from two copies, let alone five.
3. Measured: the void* version compiled a mismatched comparator and returned 2.5 where 1.5 was correct, with 0 warnings.
4. Erasing the type erases the checking — that is the approach's defining weakness.
5. Measured correction to the usual objection: the void* version was byte-identical to the template when the comparator was visible in the same translation unit, and became 8 instructions with a real call only across a TU boundary — where the template stayed at 5.
6. A template keeps one definition and keeps the types, so §3's mismatch is not expressible.
7. Measured: the template compiled to 5 instructions byte-identical to the hand-written function.
8. Measured: code size went 180 → 413 → 843 bytes for one, three and eight types — eight distinct functions from one template.
9. So the trade is code size, not speed.
10. A template is not code — it is instructions for generating code, and nothing exists until a type is supplied.
11. That one fact explains instantiation, header placement, and the long error messages.
12. Templates and runtime polymorphism are duals: space for openness, or openness for space and speed.
13. The deciding condition is whether the type set is open — Chapter 17.1 §7.
14. A template imposes nothing on the type's inheritance — it works on int.
15. And it cannot work with a type supplied after compilation, which is the one thing a hierarchy can do.

14. Exercises

Exercise 1 — the three approaches. Write larger for int, double and std::string three ways: per-type, void*, and a template.

Exercise 2 — break the void* version. Construct a call that compiles and returns a wrong answer, and say why nothing warns.

Exercise 3 — the drift argument. Explain what goes wrong when one of five per-type copies is fixed, and name the chapter that measured the general case.

Exercise 4 — the runtime cost. State the measured instruction counts for the template and the hand-written version, and say what that means for the usual objection.

Exercise 5 — the real cost. Give the three measured code sizes and say what grows and what does not.

Exercise 6 — choose the mechanism. For each, template or hierarchy: a max over any comparable type; a bus-protocol checker accepting protocols other teams add; a fixed-width bit field; a logging sink chosen from configuration; a sort over a vendor's struct.

Exercise 7 — the inheritance row. Explain why std::sort is a template and not a function taking a Comparable&.

Exercise 8 — the model. State the one-line model of what a template is, and name two things it explains.

15. Summary

• The problem is one algorithm, several types, and the alternatives come first.
• Per-type copies drift; Chapter 15.3 §2 measured what that costs for two copies.
• Measured: the void* approach compiled a mismatched comparator and returned 2.5 where 1.5 was correct, with zero warnings — erasing the type erased the checking.
• Measured: the template compiled to the same five instructions as the hand-written function.
• Measured: code size grew 180 → 413 → 843 bytes across one, three and eight types — one template, eight functions.
• So templates trade code size for type safety and speed, which is the exact dual of Module 17's trade.
• A template is not code until a type is supplied — the fact the rest of this module rests on.
• The deciding question is whether the type set is open, and templates uniquely work with types that can derive from nothing.

The case is made and the syntax is still unexplained. §4 wrote template <typename T> and used it without accounting for a single character, which is the next chapter's job — along with something the frozen description of it insists on and which is easy to skip. A template does not work for any type; it works for any type supporting the operations its body uses. smaller needs <, and nothing in the declaration says so. Before C++20 there is no way to make the compiler enforce that requirement, which means it has to be stated in a comment and honoured by discipline — and the chapter after next shows what happens when it is not, because the diagnostic for a missing operation is produced at the point of instantiation, in terms of the template's internals, far from the call that was actually wrong.