SyntaxPilot
Courses/C++/Lesson 20

C++ · Lesson 20 of 40 · 12 min

Templates

queued

These are the notes for C++ episode 20. Until now, every function and every class we wrote worked for exactly one type. Today you will feel why that hurts (a function for int that silently chops 2.9 to 2, and three copy-pasted versions that drift apart), and then invent the fix: a template, code written once with a type-shaped blank that the compiler fills in. You will write function templates, see how the compiler works out the type, fix the two errors everyone meets, build class templates (Pair<A, B>) and a template with a number as a parameter (Stack<T, N>), and see why the whole C++ Standard Template Library (STL) is built on this one idea. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; the outputs and error messages are copied from those runs.

The problem: the same question for every type

Raju runs a chai stall. Every day he asks one question: which of these two is bigger?

What he compares Example C++ type
Biscuit boxes sold Monday 3, Tuesday 7 int (whole numbers)
Sugar bags 2.5 kg vs 2.9 kg double (decimals)
Staff names Asha vs Ravi (which comes later alphabetically?) string (text)

The logic is identical every time. Only the type changes.

Attempt 1: one function for int

#include <iostream>
#include <string>
using namespace std;

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    cout << maxOf(3, 7) << endl;       // orders
    cout << maxOf(2.5, 2.9) << endl;   // kg of sugar
    return 0;
}

Output:

7
2

maxOf(3, 7) is right. maxOf(2.5, 2.9) prints 2, with no error and no warning (without -Wall). Why: the parameters are int, so C++ converts 2.5 and 2.9 to int before the call, and converting a double to an int drops the decimal part. Both become 2.

The ? : is the ternary operator (episode 3): (a > b) ? a : b means "if a > b, the value is a, otherwise b".

Attempt 2: overloading by copy-paste

Episode 7 taught function overloading: the same name with different parameter types. So we write one copy per type:

#include <iostream>
#include <string>
using namespace std;

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}
double maxOf(double a, double b) {
    return (a > b) ? a : b;
}
string maxOf(string a, string b) {
    return (a < b) ? a : b;   // copy-paste typo
}

int main() {
    string x = "Asha", y = "Ravi";
    cout << maxOf(3, 7) << endl;
    cout << maxOf(2.5, 2.9) << endl;
    cout << maxOf(x, y) << endl;
    return 0;
}

Output:

7
2.9
Asha

The int and double copies are right, but the string copy says Asha, which is wrong: "Ravi" comes after "Asha" alphabetically, so Ravi is the bigger string. A > became < while pasting. Why this approach breaks down:

  • The logic is the same, yet it is written once per type: 3 types, 3 copies; 10 types, 10 copies.
  • A bug fixed in one copy lives on in the others. Copies drift apart.
  • A new type (dates, bills, prices) means yet another copy.

The fix: a function template

Real-life example: a government form with a blank ("Name: ______"). The office writes the form once; each person fills in the blank. A template is a function with a blank, but the blank is a type, and the compiler fills it in.

template <typename T>
T maxOf(T a, T b) {
    return (a > b) ? a : b;
}
Part Meaning
template "what follows has a blank"
<typename T> the blank is a type, and it is called T (any name works; T for "type" is the habit)
T maxOf(T a, T b) wherever the type goes, write T

class can be written instead of typename here (template <class T>); for this purpose they mean the same thing.

#include <iostream>
#include <string>
using namespace std;

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

int main() {
    string x = "Asha", y = "Ravi";
    cout << maxOf(3, 7) << endl;
    cout << maxOf(2.5, 2.9) << endl;
    cout << maxOf(x, y) << endl;
    return 0;
}

Output:

7
2.9
Ravi

All three are right, from one definition. A bug now has exactly one place to be fixed.

Template argument deduction

How did C++ know T is int, then double, then string? It looked at the arguments. 3 and 7 are int, so T = int. This is template argument deduction: the compiler deduces (works out) the template's type from the arguments you pass.

When deduction fails: conflicting types

#include <iostream>
#include <string>
using namespace std;

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

