Module 12 — Concepts and Explanations

The running system holds items, members, and loans. By Module 11 it had a Catalogue, a member list and a loan register: three containers with the same logic, differing only in what they store. Every fix had to be applied three times, and the fourth record kind would have been a fourth copy.

This page answers the question that removes the duplication, and then answers the honest follow-up — is a template always the right tool?

A template is a pattern, not a type. You write the code once in terms of a parameter the caller supplies, and the compiler generates a concrete version for each set of arguments actually used. Everything is decided before the program runs.

Every snippet here is small enough to compile. This module's diagnostics are the worst in C++, so the reading of them is a skill taught here on purpose — see section 8.

---

1. I have written this container three times. What are my options?

Three answers, and they trade differently:

Approach	Decided when	Cost at run time	Works for int?	Extendable after compiling?
Copy and paste	—	none	yes	by editing every copy
Virtual functions (Module 7)	run time	one indirection per call	no: needs a base class	yes: new types plug in
Templates (this module)	compile time	none	yes	no: new types recompile the users

The second row explains why Module 8's Shape hierarchy is right for "draw anything that can be drawn" and wrong for "a collection of int". The third row is what this module adds: one definition, many types, no run-time cost, and the type fully known to the compiler — which is also why a template cannot be extended later, and why section 7 spends time on that trade.

---

2. What if the type were a parameter?

template <typename T>
T maximum(T left, T right) {
    return left > right ? left : right;
}

std::cout << maximum(3, 7)                                  << '\n';   // T = int
std::cout << maximum(std::string("b"), std::string("a"))    << '\n';   // T = std::string
std::cout << maximum(2.5, 1.5)                              << '\n';   // T = double

template <typename T> introduces a type parameter: a placeholder, not a type. The compiler works out what it stands for from the arguments — that is deduction — and then writes a real function for that type. The generated function is an instantiation, and it is as efficient as one you wrote by hand, because in every respect it is one.

Three things worth noticing in that tiny example:

• T appears twice and must be one type. maximum(3, 4.5) does not compile, because int and double disagree and deduction has to produce one answer. The error names the conflict precisely (section 8).
• The return type is T, not a class. No base class, no vtable, no indirection. That is why a template works for int, which inheritance cannot touch.
• Deduction removes top-level const and references when the parameter is written T value, because the argument is being copied. Write const T& when you mean to look at the argument rather than copy it.

---

3. Why does this fail for Book?

Because the template was imposing a requirement that nobody wrote down: operator> must exist for T. int and std::string satisfy it incidentally. A Book does not, and the error appears at instantiation:

error: no match for 'operator<' (operand types are 'const Reading' and 'Reading')

That message is a requirement surfacing. Two lessons follow, and both are the point of this module:

1. Every template has requirements, whether or not they are documented. The general ones are the operations its body uses: +, <, ==, begin(), a copy, a move.
2. Requirements belong in the interface, in words, next to the declaration — and the ones the compiler can check should be stated so that the error is one readable line instead of a page:

template <typename T>
double average(T a, T b) {
    static_assert(std::is_arithmetic<T>::value,
                  "average<T> requires an arithmetic type: use Money::average() instead");
    return static_cast<double>(a + b) / 2.0;
}

For average<Money> that produces exactly:

error: static assertion failed: average<T> requires an arithmetic type: use Money::average() instead
note: 'std::integral_constant<bool, false>::value' evaluates to false

One line, naming the requirement and the alternative — instead of an error about + on Money from four lines deeper.

---

4. How do I parameterise a type?

The same way, with class in place of a function:

template <typename T>
class Stack {
public:
    void push(T value) { items_.push_back(std::move(value)); }

    T& top() {
        if (items_.empty()) { throw std::out_of_range("top() on an empty Stack"); }
        return items_.back();
    }

    std::size_t size() const { return items_.size(); }

private:
    std::vector<T> items_;
};

Stack<int>, Stack<std::string> and Stack<std::vector<int>> are three unrelated types, each with a real definition generated by the compiler. Two consequences that surprise people:

• Each instantiation has its own copy of any static data member. Stack<int>::count() and Stack<std::string>::count() are different functions reading different variables. Nothing is shared between instantiations, because they are not the same type.
• Member functions of a class template are compiled only when they are used. A member that could not possibly work for a given element type is harmless until somebody calls it. That is why Repository<std::string> compiles until you ask it to sort by an id that std::string does not have — and it is why some template errors arrive very late.

