Generic functions

Why this matters

Programs often need the same idea for different kinds of data. You might want to square a whole number, square a decimal number, and find the larger of two words. Without templates, you write a separate function for each type. The copies look almost the same, and each copy is a place for a mistake. If you later fix a bug in one copy, you must remember to fix the others.

A function template is one function written once, with a placeholder for the type. The compiler fills in the real type at each call. One template can work for int, double, std::string, and any other type that supports the operations the body uses.

This lesson covers function templates only. Class templates, which the standard containers such as std::vector are built from, come later in the course. Here std::vector appears only as something a function receives.

Define the terms

• Type. A kind of value. int holds whole numbers, double holds decimal numbers, and std::string holds text.
• Function template. A function with a type placeholder. You write the placeholder as T (the letter is a convention, not a rule) and put template <typename T> on the line above the function.
• Type parameter. The placeholder itself, such as T.
• Type deduction. The compiler reads the types of the arguments and works out what T must be. You usually do not write the type yourself.
• Argument. A value you pass into a function when you call it. In square(4), the argument is 4.
• Instantiation. The compiler's step of making a real function from the template for one type. You never see this in your source. It happens when you call the function.
• Compile error. A message from the compiler that stops the program from building. The program does not run at all.
• Operator. A symbol that does a job. + adds, * multiplies, and < checks whether the left side is smaller.
• std::vector. A standard library type that holds a list of items of one type. std::vector<int> holds ints. You need #include <vector> to use it.

The problem without templates

Suppose you need a function that squares a number. You could write one for each type:

int square_int(int value) {
    return value * value;
}
 
double square_double(double value) {
    return value * value;
}

The two bodies are identical. Only the type names differ. This is the cost of copies: the same work is written twice, and any change must be made twice.

Your first template

A template writes the body once:

template <typename T>
T square(T value) {
    return value * value;
}

Read it from top to bottom. The first line says the next thing is a template with one type parameter named T. The second line says the function takes one value of type T and returns a value of type T. The body multiplies the value by itself, the same as the two copies above.

When you call square, the compiler looks at the argument and decides what T means:

square(4)      the argument is an int, so T is int
square(2.5)    the argument is a double, so T is double
square(7L)     the argument is a long, so T is long

Here is a complete program that uses the template three times:

#include <iostream>
 
template <typename T>
T square(T value) {
    return value * value;
}
 
int main() {
    std::cout << square(4) << '\n';
    std::cout << square(2.5) << '\n';
    std::cout << square<long long>(100000) << '\n';
}

Compile it with the course command and run it:

g++ -std=c++20 -Wall -o square square.cpp
./square

The output is:

16
6.25
10000000000

The first two calls use type deduction. The third call writes the type inside angle brackets, square<long long>. This is an explicit type argument. It tells the compiler which T to use, even if the argument could be read another way. Here it matters. The number 100000 is an int on most systems, and 100000 * 100000 is 10000000000, which is too large for a 32-bit int. Writing <long long> makes the function work with a type that can hold the answer. The variables lessons in this course cover the size limits of each type.

Example 1: square

The template did the same work for an int and for a double. For square(2.5), the argument 2.5 is a double, so the compiler makes a version of square that multiplies two doubles. The result, 6.25, is printed. The source code never mentions double. One piece of code produced two working functions.

Example 2: the larger of two values

The next template takes two values of the same type and returns the larger one. It needs < to work for its type.

#include <iostream>
#include <string>
 
template <typename T>
T larger(T a, T b) {
    if (a < b) {
        return b;
    }
    return a;
}
 
int main() {
    std::cout << larger(3, 9) << '\n';
    std::cout << larger(2.5, 1.5) << '\n';
    std::string first = "apple";
    std::string second = "banana";
    std::cout << larger(first, second) << '\n';
}

The output is:

9
2.5
banana

The same body runs for numbers and for text. For std::string, the < operator compares the words in dictionary order, so "banana" is larger than "apple". The template does not check which type it got. It only needs < to exist for that type. If it does not, the compile fails. The mistakes section shows that error.

Both arguments must have the same type. The template says T a, T b, so the two values must agree on what T is.

Example 3: total of a list

The third example takes a list of items. The parameter type is std::vector<T>, so the template reads the element type from the list you pass in.

#include <iostream>
#include <string>
#include <vector>
 
template <typename T>
T total(const std::vector<T>& items) {
    T sum{};
    for (const T& item : items) {
        sum = sum + item;
    }
    return sum;
}
 
int main() {
    std::vector<int> ages = {18, 21, 35};
    std::vector<double> prices = {1.25, 2.50, 0.75};
    std::vector<std::string> words = {"fast", "clean", "code"};
 
    std::cout << total(ages) << '\n';
    std::cout << total(prices) << '\n';
    std::cout << total(words) << '\n';
}

The output is:

74
4.5
fastcleancode

Three details in this code matter.

The parameter const std::vector<T>& items says: a list whose items have type T. When you pass ages, the compiler matches the pattern against std::vector<int> and finds that T is int. You never write T at the call.