int main() {
    cout << maxOf(3, 4.5) << endl;
    return 0;
}

g++ says:

error: no matching function for call to 'maxOf(int, double)'
note: candidate: 'template<class T> T maxOf(T, T)'
note:   template argument deduction/substitution failed:
note:   deduced conflicting types for parameter 'T' ('int' and 'double')

Why: both parameters are T, so they must be the same type. From 3, T would be int; from 4.5, double. The compiler refuses to guess. Fix: fill in the blank yourself with explicit template arguments:

#include <iostream>
#include <string>
using namespace std;

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

int main() {
    cout << maxOf<double>(3, 4.5) << endl;
    return 0;
}

Output:

4.5

With T = double, 3 is converted to 3.0 and the comparison is fair.

A template needs every operation it uses

#include <iostream>
#include <string>
using namespace std;

struct Bill {
    string table;
    double amount;
};

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

int main() {
    Bill t1 = {"Table 1", 240}, t2 = {"Table 2", 380};
    Bill big = maxOf(t1, t2);
    cout << big.table << ": Rs. " << big.amount << endl;
    return 0;
}

g++ says (first lines; it then lists many other operator> candidates it tried):

In instantiation of 'T maxOf(T, T) [with T = Bill]':
  required from here
error: no match for 'operator>' (operand types are 'Bill' and 'Bill')
    |     return (a > b) ? a : b;

Why: the template uses a > b. For int, double and string, > exists. For a Bill, C++ doesn't know what "bigger" means. A template works only for types that support everything it uses. Fix: give Bill an operator> (episode 17, operator overloading):

#include <iostream>
#include <string>
using namespace std;

struct Bill {
    string table;
    double amount;
    bool operator>(const Bill& o) const {
        return amount > o.amount;
    }
};

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

int main() {
    Bill t1 = {"Table 1", 240}, t2 = {"Table 2", 380};
    Bill big = maxOf(t1, t2);
    cout << big.table << ": Rs. " << big.amount << endl;
    return 0;
}

Output:

Table 2: Rs. 380

Tip: when a template error is long, read the first error: line and the In instantiation of ... [with T = ...] line above it. They tell you which type was filled in and what it was missing.

Instantiation: what the compiler really makes

A template is not code yet: it is a recipe. When you call maxOf with ints, the compiler writes a real int version; with doubles, a double version; with Bill, a Bill version.

                 +--> maxOf<int>     (maxOf(3, 7))
template maxOf<T> +--> maxOf<double>  (maxOf(2.5, 2.9))
                 +--> maxOf<string>  (maxOf(x, y))
                 +--> maxOf<Bill>    (maxOf(t1, t2))
  • Making a real function (or class) from a template is called instantiation; the result is an instantiation (or a specialization) of the template.
  • Each type you use gets one instantiation; types you never use produce no code at all.
  • Errors appear only when a filled-in type doesn't fit (as with Bill before it had >).
  • All of this happens at compile time, so a template runs exactly as fast as code you typed by hand.
  • Because the compiler needs the whole recipe to fill in the blank, templates are normally written entirely in header files (.h), not split into a .h and a .cpp like ordinary functions.

Class templates: Pair

The next problem is data. Three things that belong together:

Thing Values Types
Result card Asha, 92 string, int
Weather report Delhi, 31.5 string, double
Train ticket seat 42, berth B int, char

Three structs (NameMarks, CityTemp, SeatBerth) with the same shape would be copy-paste again. A class template puts the blanks on a class. This one has two blanks, A and B:

#include <iostream>
#include <string>
using namespace std;

template <typename A, typename B>
class Pair {
    A first;
    B second;
public:
    Pair(A a, B b) : first(a), second(b) {}
    A getFirst() const { return first; }
    B getSecond() const { return second; }
    void show() const;
};

template <typename A, typename B>
void Pair<A, B>::show() const {
    cout << "(" << first << ", " << second << ")" << endl;
}

