Templates
Open in the Padhaiko app8.1 Function template
A template lets one piece of code work for many data types. A function template is a "blueprint" from which the compiler generates a separate function for each type used in a call (instantiation). This is generic programming: the code is written once and the type is a parameter.
Function Template
Syntax: template <class T> (or template <typename T>) followed by a normal function definition that uses T as a type.
The compiler deduces T from the arguments of each call. If the arguments have different types for the same T (for example maximum(3, 4.5)), deduction fails and the type must be given explicitly: maximum<double>(3, 4.5).
#include <iostream>
#include <string>
using namespace std;
template <class T>
T maximum(T a, T b) {
return (a > b) ? a : b;
}
template <class T>
void swapValues(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
template <class T1, class T2>
void show(T1 a, T2 b) {
cout << a << " and " << b << endl;
}
int main() {
cout << maximum(7, 12) << endl; // T = int
cout << maximum(3.5, 2.25) << endl; // T = double
cout << maximum('a', 'z') << endl; // T = char
cout << maximum<double>(3, 4.5) << endl; // explicit argument avoids the mismatch
int x = 5, y = 9;
swapValues(x, y);
cout << "x = " << x << ", y = " << y << endl;
string s1 = "tea", s2 = "coffee";
swapValues(s1, s2);
cout << s1 << " " << s2 << endl;
show(10, "ten"); // two different types
return 0;
}12
3.5
z
4.5
x = 9, y = 5
coffee tea
10 and tenPoints to remember
- A template is resolved at compile time; there is no run-time cost compared with writing the functions by hand.
- The type used must support every operation in the body (for
maximum, the operator>must exist). - A function template with several type parameters uses
template <class T1, class T2>. - The template definition normally goes in a header file because the compiler needs it to generate the instantiations.
- Each different type used creates its own copy of the function (code growth).
8.2 Overloading function template
A function template can be overloaded by another template with a different number or kind of parameters, or by an ordinary (non-template) function. When a call is made the compiler picks the best match using these rules:
- An ordinary function that matches exactly is preferred over a template.
- Otherwise a template that gives an exact match is used (after deduction).
- If no template or function matches (even after ordinary conversions of an ordinary function), the call is an error.
#include <iostream>
#include <cstring>
using namespace std;
template <class T>
T biggest(T a, T b) {
cout << "[two-argument template] ";
return (a > b) ? a : b;
}
template <class T>
T biggest(T a, T b, T c) { // overloaded template: different parameter count
cout << "[three-argument template] ";
return biggest(biggest(a, b), c);
}
const char *biggest(const char *a, const char *b) { // ordinary function overload
cout << "[ordinary function for strings] ";
return (strcmp(a, b) > 0) ? a : b;
}
int main() {
cout << biggest(3, 8) << endl;
cout << biggest(2.5, 1.5, 9.75) << endl;
cout << biggest("apple", "mango") << endl;
return 0;
}[two-argument template] 8
[three-argument template] [two-argument template] [two-argument template] 9.75
[ordinary function for strings] mangoThe call biggest("apple", "mango") uses the ordinary function because it matches exactly, and it compares the strings with strcmp; the template would have compared the two pointers instead. The three-argument call uses the other template, which calls the two-argument template twice.
8.3 Class template
A class template defines a family of classes. It is used for containers such as a stack, a queue or an array, where the data type is a parameter. The object is created by giving the type in angle brackets: Stack<int> s;.
template <class T>
class Name {
T member;
public:
Name(T v);
T get() const;
};
template <class T> // a member defined outside the class
T Name<T>::get() const { return member; }
Name<int> a(5); // instantiation with T = int#include <iostream>
#include <string>
using namespace std;
template <class T>
class Stack {
T data[10];
int top;
public:
Stack() : top(-1) {}
bool isEmpty() const { return top == -1; }
bool isFull() const { return top == 9; }
void push(T value) {
if (isFull()) { cout << "stack overflow" << endl; return; }
data[++top] = value;
}
T pop() {
if (isEmpty()) { cout << "stack underflow" << endl; return T(); }
return data[top--];
}
int size() const { return top + 1; }
};
template <class T1, class T2>
class Pair {
T1 first;
T2 second;
public:
Pair(T1 a, T2 b) : first(a), second(b) {}
void show() const { cout << "(" << first << ", " << second << ")" << endl; }
};
int main() {
Stack<int> s;
s.push(10); s.push(20); s.push(30);
cout << "size = " << s.size() << endl;
cout << s.pop() << " " << s.pop() << " " << s.pop() << endl;
s.pop(); // underflow message
Stack<char> cs;
cs.push('A'); cs.push('B');
cout << cs.pop() << cs.pop() << endl;
Pair<string, int> p("Roll", 15);
p.show();
Pair<double, char> q(2.5, 'x');
q.show();
return 0;
}size = 3
30 20 10
stack underflow
BA
(Roll, 15)
(2.5, x)A class template can have more than one parameter (Pair<T1, T2>) and default arguments. Unlike function templates, the type is never deduced for a class template in the old style: it must be written explicitly (from C++17 a constructor call can deduce it).
8.4 Derived class template
A class template can be a base class of another template, or an ordinary class can derive from one instantiation (class IntArray : public Array<int>). When both are templates, the derived class is declared with its own template <class T> and the base is written Array<T>. In the derived class members of a dependent base must be reached with this-> (or Array<T>::), because the compiler does not look into a template base automatically.
#include <iostream>
using namespace std;
template <class T>
class Array {
protected:
T a[5];
int n;
public:
Array() : n(0) {}
void add(T v) { if (n < 5) a[n++] = v; }
void show() const {
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
};
template <class T>
class SortedArray : public Array<T> { // derived class template
public:
void sort() {
for (int i = 0; i < this->n - 1; i++)
for (int j = 0; j < this->n - 1 - i; j++)
if (this->a[j] > this->a[j + 1]) {
T t = this->a[j];
this->a[j] = this->a[j + 1];
this->a[j + 1] = t;
}
}
};
int main() {
SortedArray<int> x;
x.add(42); x.add(7); x.add(19); x.add(3);
x.show();
x.sort();
x.show();
SortedArray<double> y;
y.add(2.5); y.add(-1.5); y.add(0.5);
y.sort();
y.show();
return 0;
}42 7 19 3
3 7 19 42
-1.5 0.5 2.5 8.5 Introduction to standard template library
The Standard Template Library (STL) is the part of the C++ standard library built from templates: ready-made, tested, generic containers and algorithms that work together through iterators.
8.5.1 Components of STL
The STL has three main components, plus a few helpers.
| Component | Role | Examples |
|---|---|---|
| Containers | Store collections of objects | vector, list, deque, set, map, stack, queue |
| Iterators | Objects that point into containers and move through them | begin(), end(), ++, * |
| Algorithms | Generic functions that work on iterator ranges | sort, find, count, reverse, accumulate |
| Function objects, adaptors, allocators | Helpers | less<T>, lambdas, stack adaptor |
8.5.2 Container
| Kind | Containers | Notes |
|---|---|---|
| Sequence | vector, list, deque | Elements kept in the order inserted; vector has fast random access |
| Associative | set, map, multiset, multimap | Sorted by key; fast search |
| Container adaptors | stack, queue, priority_queue | Restricted interface built on another container |
8.5.3 Iterators
An iterator behaves like a pointer: *it gives the element, ++it moves to the next one, begin() points at the first element and end() points one past the last. Types of iterators include input, output, forward, bidirectional (list, map) and random access (vector, supports it + n and it2 - it1).
8.5.4 Algorithms
Algorithms in <algorithm> and <numeric> take a pair of iterators [first, last) and work on any suitable container: sort, find, count, count_if, reverse, max_element, min_element, accumulate and for_each.
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
vector<int> v = {40, 10, 30, 20, 50};
v.push_back(60);
cout << "size = " << v.size() << ", first = " << v.front() << ", last = " << v.back() << endl;
sort(v.begin(), v.end()); // algorithm on a container range
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) cout << *it << " ";
cout << endl;
auto pos = find(v.begin(), v.end(), 30);
cout << "30 found at index " << (pos - v.begin()) << endl;
cout << "sum = " << accumulate(v.begin(), v.end(), 0) << endl;
cout << "max = " << *max_element(v.begin(), v.end()) << endl;
cout << "count of values > 25 = " << count_if(v.begin(), v.end(), [](int x) { return x > 25; }) << endl;
reverse(v.begin(), v.end());
cout << "reversed:";
for (int x : v) cout << " " << x;
cout << endl;
list<string> names = {"Sita", "Ram"};
names.push_front("Hari");
names.push_back("Gita");
for (const string &s : names) cout << s << " ";
cout << endl;
map<string, int> marks;
marks["Asha"] = 85;
marks["Bimal"] = 72;
marks["Asha"] = 90; // replaces the old value
for (auto it = marks.begin(); it != marks.end(); ++it)
cout << it->first << " -> " << it->second << endl;
return 0;
}size = 6, first = 40, last = 60
10 20 30 40 50 60
30 found at index 2
sum = 210
max = 60
count of values > 25 = 4
reversed: 60 50 40 30 20 10
Hari Sita Ram Gita
Asha -> 90
Bimal -> 72Worked Examples
1
Write a function template maximum and show which function is generated for maximum(7, 12), maximum(3.5, 2.25) and maximum('a', 'z'). What happens for maximum(3, 4.5) and how is it fixed?
The template. template <class T> T maximum(T a, T b) { return (a > b) ? a : b; }
Instantiations. For the calls with int, double and char arguments the compiler deduces T = int, T = double and T = char and generates three separate functions. The output of the program in section 8.1 shows 12, 3.5 and z.
Mixed types. For maximum(3, 4.5) the first argument gives T = int and the second gives T = double; the two deductions conflict, so the call is an error. It is fixed by giving the type, maximum<double>(3, 4.5), which converts 3 to 3.0 and returns 4.5.
The compiler creates maximum<int>, maximum<double> and maximum<char>; mixed arguments need an explicit type: maximum<double>(3, 4.5) returns 4.5.
2
Write a class template Stack<T> with push, pop and size, and show its use with int and char. Trace the output of the program in section 8.3.
Design. An array T data[10] and an index top that starts at -1. push increments top and stores; pop returns the element at top and decrements it. Errors (overflow, underflow) print a message.
Trace for Stack<int>. After pushing 10, 20 and 30 the size is 3 and the pops return 30, 20, 10 (last in, first out). A fourth pop() on the empty stack prints stack underflow.
Stack<char> and Pair. A and B are pushed and popped as BA. Pair<string, int> prints (Roll, 15) and Pair<double, char> prints (2.5, x). The compiler generated a separate class for each different set of type arguments.
size = 3, then 30 20 10, the underflow message, BA, (Roll, 15) and (2.5, x).
3
Using the STL, store 40, 10, 30, 20, 50 and 60 in a vector. Sort it, find the position of 30, find the sum and the maximum, and count the values above 25.
Sorted vector. sort(v.begin(), v.end()) gives 10 20 30 40 50 60.
Search and statistics. find returns an iterator to 30; subtracting v.begin() gives the index 2. accumulate(v.begin(), v.end(), 0) gives 10 + 20 + 30 + 40 + 50 + 60 = 210 and max_element points at 60.
Counting. count_if with the lambda x > 25 counts 30, 40, 50 and 60, which is 4 values. The program in section 8.5.4 prints these results.
Sorted vector 10 to 60, 30 at index 2, sum 210, maximum 60, 4 values above 25.
Exercises
Exercises: Templates
Write a function template sumArray that adds the elements of an array of any type, and a template bubbleSort. Show the output for an int array {5, 2, 9, 1, 7}, a double array {1.5, 2.5, 3.0} and a string array {pear, apple, mango}.
Program.
#include <iostream>
#include <string>
using namespace std;
template <class T>
T sumArray(const T arr[], int n) {
T total = T();
for (int i = 0; i < n; i++) total += arr[i];
return total;
}
template <class T>
void bubbleSort(T arr[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
int main() {
int a[5] = {5, 2, 9, 1, 7};
double d[3] = {1.5, 2.5, 3.0};
string w[3] = {"pear", "apple", "mango"};
cout << "sum of ints = " << sumArray(a, 5) << endl;
cout << "sum of doubles = " << sumArray(d, 3) << endl;
bubbleSort(a, 5);
for (int x : a) cout << x << " ";
cout << endl;
bubbleSort(w, 3);
for (const string &s : w) cout << s << " ";
cout << endl;
return 0;
}Output. The sums are 5 + 2 + 9 + 1 + 7 = 24 and 1.5 + 2.5 + 3.0 = 7 (printed as 7); bubbleSort works for ints and strings because both support >.
sum of ints = 24
sum of doubles = 7
1 2 5 7 9
apple mango pear 24, 7, then 1 2 5 7 9 and apple mango pear.
Compare function templates and function overloading. When would you use each?
Overloading uses several functions with the same name but separate bodies; it is right when the algorithms differ for different types. A function template has one body and the compiler writes the versions; it is right when the algorithm is the same and only the type changes.
Both are resolved at compile time. A template needs every operation in its body to exist for the type used, while overloading lets each version use type-specific code. They can be combined: a special ordinary function is provided for a type (such as const char *) where the generic body would be wrong.
Templates: one generic body, type is a parameter. Overloading: separate bodies for separate types. Use templates when the logic does not change with the type.
What is the difference between a class template and a template class? Instantiate Pair<T1, T2> for (string, int) and for (double, char).
A class template is the blueprint (template <class T> class Stack {...}); a template class is a concrete class generated from it, such as Stack<int>.
Pair<string, int> p("Roll", 15); and Pair<double, char> q(2.5, 'x'); generate two different classes; the program of section 8.3 prints (Roll, 15) and (2.5, x).
Class template = blueprint; template class = instantiation such as Pair<string, int>.
Name the three main components of the STL and explain begin() and end(). What does *max_element(v.begin(), v.end()) return for the vector 10, 20, 30, 40, 50, 60?
The components are containers, iterators and algorithms. begin() returns an iterator to the first element and end() an iterator one past the last element, so an algorithm works on the half-open range [begin, end).
max_element returns an iterator to the largest element; dereferencing it with * gives the value 60.
Containers, iterators, algorithms; the expression returns 60.
In a derived class template SortedArray<T> : public Array<T>, why must n and a be written as this->n and this->a[j]? Give the output of sorting 42, 7, 19, 3.
The base Array<T> depends on the template parameter, so when the derived template is compiled the compiler does not yet know what members the base has. Writing this->n (or Array<T>::n) tells it the name is a member that will be found when T is known.
The program in section 8.4 prints the original order 42 7 19 3 and then, after the bubble sort, 3 7 19 42.
Use this-> because the base class is dependent on T; the sorted output is 3 7 19 42.