jieqi's archive
Go back

C++: Polymorphism - Templates Pt 1

The overloading post covered the first two boxes on the compile-time branch of the polymorphism tree. This one starts on the third: templates. The map below is the full territory — this post walks the mechanism branch, and Pt 2 will cover the rest.

                          TEMPLATES
               (one body, many functions: a recipe
                 cooked per type, on demand)
                              |
       +----------------------+----------------------+
       |                      |                      |
 THE MECHANISM           THE CONTRACT           THE ECOSYSTEM
 (how it works)         (what T must do)       (how it fits in)
       |                      |                      |
 instantiation:          implicit, lives        joins the overload
 one fn + mangled        in the body,           set; lives in
 sym per type;           checked at             headers (weak syms,
 deduction infers        instantiation;         deduped by mangled
 T from args             concepts (C++20)       name)
                         make it explicit

 .................... out of scope ....................
 :  specialization   SFINAE   variadics               :
 :  metaprogramming  class templates  CRTP (next post):
 :......................................................

Motivation

In the last post we solved the absolute-value problem with overloads:

int    abs(int x)    { return x < 0 ? -x : x; }
long   abs(long x)   { return x < 0 ? -x : x; }
double abs(double x) { return x < 0 ? -x : x; }

This works fine: one name, and the compiler picks the right overload. The problem is that the bodies are all identical. Only the types change — the logic just needs < and unary - to work on x.

Now someone wants abs for float, so we add a fourth copy. Then for their custom BigInt class, a fifth. Each new type needs its own hand-written version of the same body, and if the logic ever changes, every copy has to be updated. Overloading let us reuse the name, but not the body.

The solution — a function template:

template <typename T>
T abs(T x) { return x < 0 ? -x : x; }

abs(-3);            // instantiates abs<int>
abs(-2.5f);         // instantiates abs<float>
abs(BigInt{-42});   // instantiates abs<BigInt>

We write the body once, and the type becomes a parameter. The copy-pasting still happens, but now the compiler does it: each call with a new type generates a real function at compile time, once per translation unit.

Note that we never wrote abs<int> — the compiler deduces T from the argument type. Deduction has rules of its own (stricter than overload resolution: no conversions allowed), which we’ll get to in Pt 2.

It also works for types that don’t exist yet. BigInt can be written years later, and abs(BigInt{-42}) will compile as long as BigInt supports < and unary -, without touching abs at all. Overloads can’t do this: an overload set only ever contains what we wrote by hand, while a template accepts any type that supports the operations it uses.

What the Compiler Generates

At a high level, the compiler turns our template plus its calls into ordinary functions — one per distinct type. Given the following file main.cpp:

template <typename T>
T abs(T x) { return x < 0 ? -x : x; }

int   a = abs(-3);
float b = abs(-2.5f);

the compiler generates the equivalent of:

template<> int abs<int>(int x) {
    return x < 0 ? -x : x;
}
template<> float abs<float>(float x) {
    return x < 0 ? -x : x;
}

int   a = abs(-3);
float b = abs(-2.5f);

The template<> prefix marks each as a concrete instantiation of the template rather than a hand-written function.

Per instantiation, the compiler also produces a mangled symbol for the linker, with the template arguments encoded into the name:

int abs<int>(int)        ->  _Z3absIiET_S0_
float abs<float>(float)  ->  _Z3absIfET_S0_

These mangled symbols live in the object file’s symbol table, which the linker uses to match call sites to definitions (see Understanding ELF for where that table sits in the file).

There’s a wrinkle here that plain functions don’t have. TUs compile in isolation, so if both a.cpp and b.cpp call abs(3), each one instantiates its own copy of abs<int> — and the exact same mangled symbol ends up in both object files:

a.o:  weak  _Z3absIiET_S0_     <- each TU that used abs<int>
b.o:  weak  _Z3absIiET_S0_        compiled its own full copy
                |
              linker: same name, marked weak
                -> keep one copy, discard the rest
                |
final binary:  one _Z3absIiET_S0_

For an ordinary function this would be a “duplicate symbol” link error: normal definitions are strong symbols, and the linker demands exactly one of each. Template instantiations are emitted as weak symbols instead — duplicates are expected, so the linker keeps one copy (matched by mangled name) and drops the rest. That’s how a template instantiated in every TU still exists once in the binary.

The template alone contributes nothing: delete the two calls and the object file contains no abs at all. Instantiations exist only because calls demanded them.

Wrapping Up

A template is a recipe, not a function: it contributes nothing until a call demands an instantiation, at which point the compiler generates a real function for that type, gives it a mangled symbol with the template arguments encoded, and marks it weak so the copies from other TUs can be deduplicated at link time. One body, many functions — and like the rest of the compile-time branch, none of it exists at runtime.

That’s the mechanism branch of the map. Pt 2 covers the other two: the contract (what happens when T doesn’t support the operations, and how concepts fix it) and the ecosystem (deduction rules, and how templates join the overload set).

Appendix: What Is a Translation Unit?

A translation unit is what a .cpp file becomes after preprocessing: every #include pasted in (recursively), macros expanded, #ifdefs resolved. The result is one giant, self-contained wad of C++ source with no preprocessor directives left — and that’s the unit of compilation.

lexer.cpp ──preprocessor──> translation unit ──compiler──> lexer.o

You can see it with clang++ -E lexer.cpp, which stops after preprocessing and prints the TU. A single #include <vector> balloons it to tens of thousands of lines — the header’s contents were physically pasted in.

Two things make the term worth having:

Next Post
C++: Polymorphism - Overloading