This is the point at which the module's vocabulary stops being abstract and becomes greppable: std::vector, std::map, std::unique_ptr and std::sort are all instances of exactly this mechanism.

---

5. Where does the code for each type come from?

From the compiler, at compile time, where the template is used — which is why the definition must be visible there:

// repository.h
template <typename T>
class Repository {
public:
    void add(const T& record);          // declaration
};

// repository.cpp
template <typename T>
void Repository<T>::add(const T& record) { items_.push_back(record); }   // definition, invisible

// main.cpp
Repository<int> numbers;
numbers.add(7);                          // the compiler needs the DEFINITION here

That three-file arrangement compiles cleanly and then fails to link. It is worth seeing what the linker knows, because on this toolchain the linker names no symbol at all — only collect2.exe: error: ld returned 5 exit status — while the object files tell the whole story:

$ nm -C main.o | grep ' U ' | grep Repository
                 U Repository<int>::add(int const&)
                 U Repository<int>::size() const
$ nm -C repository.o | grep -c Repository
0

main.o asks for two symbols. The object built from the template's own source defines none, because nothing in repository.cpp instantiated Repository<int>. The generic version was never generated. The fix is one of two things:

• put the definition in the header (the normal answer), so every user can instantiate it; or
• keep it in a .cpp and instantiate explicitly — template class Repository<int>; — which is a deliberate trade: a shorter build for users, and every new type becomes a manual decision.

---

6. Can I parameterise a number?

Yes, with a non-type parameter — a value rather than a type:

template <typename T, std::size_t Capacity>
class FixedArray {
public:
    static constexpr std::size_t capacity() { return Capacity; }
    bool push(const T& value) {
        if (size_ == Capacity) { return false; }
        data_[size_++] = value;
        return true;
    }
private:
    T data_[Capacity]{};        // an array, not a pointer: no allocation at all
    std::size_t size_ = 0;
};

FixedArray<int, 3> and FixedArray<int, 8> are different types with different storage inside them. Three consequences, all demonstrated by examples/module-12/03-non-type-parameters/main.cpp:

• No heap allocation. The elements are members, so there is nothing to free and no Rule of Five to write (Module 10). sizeof(FixedArray<int, 8>) is 40 bytes on this machine: thirty-two for the elements and eight for the counter.
• The capacity is a compile-time constant, usable where C++ requires one — an array bound, another template argument, a switch case, a static_assert.
• It is the wrong tool for a run-time size. FixedArray<int, requested> cannot compile when requested comes from a config file, because a template argument must be a constant expression. That is when std::vector<int> is the honest answer.

std::array<T, N> is this idea in the standard library, and a matrix dimension, a fixed pool size and a hash table's bucket count are all legitimate uses. A value that differs per object of the same type is not.

---

7. Is there only one kind of abstraction?

No, and choosing between the two kinds is a design skill rather than a syntax question. The same extension point, built twice:

// Compile-time: the container knows its element type exactly.
template <typename T>
class Repository { std::vector<T> items_; /* ... */ };

// Run time: one interface, implementations supplied later.
class RecordSink {
public:
    virtual ~RecordSink() = default;
    virtual void store(const Record& record) = 0;
};

	Templates	Virtual functions
Chosen when	Compile time	Run time
Run-time cost	None added	One indirection per call
Element types must be known	At compile time	Only the base type
Works for int, std::string	Yes	No
Add a new implementation later	Requires recompiling users	Add a class, recompile nothing else
Errors appear	At instantiation, often deep in library code	At the call site, or as a missing override

Neither is better in the abstract. Reach for the template when the type is a fact about the design, and for an interface when the type is something the program discovers — a plugin, a configured backend, a list of shapes read from a file.

---

8. Why is this error three pages long? How do I read it?

Because a template is instantiated inside other templates, and the compiler prints the whole path it took. The method, and it is a method rather than a hope:

1. Read the last line first. That is the actual complaint, and it is about your type.
2. Find which template argument it concerns by looking for [with T = ...] in the chain above.
3. Reproduce it in five lines — your type, the one operation — with no library code at all. A minimal case isolates the requirement.

A real example, three lines of code reduced to one complaint:

scratch/m12d-errors.cpp: In instantiation of 'T smallest(const std::vector<T>&) [with T = Reading]':
scratch/m12d-errors.cpp:31:20:   required from here
scratch/m12d-errors.cpp:17:19: error: no match for 'operator<' (operand types are 'const Reading' and 'Reading')