The line T sum{}; creates the running total. The empty braces start the variable with the default value for its type. For int that is 0. For double it is 0.0. For std::string it is an empty string. A plain T sum; would leave a number with an unknown value, so the braces are the safe choice.

The loop uses const T& item. The & makes the loop look at each item in the list directly, without making a copy. The const promises the loop will not change the item. The pass-by-value and reference lesson earlier in this module explains the & in detail.

The same template joins strings because + joins two std::string values. It adds numbers because + adds two numbers. The body is written once, and the operator decides what the addition means.

Trace one call

Here is total(prices) step by step.

1. The argument has type std::vector<double>, so T is double.
2. sum starts at 0.0.
3. The first item is 1.25. The sum becomes 1.25.
4. The second item is 2.50. The sum becomes 3.75.
5. The third item is 0.75. The sum becomes 4.5.
6. The function returns 4.5, which is printed.

Tracing a template call is the same as tracing a normal function. The only extra step is working out T first.

Example 4: finding a position

The last worked example returns a position instead of a value. It searches a list for a target and returns the index of the first match. An index is the position of an item in a list, counted from 0 for the first item. The function needs a way to say "not found", so it returns items.size(), which is one past the last valid index. A std::size_t is an unsigned integer type, which means it cannot hold a negative number. The standard library uses it for sizes and positions.

#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
 
template <typename T>
std::size_t find_index(const std::vector<T>& items, const T& target) {
    for (std::size_t i = 0; i < items.size(); i++) {
        if (items[i] == target) {
            return i;
        }
    }
    return items.size();
}
 
int main() {
    std::vector<int> scores = {70, 85, 92};
    std::vector<std::string> colors = {"red", "green", "blue"};
 
    std::cout << find_index(scores, 85) << '\n';
    std::cout << find_index(colors, std::string("blue")) << '\n';
    std::cout << find_index(colors, std::string("pink")) << '\n';
}

The output is:

1
2
3

Trace the first call. T is int, so items is a std::vector<int> and target is 85. The loop checks index 0, which holds 70. That is not a match. It checks index 1, which holds 85. That matches, so the function returns 1. The third call searches for "pink", which is not in the list, so the function returns items.size(), which is 3.

The == operator checks whether two values are equal. Like <, it has to exist for T. Both int and std::string have it.

The target parameter is a const T&, and that matters for the next call. Writing a text literal such as "blue" directly does not work here. The literal has a different type from std::string, so the compiler finds two types for T:

find_err.cpp:18:28: error: no matching function for call to ‘find_index(std::vector<std::__cxx11::basic_string<char> >&, const char [5])’
find_err.cpp:18:28: note:   deduced conflicting types for parameter ‘const T’ (‘std::__cxx11::basic_string<char>’ and ‘char [5]’)

The fix is the same as before: wrap the literal in std::string(...), as the main function above does.

Where a template lives

The compiler needs the full body of a template to make a version of it for each type. Programs with several files usually put templates in a header file, a file ending in .h or .hpp that each calling file includes with #include. All the examples in this lesson fit in one file, so the question does not come up yet.

Common mistakes

Forgetting the template line

The compiler needs the template <typename T> line to know that T is a placeholder. Without it, T is an unknown name.

#include <iostream>
 
T square(T value) {
    return value * value;
}
 
int main() {
    std::cout << square(3) << '\n';
}

The compiler reports:

gen_err4.cpp:3:1: error: ‘T’ does not name a type
gen_err4.cpp:8:18: error: ‘square’ was not declared in this scope

The first message points at the placeholder. The second is a result of the first. When the first error is about a name that should be a type, look above the function for the missing template line.

Two different types in one call

Each template parameter has one type for one call. The next call passes an int and a double to the same T.

#include <iostream>
 
template <typename T>
T larger(T a, T b) {
    if (a < b) {
        return b;
    }
    return a;
}
 
int main() {
    std::cout << larger(1, 2.5) << '\n';
}

The compiler reports:

gen_err1.cpp:12:24: error: no matching function for call to ‘larger(int, double)’
gen_err1.cpp:4:3: note: template argument deduction/substitution failed:
gen_err1.cpp:12:24: note:   deduced conflicting types for parameter ‘T’ (‘int’ and ‘double’)

The note says the compiler saw two answers for T: int from the first argument and double from the second. There are two ways out. Make both arguments the same type, such as 1.0 and 2.5. Or name the type yourself with larger<double>(1, 2.5). In a test run, larger<double>(2, 2.0) printed 2, because the number is converted to double and then printed as 2.

A type that lacks the needed operator

The template body uses <. A type you define yourself does not have < unless you write it. Here is a small struct that holds a card rank:

#include <iostream>
 
struct Card {
    int rank;
};
 
template <typename T>
T larger(T a, T b) {
    if (a < b) {
        return b;
    }
    return a;
}
 
int main() {
    Card x{3};
    Card y{5};
    Card z = larger(x, y);
    std::cout << z.rank << '\n';
}

