In general, templates are patterns, models, or outlines. An example of a template is a word processing file containing the basic format of a specialized document that writers use as a starting point. Writes use the template by filling in some specific or missing information. C++ template functions similarly provide the function's basic pattern or format while allowing programmers to provide one or more unspecified data types.
For example, the steps for swapping two array elements (a sub-task of sorting an array) are always the same, independent of the element type. The first presentation of the swapping problem demonstrated that a solution requires a temporary variable, whether implemented "inline" or as a function, requiring a data type as part of its definition. A function implementation further requires two parameter definitions, including their types. A large set of overloaded functions can handle the fundamental data types (char, double, etc.) but not application classes, structures, or enumerations. Templates allow programmers to create a generic swap function.
template <class T> void swap(T& x, T& y) { T temp = x; x = y; y = temp; } |
template <typename T> void swap(T& x, T& y) { T temp = x; x = y; y = temp; } |
double data[1000]; . . . swap(data[i], data[j]); --------------------------------- Person people = new Person[100]; . . . swap(people[x], people[y]); |
| (a) | (b) | (c) |
class keyword to begin template functions.typename keyword to the templating mechanism, making both keywords valid.double array, replacing T with double.Person is an application class. So, passing two elements of the people array replaces T with Person.How C++ compiles template functions differs from how it processes "regular" or non-template functions. The compiler compiles regular functions to machine code, which the linker or loader can link to one or more application programs in the future. However, when substituting a type name for the template variable, the compiler can't make the substitution independently of the application using it, implying that the compiler must compile the template function and application code simultaneously. Therefore, it's impossible to compile template functions and store the object code in a system library like sqrt and pow. C++ provides template functions as source code in header files, which application programs #include, so they are compiled with the application.
C++ libraries put template function source code in a header file, programmers include it with "normal" source code, and the compiler processes it following the type expansion or substitution. If the application uses the template function with multiple data types, each type results in a different substitution, one for each type. For example, Figure 1(c) shows the swap function used with both an array of integers and an array of Person objects. In the first example, int replaces T, while in the second example, Person replaces it. Each replacement results in a separate copy of the swap function source code in the program, one copy processing int values and the second processing Person objects.
C++ provides numerous template functions, prototyped in the <algorithm> header file. There are too many to describe in detail, so we focus on one as an example. The min function (near the bottom of the list) is just one of many template functions C++ programmers may utilize. The complexity and flexibility of these functions have steadily increased since their introduction with the ANSI 1998 C++ standard.
template <class T> const T& min(const T& a, const T& b) // (a) { return (a < b) ? a : b; } template <class T, class Compare> const T& min(const T& a, const T& b, Compare comp) // (b) { return comp(a, b) ? a : b; }
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int x = 20;
int y = 10;
cout << min(x, y) << endl;
return 0;
}
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Employee
{
private:
string name;
int id;
public:
Employee(string n, int i) : name(n), id(i) {}
friend bool operator<(const Employee& e1, const Employee& e2) { return e1.name < e2.name; }
friend ostream& operator<<(ostream& out, const Employee& me) // (a)
{
out << me.name << "\t" << me.id;
return out;
}
};
int main()
{
Employee e1("Dilbert", 123);
Employee e2("Alice", 987);
cout << min(e1, e2) << endl; // (b), requires "const" in operator<<
Employee e3 = min(e1, e2); // (c), works with and without "const"
cout << e3 << endl;
return 0;
}
Both versions of the min function (Figure 2 (a) and (b)) return a const value, complicating the coordination between operator<< and the min function. Making me const (a) enables statement (b) to compile and run but limits how programmers can use the Employee inserter. Conversely, if me isn't const (a), statement (b) fails. In this case, programmers can use statement (c), which works in both cases.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Employee
{
private:
string name;
int id;
public:
Employee(string n, int i) : name(n), id(i) {}
friend bool comp1(const Employee& e1, const Employee& e2) { return e1.name < e2.name; }
friend bool comp2(const Employee& e1, const Employee& e2) { return e1.id < e2.id; }
friend ostream& operator<<(ostream& out, Employee& me)
{
out << me.name << "\t" << me.id;
return out;
}
};
int main()
{
Employee e1("Dilbert", 123);
Employee e2("Alice", 987);
Employee e3 = min(e1, e2, comp1);
cout << e3 << endl;
Employee e4 = min(e1, e2, comp2);
cout << e4 << endl;
return 0;
}
This example illustrates creating two comparator functions and passing them by pointer to min. One function, comp1, orders Employee objects by name and the other function, comp2, orders them by id number. Making the functions friends of the Employee class allows them to access its private members. Alternatively, application programmers can define the ordering functions in the application if the ordered objects provide appropriate getter functions. This example passes the functions by pointer.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Employee
{
private:
string name;
int id;
public:
Employee(string n, int i) : name(n), id(i) {}
string getName() const { return name; }
int getID() const { return id; }
friend ostream& operator<<(ostream& out, Employee& me)
{
out << me.name << "\t" << me.id;
return out;
}
};
class CompareName
{
public:
bool operator() (const Employee& e1, const Employee& e2) { return e1.getName() < e2.getName(); }
};
class CompareID
{
public:
bool operator() (const Employee& e1, const Employee& e2) { return e1.getID() < e2.getID(); }
};
int main()
{
CompareName c1;
Employee e1("Dilbert", 123);
Employee e2("Alice", 987);
Employee e3 = min(e1, e2, c1);
cout << e3 << endl;
return 0;
}
(a < b) ? a : b, and the linked online version, !(b < a) ? a : b, are similar but not identical. The difference between the two versions' tests (the conditional operator's first operand) is subtle and often irrelevant. The two versions behave differently only when a == b. In this case, the textbook version returns b while the online version returns a. But, since the two are equal, does it matter which value the function returns?
Alone, returning b rather than a is irrelevant. However, the difference may become relevant when the min function is part of a more complex operation, such as sorting an array's elements. A sorting algorithm is said to be stable (an often desirable characteristic) if it doesn't change the relative order of equal elements. For example, if a precedes b in an unsorted array, a stable sorting algorithm will preserve that relative order in the sorted array. If the sorting function calls min, the online version maintains the sorting operation's stability, while the textbook's simpler version does not.