Templates, the Idea: One Function, Every Type

In C, Amara needed the larger of two numbers three times last term: for marks, for prices and for distances. So she wrote max_int, max_double and max_ll, three functions with the same body. In C++ she writes std::max and never writes the body at all. The trick behind it is called a template, and every container and algorithm in this track is one.

Three max functions in C, one in C++

Here is the C way. The bodies are identical; only the types differ, and C needs a separate name for each.

#include <stdio.h>

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

double max_double(double a, double b)
{
    return a > b ? a : b;
}

long long max_ll(long long a, long long b)
{
    return a > b ? a : b;
}

int main(void)
{
    printf("%d\n", max_int(3, 7));
    printf("%.2f\n", max_double(2.5, 1.25));
    printf("%lld\n", max_ll(4000000000LL, 3000000000LL));
    return 0;
}

7
2.50
4000000000

And here is C++, with one name for all of them, strings included.

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::cout << std::max(3, 7) << '\n';
    std::cout << std::max(2.5, 1.25) << '\n';
    std::cout << std::max(4000000000LL, 3000000000LL) << '\n';
    std::cout << std::max(std::string("pear"), std::string("apple")) << '\n';
    return 0;
}

7
2.5
4000000000
pear

std::max lives in the header <algorithm>. For two strings it returns the one a dictionary lists later, so "pear" beats "apple". So one name, std::max, does the work of three C functions and a fourth C never had.

A template is a recipe with a blank for the type

A template is code written once with a blank where a type goes. The standard library wrote max as "compare two values of some type T with <, return the larger". When you call it on two int values, T is filled in with int.

For a function template the compiler usually works out T from the arguments, as above. For a container you name the type yourself, in angle brackets. Read <...> as "filled in with".

std::vector<int>                  a vector, filled in with int
std::vector<std::string>          a vector, filled in with string
std::map<std::string, int>        a map, filled in with string keys and int values
std::pair<std::string, int>       a pair, filled in with a string and an int
std::max(3, 7)                    max, with T worked out as int

So std::vector<long long>, which you met in lesson 04, is one recipe, "vector", filled in with one type, long long.

What the compiler does with a template

A template is not code the machine can run. It is a pattern the compiler copies out, with the blank filled in, the first time a program asks for that type. The filled-in copy is called an instantiation. Ask for max on int, double and std::string, and the compiler writes three ordinary functions.

This is not a figure of speech. Compile a program that calls std::max on those three types on Compiler Explorer with GCC 12, optimisation off (-O0). The assembly listing names three separate functions: std::max<int>(int const&, int const&), std::max<double>(double const&, double const&) and one for std::string. At the Playground's -O2 they disappear: each one is so small that GCC 12 copies its body straight into main.

A class template works the same way. std::vector<int> and std::vector<std::string> are two different types the compiler wrote from one recipe. They do not mix: assigning one to the other gets error: no match for 'operator=' (operand types are 'std::vector<int>' and 'std::vector<std::__cxx11::basic_string<char> >') from GCC 12. The odd std::__cxx11::basic_string<char> is the real name of std::string in GCC's library, and you will meet it in many messages.

One honest line about scope. This track reads and uses templates: every container, every algorithm. Writing your own template, with the word template and a T of your own, belongs to the C++ track. So in this track the compiler writes the instantiations, and your job is to fill in the types and read its messages.

std::max, std::min and std::swap on any type

Three small templates turn up in almost every program. std::max and std::min return the larger and the smaller of two values. std::swap exchanges two variables, through references, exactly like Maria's swapRef in lesson 03.

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    int a = 4;
    int b = 9;
    std::cout << "max " << std::max(a, b) << ", min " << std::min(a, b) << '\n';
    std::cout << "max of three " << std::max({a, b, 2}) << '\n';

    std::swap(a, b);
    std::cout << "after swap: a = " << a << ", b = " << b << '\n';

    std::string first = "Kenji";
    std::string second = "Amara";
    std::swap(first, second);
    std::cout << first << ' ' << second << '\n';
    return 0;
}

max 9, min 4
max of three 9
after swap: a = 9, b = 4
Amara Kenji

Each of the three has one rule. std::max and std::min need two values of the same type that can be compared with <. For more than two, put them in braces: std::max({a, b, 2}) takes a whole list. std::swap needs two variables of the same type, never a plain number, because it writes through references.

So one template call works on int, double, std::string and every other type that has a <, and the compiler writes the version you need.

Reading a template error: the one line that matters

A mistake inside a template call can make GCC 12 print dozens of lines for one error. They are not dozens of problems. The compiler is listing every version of the function it tried and why each failed. One or two lines tell you what is wrong, and the rest is the search.

The rule for finding them has three steps.

1. Find the first line that names your file and says error:. Files inside the compiler's own folders (paths ending in bits/stl_algobase.h and the like) are the library, not you.
2. If the first error: is inside a library file, look just above it for required from here. The line with that phrase names your file and your line.
3. Read the note: that gives a reason in plain words: "deduced conflicting types", "no known conversion", "no match for 'operator<'". Skip the notes that only list candidates.