int main() {
    Pair<string, int> asha("Asha", 92);
    Pair<string, double> delhi("Delhi", 31.5);
    Pair<int, char> seat(42, 'B');
    asha.show();
    delhi.show();
    seat.show();
    cout << asha.getFirst() << " scored " << asha.getSecond() << endl;
    return 0;
}

Output:

(Asha, 92)
(Delhi, 31.5)
(42, B)
Asha scored 92
  • For a class template you usually write the types yourself: Pair<string, int>. (Since C++17 the compiler can sometimes deduce them from the constructor, called class template argument deduction, but writing them is clearer while learning.)
  • Pair<string, int> and Pair<int, char> are different types, both made from one template.

Defining a member outside the class

If you define show() outside the class without the template line:

void Pair<A, B>::show() const {
    cout << "(" << first << ", " << second << ")" << endl;
}

g++ says:

error: 'A' was not declared in this scope
error: 'B' was not declared in this scope
error: template argument 1 is invalid

Why: the names A and B exist only inside the template they belong to. A member defined outside is a separate piece of code, so it needs its own template <typename A, typename B> line above it (as in the working program).

A number as a blank: Stack

Real-life example: a rack of plates. You put a plate on top and take from the top: the last one on is the first one off. That is a stack (Last In, First Out, LIFO). The rack holds 3 plates: the size is part of what the rack is. A template blank can be a number, a non-type template parameter like int N:

#include <iostream>
#include <string>
using namespace std;

template <typename T, int N>
class Stack {
    T items[N];
    int count = 0;
public:
    bool push(T x) {
        if (count == N) return false;
        items[count++] = x;
        return true;
    }
    T pop() { return items[--count]; }
    bool empty() const { return count == 0; }
};

int main() {
    Stack<string, 3> plates;
    string names[] = {"red", "blue", "green", "gold"};
    for (string p : names)
        cout << p << (plates.push(p) ? " stacked" : " REFUSED: full") << endl;
    while (!plates.empty())
        cout << "take " << plates.pop() << endl;
    Stack<int, 100> tokens;
    tokens.push(42);
    cout << "token " << tokens.pop() << endl;
    return 0;
}

Output:

red stacked
blue stacked
green stacked
gold REFUSED: full
take green
take blue
take red
token 42
  • push refuses the 4th plate because count == N.
  • Plates come off in reverse order: green, blue, red.
  • Stack<string, 3> and Stack<int, 100> are two different types. N must be known at compile time (a literal or a const/constexpr value), because it sets the array's size.

Where templates take you: the STL

The STL (Standard Template Library) is the collection of ready-made templates that ships with C++. Over the next episodes we open them one by one:

STL template What it is Episode
vector<T> a list that grows by itself 21
deque<T>, list<T> fast adds at both ends / in the middle 22
map<K, V>, set<T> sorted key-value pairs / unique values 23
unordered_map<K, V>, unordered_set<T> hash-based lookup 24
stack<T>, queue<T>, priority_queue<T> like our plate rack, and more 25
sort, max, find, ... function templates (algorithms) 27
pair<A, B> the real version of our Pair 23

Common mistakes (and the real g++ messages)

Mistake Code What g++ says / what happens Fix
Mixing types for one T maxOf(3, 4.5) error: no matching function for call to 'maxOf(int, double)' ... deduced conflicting types for parameter 'T' ('int' and 'double') maxOf<double>(3, 4.5)
A type without the operator the template uses maxOf(t1, t2) with a plain struct Bill error: no match for 'operator>' (operand types are 'Bill' and 'Bill') give Bill an operator>
Out-of-class member without its template line void Pair<A, B>::show() const {...} error: 'A' was not declared in this scope template <typename A, typename B> above it
A function for int called with decimals maxOf(2.5, 2.9) with int maxOf(int, int) no message: prints 2 a template, so T = double
Copy-pasted overloads string maxOf(...) { return (a < b) ? a : b; } no message: wrong answer Asha in one copy only one template instead of copies
Comparing string literals maxOf("apple", "mango") T becomes const char*, so it compares addresses, not text maxOf(string("apple"), string("mango"))

