Many C++ programs use common data structures such as stacks, queues, and lists. Imagine a program that requires a queue of customers and a queue of messages. You could easily implement a queue of customers, and then take the existing code and implement a queue of messages. If the program grows and there is a need for a queue of orders you could take the queue of messages and convert it to a queue of orders. But what if you need to make some changes to the queue implementation? This would not be a very easy task because the code has been duplicated in many places. Re-inventing source code is not an intelligent approach in an object-oriented environment that encourages re-usability. It seems to make more sense to implement a queue that can contain any arbitrary type rather than duplicating code. How does one do that? The answer is to use Type Parameterization, more commonly referred to as Templates.
C++ templates allow one to implement a generic Queue<T> template that has a T type parameter. T can be replaced with actual types. For example, if the type parameter is <Customers>, C++ will generate the class Queue<Customers>. Therefore, changing the implementation of the Queue becomes relatively simple. In our example, once the changes are implemented in the template Queue<T>, they are immediately reflected in the classes Queue<Customers>, Queue<Messages>, and Queue<Orders>.
Templates are very useful when implementing generic constructs such as vectors, stacks, lists, and queues that can be used with any arbitrary type. C++ templates provide a way to reuse source code, as opposed to inheritance and composition, which provide a way to reuse object code.
C++ provides two types of templates: class templates and function templates. Use function templates to write generic functions: for example, searching and sorting routines that can be used with arbitrary types. The Standard Template Library generic algorithms have been implemented as function templates and the containers have been implemented as class templates.
A class template definition looks like a regular class definition, except it is prefixed by the keyword template. For example, here is the definition of a class template for a stack:
template <class T>
class Stack {
public:
Stack(int = 10);
~Stack() { delete [] stackPtr; }
int push(const T&);
int pop(T&);
int isEmpty()const { return top == -1; }
int isFull() const { return top == size - 1; }
private:
int size; // number of elements on Stack.
int top;
T* stackPtr;
};
T is any type parameter, for example, Stack<Tokens>, where Token is a user defined class. T does not have to be a class type as implied by the keyword class. For example, Stack<int> and Stack<Message*> are valid instantiations, even though int and Message* are not classes.
Implementing template member functions is somewhat different than implementing the regular class member functions. The declarations and definitions of the class-template member functions should all be in the same header file. Why do the declarations and definitions need to be in the same header file? Consider the following:
//B.h template
<class t> class b {
public:
b( );
~b( );
};
|
// B.cpp
#include “B.h”
template <class t>
b<t>::b() { }
template <class t>
b<t>::~b() { }
|
//main.cpp
#include “B.h”
void main() {
b<int> bi;
b <float> bf;
}
|
When compiling B.cpp, the compiler has both the declarations and the definitions available. At this point, the compiler does not need to generate any definitions for template classes, since there are no instantiations. When the compiler compiles main.cpp, there are two instantiations: template classes B<int> and B<float>. At this point, the compiler has the declarations but no definitions!
While implementing class-template member functions, the definitions are prefixed by the keyword template. Here is the complete implementation of the Stack class template:
//stack.h
#pragma once
template <class T>
class Stack {
public:
Stack(int = 10);
~Stack() { delete [] stackPtr ; }
int push(const T&);
int pop(T&); // pop an element off the stack
int isEmpty()const { return top == -1; }
int isFull() const { return top == size - 1; }
private:
int size; // Number of elements on Stack
int top;
T* stackPtr;
};
//Constructor with the default size 10
template <class T>
Stack<T>::Stack(int s) {
size = s > 0 && s < 1000 ? s : 10;
top = -1 ; // initialize stack
stackPtr = new T[size];
}
//Push an element onto the Stack.
template <class T>
int Stack<T>::push(const T& item) {
if (!isFull()) {
stackPtr[++top] = item;
return 1; // push successful
}
return 0; // push unsuccessful
}
//Pop an element off the Stack.
template <class T>
int Stack<T>::pop(T& popValue) {
if (!isEmpty()) {
popValue = stackPtr[top--];
return 1; // pop successful
}
return 0; // pop unsuccessful
}
Using a class template is very easy. Create the required classes by plugging in the actual type for the type parameters. This process is commonly known as instantiating a class. Here is a sample driver class that uses the Stack class template:
#include <iostream>
#include “stack.h”
void main() {
typedef Stack<float> FloatStack;
typedef Stack<int> IntStack;
FloatStack fs(5);
float f = 1.1;
cout << "Pushing elements onto fs" << endl;
while (fs.push(f)) {
cout << f << ' ';
f += 1.1;
}
cout << endl << "Stack Full." << endl;
cout << endl << "Popping elements from fs" << endl;
while (fs.pop(f))
cout << f << ' ';
cout << endl << "Stack Empty" << endl << endl;
IntStack is;
int i = 1.1;
cout << "Pushing elements onto is" << endl;
while (is.push(i)) {
cout << i << ' ';
i += 1 ;
}
cout << endl << "Stack Full" << endl;
cout << endl << "Popping elements from is" << endl;
while (is.pop(i))
cout << i << ' ';
cout << endl << "Stack Empty" << endl;
}
Here is the output:
Pushing elements onto fs
1.1 2.2 3.3 4.4 5.5
Stack Full.
Popping elements from fs
5.5 4.4 3.3 2.2 1.1
Stack Empty
Pushing elements onto is
1 2 3 4 5 6 7 8 9 10
Stack Full
Popping elements from is
10 9 8 7 6 5 4 3 2 1
Stack Empty
In the above example we defined a class template Stack. In the driver program we instantiated a Stack of float (FloatStack) and a Stack of int(IntStack). Once the template classes are instantiated, you can instantiate objects of that type (for example, fs and is.)
A very good programming practice is to use typedef while instantiating template classes. Then throughout the program, one can use the typedef name. There are two advantages:
This practice is especially helpful when using STL components. There are many implementations of STL available, some of which are incompatible. The implementation in Visual C++ 4.2 may change in future versions. For example, currently the definition of the vector required you to specify an allocator parameter:
typedef vector<int, allocator<int> > INTVECTOR ; INTVECTOR vi1 ;
In a future version, the second parameter may not be required, for example,
typedef vector<int> INTVECTOR ; INTVECTOR vi1 ;
Imagine how many changes would be required if there was no typedef!
Each instantiation of a class template has it’s own static members that are shared with other objects of that instantiation. This is true of static data members and static member functions.
To perform identical operation for each type of data compactly and conveniently, use function templates. You can write a single function template definition. Based on the argument types provided in calls to the function, the compiler automatically instantiates separate object code functions to handle each type of call appropriately. The STL algorithms are implemented as function templates.
Function templates are implemented like regular functions, except they are prefixed with the keyword template. Using function templates is very easy; just use them like regular functions. Here is a sample with a function template:
#include <iostream>
//max returns the maximum of the two elements
template <class T>
T max(T a, T b) {
return a > b ? a : b;
}
void main() {
cout << "max(10, 15) = " << max(10, 15) << endl;
cout << "max('k', 's') = " << max('k', 's') << endl;
cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;
}
Here is the output:
max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
In some cases it is possible to override the template-generated code by providing special definitions for specific types. This is called template specialization. For example:
#include <iostream.h>
//max returns the maximum of the two elements of type T, where T is a
//class or data type for which operator> is defined.
template <class T>
T max(T a, T b) {
return a > b ? a : b;
}
void main() {
cout << "max(10, 15) = " << max(10, 15) << endl;
cout << "max('k', 's') = " << max('k', 's') << endl;
cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl;
cout << "max(\"Aladdin\", \"Jasmine\") = " << max("Aladdin", "Jasmine") << endl;
}
Here is the output:
max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Aladdin
Not quite the expected results! Why did that happen? The function call max(“Aladdin”, “Jasmine”) causes the compiler to generate code for max(char*, char*), which compares the addresses of the strings! To correct special cases like these or to provide more efficient implementations for certain types, one can use template specializations. The above example can be rewritten with specialization as follows:
#include <iostream.h>
#include <string.h>
//max returns the maximum of the two elements
template <class T>
T max(T a, T b) {
return a > b ? a : b;
}
// Specialization of max for char* char*
max(char* a, char* b) {
return strcmp(a, b) > 0 ? a : b;
}
void main() {
cout << "max(10, 15) = " << max(10, 15) << endl;
cout << "max('k', 's') = " << max('k', 's') << endl;
cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl;
cout << "max(\"Aladdin\", \"Jasmine\") = " << max("Aladdin", "Jasmine") << endl;
}
Here is the output:
max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Jasmine
Friendship can be established between a class template and a global function, a member function of another class (possibly a template class), or even an entire class (possibly a template class). Table 3 lists the results of declaring different kinds of friends of a class:
Table 3. Friend Declarations
| Class Template | Friend declaration in class template X | Result of giving friendship |
| template class <T> class X | friend void f1() ; | makes f1() a friend of all instantiations of template X. For example, f1() is a friend of X<int>, X<A>, and X<Y>. |
| template class <T> class X | friend void f2(X<T>&) ; | For a particular type T for example, float, makes f2(X<float>&) a friend of class X<float> only. f2(x<float>&) cannot be a friend of class X<A>. |
| template class <T> class X |
friend A::f4() ; // A is a user defined class |
makes A::f4() a friend of all instantiations of template X. For example, A::f4() is a friend of X<int>, X<A>, and X<Y>. |
| template class <T> class X |
friend C<T>::f5(X<T>&) ; // C is a class |
A particular type T (for example, float) makes C<float>::f5(X<float>&) a friend of class X<float> only. C<float>::f5(x<float>&) cannot be a friend of class X<A>. |
| template class <T> class X | friend class Y ; | makes every member function of class Y a friend of every template class produced from the class template X. |
| template class <T> class X | friend class Z<T> ; | when a template class is instantiated with a particular type T, such as a float, all members of class Z<float> become friends of template class X<float>. |
The Stack class template, described in the previous section, used only type parameters in the template header. It is also possible to use nontype parameters. For example, the template header could be modified to take an int elements parameter as follows:
template <class T, int elements> class Stack ;
Then, a declaration such as:
Stack<float, 100> mostRecentSalesFigures ;
could instantiate (at compile time) a 100 element Stack template class named mostRecentSalesFigures (of float values); this template class would be of type Stack<float, 100>.
Let us look at the Stack class template again:
template <class T, int elements> Stack { ....} ;
C++ allows you to specify a default template parameter, so the definition could now look like:
template <class T = float, int elements = 100> Stack { ....} ;
Then a declaration such as:
Stack<> mostRecentSalesFigures ;
would instantiate (at compile time) a 100 element Stack template class named mostRecentSalesFigures (of float values); this template class would be of type Stack<float, 100>.
If you specify a default template parameter for any formal parameter, the rules are the same as for functions and default parameters. Once a default parameter is declared, all subsequent parameters must have defaults.
The following example demonstrates member templates. When you define a class template or a function template as a member of a class, it is called a member template. Visual C++ 4.2 does not support member templates.
class MyAllocator {
int size;
template class<T>
class types; // member class template
template class<T>
print(T type); // member function template
};