The compiler reports this, shortened:

gen_err2.cpp: In instantiation of ‘T larger(T, T) [with T = Card]’:
gen_err2.cpp:18:20:   required from here
gen_err2.cpp:9:11: error: no match for ‘operator<’ (operand types are ‘Card’ and ‘Card’)

The message names the type, Card, and the missing operator, <. It points at line 9, inside the template, and at line 18, where the call was made. To fix it, compare the field the program cares about, such as a.rank < b.rank, or define < for Card yourself.

Wrong number of type names

Writing an explicit type argument must match the template's parameter count. square has one type parameter, so one name is allowed.

#include <iostream>
 
template <typename T>
T square(T value) {
    return value * value;
}
 
int main() {
    std::cout << square<int, int>(3) << '\n';
}

The compiler reports:

gen_err3.cpp:9:34: error: no matching function for call to ‘square<int, int>(int)’
gen_err3.cpp:9:34: note: there is 1 candidate
gen_err3.cpp:4:3: note: candidate 1: ‘template<class T> T square(T)’
gen_err3.cpp:4:3: note: template argument deduction/substitution failed:
gen_err3.cpp:9:34: error: wrong number of template arguments (2, should be 1)
gen_err3.cpp:4:3: note: provided for ‘template<class T> T square(T)’

The line that says wrong number of template arguments (2, should be 1) gives the rule in plain words: two names were given, and one was expected.

Text in quotes is not a std::string

A string written in double quotes, such as "apple", has a different type from std::string. It is a pointer to the first letter in memory. A pointer is a value that holds the memory address of another value. When the template compares two of them with <, it compares their addresses, not the words.

#include <iostream>
 
template <typename T>
T larger(T a, T b) {
    if (a < b) {
        return b;
    }
    return a;
}
 
int main() {
    std::cout << larger("apple", "banana") << '\n';
}

The program compiles without a warning under -Wall. On the build used to test this lesson, it printed apple, which is not the larger word. Another build may print banana, because the answer depends on where the compiler placed the two strings in memory. The program has no error to point at, so the fix is to make the words std::string values:

std::cout << larger(std::string("apple"), std::string("banana")) << '\n';

On the same build this prints banana.

Practice

Each exercise is followed by its answer. Try the exercise on your own first, then compare.

Exercise 1. Write a template twice that takes one value and returns that value added to itself. Call it with 4, with 1.5, and with std::string("ab"). What does each call print?

Show the answer

#include <iostream>
#include <string>
 
template <typename T>
T twice(T value) {
    return value + value;
}
 
int main() {
    std::cout << twice(4) << '\n';
    std::cout << twice(1.5) << '\n';
    std::cout << twice(std::string("ab")) << '\n';
}

The output is 8, then 3, then abab. The value 1.5 plus 1.5 is 3.0, which std::cout prints as 3.

Exercise 2. Write a template smallest that takes two values of the same type and returns the smaller one. Call it with the characters 'z' and 'b'. What does it print?

Show the answer

template <typename T>
T smallest(T a, T b) {
    if (b < a) {
        return b;
    }
    return a;
}

With smallest('z', 'b'), T is char. The check b < a is 'b' < 'z', which is true, so the function returns 'b'. The program prints b.

Exercise 3. The function below is meant to total a list of doubles, but it is written with int sum = 0; instead of T sum{};. Call it with std::vector<double>{1.5, 2.25}. What does it print, and why?

template <typename T>
T total_wrong(const std::vector<T>& items) {
    int sum = 0;
    for (const T& item : items) {
        sum = sum + item;
    }
    return sum;
}

Show the answer

It prints 3. The running total is an int, so each addition drops the decimal part. The first step is 0 + 1.5, which becomes 1 as an int. The second step is 1 + 2.25, which is 3.25, and that becomes 3. The fix is T sum{};, which keeps the type of the list.

Exercise 4. Write a template print_all that takes a std::vector<T> and prints each item on its own line. Call it with std::vector<std::string>{"red", "green", "blue"}.

Show the answer

template <typename T>
void print_all(const std::vector<T>& items) {
    for (const T& item : items) {
        std::cout << item << '\n';
    }
}

The output is three lines: red, green, and blue. The function returns void, which means it returns nothing. It only prints.

Exercise 5. The call larger(2, 2.0) does not compile with the template from Example 2. Explain why, and write a call that works.

Show the answer

The first argument is an int and the second is a double, so the compiler finds two different types for T. A working call is larger<double>(2, 2.0). The explicit <double> sets T for the call, and both arguments are converted to double. The program prints 2.

Summary

• A function template is written once with a type placeholder, such as T, and template <typename T> on the line above it.
• The compiler deduces T from the arguments, or you name it yourself with angle brackets, such as square<long long>.
• Every use of T in one call must be the same type.
• The body only works for types that support the operations it uses, such as < or +.
• When a compile error mentions a missing operator or conflicting types for T, the problem is in the call, not in the template's logic.