Mini project: Raju's weekly board

One function template finds the largest element of any array, and another prints any array with a label. Both work for int, double and string:

#include <iostream>
#include <string>
using namespace std;

template <typename T>
T largest(T arr[], int n) {
    T best = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > best) best = arr[i];
    return best;
}

template <typename T>
void showAll(string label, T arr[], int n) {
    cout << label << ":";
    for (int i = 0; i < n; i++) cout << " " << arr[i];
    cout << "  -> largest " << largest(arr, n) << endl;
}

int main() {
    int orders[] = {3, 7, 5, 12, 9, 4, 6};
    double sugar[] = {2.5, 2.9, 1.75};
    string staff[] = {"Asha", "Ravi", "Meena", "Kabir"};
    showAll("Orders this week", orders, 7);
    showAll("Sugar bags (kg)", sugar, 3);
    showAll("Staff", staff, 4);
    return 0;
}

Output:

Orders this week: 3 7 5 12 9 4 6  -> largest 12
Sugar bags (kg): 2.5 2.9 1.75  -> largest 2.9
Staff: Asha Ravi Meena Kabir  -> largest Ravi

Note that showAll calls largest: one template using another, both instantiated for each type.

Practice

  1. Write a minOf template and test it with int, double and string.
  2. Write swapThem(T& a, T& b) and swap two strings and two ints.
  3. Add a peek() to Stack<T, N> that returns the top item without removing it.
  4. Write a Triple<A, B, C> class template with a show() defined outside the class.
Solutions

1. The same template as maxOf, with <:

#include <iostream>
#include <string>
using namespace std;

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

int main() {
    string x = "Asha", y = "Ravi";
    cout << minOf(3, 7) << endl;
    cout << minOf(2.5, 2.9) << endl;
    cout << minOf(x, y) << endl;
    return 0;
}
3
2.5
Asha

2. References (T&) let the function change the caller's variables:

#include <iostream>
#include <string>
using namespace std;