Here are three real errors, each from GCC 12 at the Playground's command line, -O2 -std=c++17. Compiler Explorer names your file <source>; the long paths into the compiler's own files are cut to their last part here.

Gallery 1: two types where one is needed. Kenji keeps a running total as long long and wants it never below zero.

long long total = 0;
long long best = std::max(total, 0);

GCC 12 prints over 30 lines. The two to read:

<source>:7:30: error: no matching function for call to 'max(long long int&, int)'
<source>:7:30: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')

The first names the call and the two types it got. The note says why: _Tp is the library's name for the blank, and it cannot be long long and int at once. The fix is to make both the same type: std::max(total, 0LL), where LL makes the zero a long long.

Gallery 2: a type with no <. Maria stores parcels as a C struct and asks for the heavier one.

struct Parcel {
    int weight;
    int price;
};

Parcel a = {3, 120};
Parcel b = {5, 80};
Parcel heavier = std::max(a, b);

GCC 12 prints over 40 lines, and the first error: is inside the library. Step 2 finds your line:

.../bits/stl_algobase.h: In instantiation of 'constexpr const _Tp& std::max(const _Tp&, const _Tp&) [with _Tp = Parcel]':
<source>:13:30:   required from here
.../bits/stl_algobase.h:259:15: error: no match for 'operator<' (operand types are 'const Parcel' and 'const Parcel')

[with _Tp = Parcel] says which instantiation broke. required from here points at line 13, your call. The error says the reason: std::max compares with <, and nobody said what "less" means for a parcel. Heavier by weight? Cheaper by price? The compiler cannot guess. Compare the field you mean, std::max(a.weight, b.weight); Module 12 shows how to hand an algorithm your own rule.

Gallery 3: the wrong type into a container. Bob puts a name into a list of marks.

std::vector<int> marks = {70, 85};
std::string name = "Zara";
marks.push_back(name);

GCC 12 prints about 20 lines. The two to read:

<source>:9:20: error: no matching function for call to 'std::vector<int>::push_back(std::string&)'
.../bits/stl_vector.h:1276:35: note:   no known conversion for argument 1 from 'std::string' {aka 'std::__cxx11::basic_string<char>'} to 'const std::vector<int>::value_type&' {aka 'const int&'}

push_back adds one element at the end (Module 2). The note says it wanted a const int&, because this vector was filled in with int, and got a std::string. The {aka ...} parts translate the library's names into plain ones. The fix depends on what Bob meant: a second vector for names, or a pair of name and mark (lesson 06).

So a 50-line template error is one mistake and a long search. Your file's first error:, or the required from here above the library's, plus one reason note, is all you need to read.

#include <algorithm>
#include <iostream>

int main()
{
    int a = 0;
    int b = 0;
    std::cin >> a >> b;

    std::cout << "higher " << std::max(a, b) << ", lower " << std::min(a, b) << '\n';
    return 0;
}

higher 85, lower 72

#include <algorithm>
#include <iostream>

int main()
{
    int readings[3] = {25, -55, 70};

    for (int& t : readings) {
        t = std::min(std::max(t, -40), 60);
    }
    std::cout << readings[0] << ' ' << readings[1] << ' ' << readings[2] << '\n';
    return 0;
}

25 -40 60

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    int n = 0;
    std::cin >> n;

    std::string title;
    int price = 0;
    std::cin >> title >> price;

    std::string firstTitle = title;
    std::string lastTitle = title;
    int cheapest = price;
    int dearest = price;

    for (int i = 1; i < n; i++) {
        std::cin >> title >> price;
        firstTitle = std::min(firstTitle, title);
        lastTitle = std::max(lastTitle, title);
        cheapest = std::min(cheapest, price);
        dearest = std::max(dearest, price);
    }
    std::cout << "prices " << cheapest << " to " << dearest << '\n';
    std::cout << "titles " << firstTitle << " to " << lastTitle << '\n';
    return 0;
}

prices 120 to 450
titles Dracula to Ulysses

std::cout << std::max(a, b, c) << '\n';

std::vector v;

long long smallest = 5000000000LL;
smallest = std::min(smallest, 1000000000);

std::swap(a, 5);

#include <algorithm>
#include <iostream>

int main()
{
    double best = 4.5;
    best = std::max(best, 3.0);
    std::cout << best << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>

int main()
{
    double a = 0;
    double b = 0;
    double c = 0;
    std::cin >> a >> b >> c;

    // Use std::min and std::max to find the fastest and the slowest lap.

    return 0;
}

#include <iostream>
#include <string>
#include <utility>

int main()
{
    std::string first;
    std::string second;
    std::cin >> first >> second;

    // The long way: swap first and second with a third string, then print.

    // The short way: swap them back with std::swap, then print again.

    return 0;
}

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 0;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        std::string type;
        int k = 0;
        std::cin >> type >> k;

        // type is "int", "double" or "string". Read the k values into
        // variables of that type, keep the largest with std::max,
        // and print it on its own line.
    }
    return 0;
}

Next, lesson 06 fills in a template with two types at once: std::pair, and its bigger sibling std::tuple.