Read bottom-up, that says: Reading cannot be ordered. The library was never the problem; the requirement was real and undocumented. Two more messages you will meet in every template you write:

error: need 'typename' before 'T::value_type' because 'T' is a dependent scope
error: dependent-name 'T::value_type' is parsed as a non-type, but instantiation yields a type
note: say 'typename T::value_type' if a type is meant

T::value_type is a dependent name: until T is known, the compiler cannot tell whether value_type is a type or a static value. You know, so you say so — typename T::value_type — and the third line above is the compiler telling you exactly that.

error: no matching function for call to 'larger(int, double)'
note:   deduced conflicting types for parameter 'T' ('int' and 'double')

One parameter, two answers. Make the types agree, or give the function two parameters.

And the one that catches everybody at first:

error: class template argument deduction failed:
note:   couldn't deduce template parameter 'T'

Stack untyped;              // Stack of what? Nothing in the line says.
Stack<int> typed;           // now the compiler can generate the class

A class template is not a type. Before C++17 you always wrote the arguments; C++17 and later can deduce them from a constructor's arguments, which is why std::pair p{1, 'a'} works today.

---

9. Can I write a different version for one type?

Yes, and it is used in the standard library for exactly this reason:

template <typename T>
class Formatter {                                   // the general case
public:
    static std::string text(const T& value) { std::ostringstream out; out << value; return out.str(); }
};

template <>                                          // FULL specialisation: one type
class Formatter<bool> {
public:
    static std::string text(bool value) { return value ? "true" : "false"; }   // not "1"/"0"
};

template <typename T>                                // PARTIAL specialisation: a family of types
class Formatter<T*> {
public:
    static std::string text(T* value) {
        return value == nullptr ? "(null)" : "-> " + Formatter<T>::text(*value);
    }
};

Three ways to specialise behaviour, and they cost different things:

• Full specialisation (Formatter<bool>) gives one type a different implementation.
• Partial specialisation (Formatter<T*>) covers a family, with T still deduced.
• if constexpr (C++17) branches inside one implementation on a compile-time question, and the branch not taken is discarded — so it need not even be valid for that type:

template <typename T>
std::string describe(const T& value) {
    if constexpr (std::is_integral<T>::value) { return "integral: " + std::to_string(value); }
    else if constexpr (std::is_pointer<T>::value) { return "pointer " + Formatter<T>::text(value); }
    else { return "other: " + Formatter<T>::text(value); }
}

std::vector<bool> is the standard library's own famous full specialisation: it packs one bit per element, so v[0] returns a proxy object, not a bool&. Assignment through it works; taking its address does not, and the compiler says so in its own way:

error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
note:   after user-defined conversion: 'std::_Bit_reference::operator bool() const'

That is the cost of the space saving, and it is why std::vector<bool> is the container everyone is warned about. The design lesson is broader: specialising for correctness is right (a bool that prints as 1 is a bug, a packed bit vector is a deliberate trade); specialising to make one type "nicer" is not, because the general contract stops being true.

---

10. So when should I generalise?

When a second genuine use appears — not before. The cost of generalising early is real and immediate: the code is harder to read, the requirements must be documented, the errors become harder to interpret, and every user recompiles when the template changes. What you buy is flexibility that nobody has asked for.

The practical test in this course's labs: do two things use it now? Lab 11's catalogue had one container. Lab 12 has three record kinds, so the template pays for itself — and the requirements that Lab 12 asks you to document were discovered by using the repository with the second type, which is exactly the moment generalisation becomes visible as the right answer.

---

Checkpoint

1. What is a template, in one sentence? (section 2)
2. When are the two phases of template checking, and what is checked in each? (sections 3, 4 and 5: syntax and non-dependent names at definition; everything involving T at instantiation)
3. Why does a template definition normally live in a header? (section 5)
4. A class template compiles for int and fails for Book. What does that tell you about the template? (section 3: it was imposing a requirement that was never written down)
5. Name one thing a template can do that a virtual function cannot, and one it cannot do that a virtual function can. (section 7)
6. What is the first thing you do with a hundred-line template error, and what is the second? (section 8)
7. Why is generalising "in case it is needed" a bad trade? (section 10)

Next: Worked examples — six programs, each asking for a prediction before it shows you anything.