template <typename T>
void swapThem(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

int main() {
    string first = "chai", second = "coffee";
    swapThem(first, second);
    cout << first << " " << second << endl;
    int p = 1, q = 2;
    swapThem(p, q);
    cout << p << " " << q << endl;
    return 0;
}
coffee chai
2 1

3. peek() reads items[count - 1] without changing count (const, because it doesn't modify the stack):

#include <iostream>
#include <string>
using namespace std;

template <typename T, int N>
class Stack {
    T items[N];
    int count = 0;
public:
    bool push(T x) {
        if (count == N) return false;
        items[count++] = x;
        return true;
    }
    T pop() { return items[--count]; }
    T peek() const { return items[count - 1]; }
    bool empty() const { return count == 0; }
};

int main() {
    Stack<string, 3> plates;
    plates.push("red");
    plates.push("blue");
    cout << "top: " << plates.peek() << endl;
    cout << "take " << plates.pop() << endl;
    cout << "top: " << plates.peek() << endl;
    return 0;
}
top: blue
take blue
top: red

4. Three blanks, and the out-of-class show() repeats the template line. A bool prints as 1:

#include <iostream>
#include <string>
using namespace std;

template <typename A, typename B, typename C>
class Triple {
    A first;
    B second;
    C third;
public:
    Triple(A a, B b, C c) : first(a), second(b), third(c) {}
    void show() const;
};

template <typename A, typename B, typename C>
void Triple<A, B, C>::show() const {
    cout << "(" << first << ", " << second << ", " << third << ")" << endl;
}

int main() {
    Triple<string, int, char> ticket("Asha", 42, 'B');
    Triple<string, double, bool> city("Delhi", 31.5, true);
    ticket.show();
    city.show();
    return 0;
}
(Asha, 42, B)
(Delhi, 31.5, 1)

Quick quiz

What does this print?

#include <iostream>
#include <string>
using namespace std;

template <typename T>
T twice(T x) {
    return x + x;
}

int main() {
    string s = "ab";
    cout << twice(5) << " " << twice(s) << " " << twice(2.5);
    return 0;
}
  1. 10 abab 5
  2. 10 ab 5
  3. 10 abab 2.5
  4. Compile error
Answer

1: 10 abab 5. Each call makes its own instantiation. int: 5 + 5 = 10. string: + joins strings, so "ab" + "ab" = "abab". double: 2.5 + 2.5 = 5.0, and cout prints 5.0 as 5.

10 abab 5

Interview questions

  1. What is a template in C++? A blueprint for a function or class with one or more parameters (usually types) that the compiler fills in at compile time to generate real code.
  2. Function template vs class template? A function template generates functions (maxOf<int>); a class template generates classes (Pair<string, int>). Function template arguments are usually deduced from the call; class template arguments are usually written explicitly (C++17 can deduce some from constructors).
  3. What is template argument deduction? The compiler working out the template parameters from the types of the function arguments. It fails when the same parameter would need two different types (maxOf(3, 4.5)).
  4. What is instantiation? Generating a concrete function or class from a template for specific arguments. Only the types actually used are instantiated.
  5. Do templates slow a program down? No. All the work happens at compile time; the generated code is as fast as hand-written code. The cost is longer compile times and larger binaries if many types are used.
  6. Why are templates usually defined in header files? The compiler needs the full definition to instantiate a template wherever it is used, so it can't be compiled separately in a .cpp file like an ordinary function.
  7. What is a non-type template parameter? A template parameter that is a value, not a type, such as int N in Stack<T, N>. It must be a compile-time constant.
  8. typename vs class in template <...>? For declaring a type parameter they are interchangeable.
  9. Templates vs overloading vs virtual functions? Overloading: separate hand-written functions per type. Templates: one definition, the compiler generates per type at compile time (compile-time polymorphism). Virtual functions: one call that picks the right override at run time (run-time polymorphism).

Glossary

Term Meaning Example
Template Code with blanks (usually types) that the compiler fills in template <typename T> T maxOf(T a, T b)
Template parameter A blank in a template T, A, B, N
typename Declares that a template parameter is a type template <typename T>
Function template A template that generates functions maxOf<T>
Class template A template that generates classes Pair<A, B>, Stack<T, N>
Template argument The actual type or value that fills a blank int in maxOf<int>
Template argument deduction The compiler working out template arguments from the call's arguments maxOf(3, 7) → T = int
Explicit template argument Filling the blank yourself in angle brackets maxOf<double>(3, 4.5)
Instantiation Generating a real function or class from a template for given arguments maxOf<Bill>
Non-type template parameter A template parameter that is a compile-time value int N in Stack<T, N>
Ternary operator cond ? x : y: x if the condition is true, else y (a > b) ? a : b
Function overloading Several functions with one name and different parameter types int maxOf(int, int), double maxOf(double, double)
Operator overloading Defining what an operator means for your own type bool operator>(const Bill& o) const
Stack A collection where the last item added is the first removed (LIFO) a rack of plates
LIFO Last In, First Out push red, blue; pop gives blue
STL Standard Template Library: C++'s ready-made templates (containers and algorithms) vector<int>, sort
Compile time When the compiler turns your code into a program, before it runs template instantiation
Generic programming Writing code once so it works for many types templates

Summary

  • One function per type either chops values (int maxOf with 2.9 → 2) or creates copies that drift apart (a < typo in one overload).
  • A template is code written once with a type-shaped blank: template <typename T>. The compiler fills it in.
  • Deduction: the compiler reads T from the arguments. If it gets conflicting types, fill the blank yourself: maxOf<double>(3, 4.5).
  • A template needs every operation it uses: no match for 'operator>' means your type is missing one; overload it.
  • Instantiation: one real copy per type used, made at compile time, so templates cost nothing at run time.
  • Class templates (Pair<A, B>) put blanks on a class; members defined outside need their own template line.
  • Blanks can be numbers too: Stack<T, N>.
  • The STL is a library of templates. Next episode: the first one, vector.