C++ Templates
A printable version of this web page can
be found at
http://www.coquitlamcollege.com/adawson/TutorialTemplates.doc
Please note that in this
document I am referring to code which is tested on
Borland C++ compiler version
5.02 (the current installation at Coquitlam College).
There are numerous C++ compilers
and integrated development environments (IDEs)
currently in use, and your
instructor is not an expert on all of them. Please feel free to
email me questions on the
Borland v5.02 compiler: adawson@coquitlamcollege.com
Introduction to Templates
In this tutorial, I am summarizing
the material of Chapter 3 of the Weiss textbook.
In order to understand the
material of this tutorial you will need to read
Chapters 1 and 2 of the textbook
first.
An important goal of
object-oriented programming is to reuse code.
C++ provides several different
ways to reuse code, and templates is one way.
Inheritance is another way to
reuse code - inheritance is the topic of Chapter 4.
There are different kinds of
templates: the function template and the class template.
The C++ language comes with a
library of ready-made templates -
the Standard Template Library
(STL) which is the topic of Chapter 7.
In this document you will see
examples of the use of function templates,
class templates and templates
from the STL. This document is a
work in progress.
As more examples become
available, I will include them here.
A function template
Imagine you want to write a
function to swap two whole numbers, say 5 and 6.
You could send those two
integers to a function and the function swaps them.
You would send the two numbers
in variables as arguments to a function.
If the
variables are received into
reference parameters (those prefixed with the
ampersand symbol &), then if
any changes are made to the variables, these are
permanent changes as we are working
on the variables themselves and not on copies.
The function would look like
this:
void SwapInts( int & lhs, int
& rhs )
{
int tmp = lhs;
lhs = rhs;
rhs = tmp;
}
you would call it like
this: SwapInts(x,y);
Now imagine you want a function
to swap real numbers (ones with a fractional part),
you would have to write a
version of the Swap function for data of type double:
void SwapDoubles( double & lhs,
double & rhs )
{
int tmp = lhs;
lhs = rhs;
rhs = tmp;
}
Now imagine you want to swap to
long integers, you'd have to rewrite the function like this:
void SwapLongs( long & lhs, long
& rhs )
{
int tmp = lhs;
lhs = rhs;
rhs = tmp;
}
These three functions are essentially
doing the same thing - swapping the two values sent to them.
It would be nice if we could
have a generic function, one which we could use for swapping pairs
of ints or pairs of
doubles or pairs of longs. We'd like something like this:
void Swap( AnyDataType & lhs,
AnyDataType & rhs )
{
AnyDataType tmp = lhs;
lhs = rhs;
rhs = tmp;
}
where AnyDataType is a placeholder
for the actual data type (int, double or long).
Function templates allow us to
do this.
The function template looks like
this in a C++ program:
template <class Object>
void Swap( Object & lhs, Object
& rhs )
{
Object tmp = lhs;
lhs = rhs;
rhs = tmp;
}
The word "Object"
stands for any data type. You could use any word (as long as it is
a valid identifier) in place of
the word Object. A function
template is not an actual function.
A function template is a design
or a pattern for what could become
a function. In that
respect it is a bit like the
difference between a data type and a variable of the data type.
A variable is an instance of a
data type. A function is an
instance of a function template.
If a function template exists
with the name "Swap", then when Swap is called with two
int variables, a version of the function
is created, with the Object replaced with int:
void Swap( int & lhs, int &
rhs )
{
int tmp = lhs;
lhs = rhs;
rhs = tmp;
}
If Swap is called with two
double variables, then an instance of the function template for
doubles is created:
void Swap( double & lhs, double
& rhs )
{
double tmp = lhs;
lhs = rhs;
rhs = tmp;
}
The primitive data types (short
int, int, double etc.) are abstract data types which have a range
of allowable values and a set of
operations which can be performed on those values. E.g. the
short int data type stores
integers in the range -32,767 to
+32,767 and you can perform additions,
subtractions, multiplications
etc. on them. You can assignment
an integer variable to another
integer variable.
If you tried to use the Swap
function with objects of a class type,
remember that the
assignment operator works
differently with classes. The copy
assignment operator (operator =),
is used to copy objects. To use the = with objects, both of the objects
have to have previously
been constructed. Thus for objects of a class type, the
statement doesn’t work:
Object tmp = lhs;
For the line above to work with
objects of a class type you would have to have a copy constructor
written in the definition of the
class. If any of the member variables are pointers, extra care is needed.
With primitive types (and some
built-in types like the String class) these details have been taken care
of, and you can use operators
like =, +, - , >, < etc without having to define them yourself.
The following code is
FuncTemplates.cpp from: http://www.cs.fiu.edu/~weiss/adspc++2/code/
(scroll down the web page to see
the code for Chapter 3). A
cut-down version of the same code
is shown on page 99 of the
textbook - figures 3.2 and 3.3.
Note: I changed the first two
lines so that the code compiles on Borland C++ version 5.02.
// Start of FuncTemplates.cpp
#include <iostream.h> // change
to textbook code
// using namespace std; // change to
textbook code
// Note: There are swap and min
functions already defined in the library.
// Visual C++ has a bug that makes
them visible.
// So to avoid this, we define Swap
and Min (note capitalization).
// Swap function template
// Object: must have copy constructor
and operator =
template <class Object>
void Swap( Object & lhs, Object
& rhs )
{
Object tmp = lhs;
lhs = rhs;
rhs = tmp;
}
// Min function templates
// Comparable: must have copy constructor
and operator <
template <class Comparable>
Comparable Min( const Comparable &
lhs, const Comparable & rhs )
{
if( lhs < rhs )
return lhs;
else
return rhs;
}
// Exercise the function templates
int main( )
{
int x = 5;
int y = 7;
double a = 2;
double b = 4;
Swap( x, y ); // Instantiates swap with int
Swap( x, y ); // Uses already instantiated swap with int
Swap( a, b ); // Instantiates swap with double
cout << x << " " <<
y << endl;
cout << a << " " <<
b << endl;
// Swap( x, b );
// Illegal: no match
cout << "Min of x and y "
<< Min( x, y ) << endl;
cout << "Min of a and b "
<< Min( a, b ) << endl;
// cout << "Min of a and x " << Min( a, x
) << endl; // Illegal:
ambiguous
return 0;
}
// End of FuncTemplates.cpp
Note: this is how I set up my C++ projects:
This is the code running:
Good programming practice
requires placing a comment before a template with a list of the
conditions which must be
satisfied by the template parameter.
Throughout the C++ textbook,
the author uses Object and Comparable as template types.
(Any (legal) name could have
been chosen for the template
type, but Object
and Comparable are
appropriate names,
and nicely but loosely compare
to the Java's Comparable interface and Object class, which
form part of the Java
language.) For the Object template type it is
assumed that a zero-parameter
constructor, a copy constructor
and a copy assignment operator are available. For the
Comparable template type it is assumed that a zero-parameter
constructor, a copy constructor,
a copy assignment operator and
the operator < are available.
Class templates
Class templates have the same
advantages as function templates - you can write a definition
of the class template, then when
you create an object using the template, you specify the
data type you wish to use with
it. A class template is created
using the template keyword,
which tells the compiler that
the following class definition will manipulate one or more unspecified
types. At the time the object is defined, those type must be
specified so the compiler can do
the substitution.
A class without a class
template
First of all, here is an example
of a Queue class implemented with a linked list of structures
which does NOT use a class
template. Later I will show you
the same program amended
so it does use a class template.
This example is composed of
three files:
QueueDriver.cpp (the code that
tests the class)
QueueLi.h (the class definition)
QueueLi.cpp (the class
implementation)
Copy and paste the following
three files to the path shown in the following window,
and set up the project as shown
in the same window.
//*****************************************************
// queuedriver.cpp
#include "QueueLi.h"
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
int main ( )
{
Queue line;
char car;
cout << "First car arrives at the
pump"<<"\n";
line.enqueue('A');
cout
<< "Second car arrives at the pump"<<"\n";
line.enqueue('B');
cout << "Another car arrives at the
pump"<<"\n";
line.enqueue('C');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('D');
cout << "A car arrives at the
pump"<< "\n";
line.enqueue('E');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('F');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('G');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('H');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('I');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "Another car arrives at the
pump" << "\n";
line.enqueue('J');
getch();
return 0 ;
}
// end off queuedriver.cpp
//******************************************
// queueli.h
#ifndef _QUEUELI_H_
#define _QUEUELI_H_
#include <stdlib.h>
#include "Except.h"
// Queue class -- linked list
implementation.
//
// CONSTRUCTION: with no parameters.
//
// ******************PUBLIC
OPERATIONS*********************
// void enqueue( x ) --> Insert x
// void dequeue( ) --> Return and remove
least recent item
// Object getFront( ) --> Return
least recently inserted item
// bool isEmpty( ) --> Return true if
empty; else false
// void makeEmpty( ) --> Remove all items
// int
sizeOfQueue( ) --> Returns number of items in the Queue
//
******************ERRORS********************************
// UnderflowException thrown as
needed.
class Queue
{
public:
Queue( );
Queue( const Queue & rhs );
~Queue( );
const Queue & operator= ( const Queue &
rhs );
bool isEmpty( ) const;
const char & getFront( ) const;
void makeEmpty( );
char dequeue( );
void enqueue( const char & x );
int sizeOfQueue( );
private:
struct ListNode
{
char element;
ListNode *next;
ListNode( const char
& theElement, ListNode * n = NULL )
: element(
theElement ), next( n ) { }
};
int size;
ListNode *front;
ListNode *back;
};
#include "QueueLi.cpp"
#endif
// end of queueli.h
//******************************************
//****************************************
// start of queueli.cpp
#include "QueueLi.h"
#include <iostream.h>
// default constructor
Queue::Queue( )
{
front = back = NULL;
size = 0;
}
// Copy constructor.
Queue::Queue( const Queue & rhs )
{
front =
back = NULL;
*this = rhs;
}
// Destructor.
Queue::~Queue( )
{
makeEmpty( );
}
// Test if the queue is logically
empty.
// Return true if empty, false,
otherwise.
bool Queue::isEmpty( ) const
{
return front == NULL;
}
// Make the queue logically empty.
void Queue::makeEmpty( )
{
while( !isEmpty( ) )
dequeue( );
}
// Return the least recently inserted
item in the queue
const char & Queue::getFront( )
const
{
return front->element;
}
// Return and remove the least
recently inserted item from
// the queue. Throw UnderflowException
if empty.
char Queue::dequeue( )
{
char frontItem = getFront( );
ListNode *old = front;
front = front->next;
size--;
delete old;
return frontItem;
}
// Insert x into the queue.
void Queue::enqueue( const char &
x )
{
if
(size < 15)
{
if(
isEmpty( ) )
back = front = new ListNode( x );
else
back = back->next = new
ListNode( x );
size++;
}
else
{
cout
<< "There are currently 15 cars at the pump. ";
cout << "The car is
turned away" << "\n";
}
}
// Returns number of items in the
Queue
int Queue::sizeOfQueue( )
{
return
size;
}
// Deep copy.
const Queue & Queue::operator=(
const Queue & rhs )
{
if( this != &rhs
)
{
makeEmpty( );
ListNode *rptr;
for( rptr = rhs.front;
rptr != NULL; rptr = rptr->next )
enqueue( rptr->element );
}
return *this;
}
// end of queueli.cpp
//****************************************
When you compile, link and
execute the code, you will see the following window:
Study the code and compare with
the output. In the following
section of this document, you
will see the same code, but
amended to use class templates. The
programs perform the same
actions. You may choose to implement your code
with or without templates. The code will
be a little simpler if you do
not use templates, but knowing how to use them, and when to use
them, and recognizing what they
look like and how they work is very important to any advanced
studies of data structures using
C++.
A class defined as a class
template
This example is composed of
three files:
QueueDriverT.cpp (the code that
tests the class)
QueueLiT.h (the class
definition)
QueueLiT.cpp (the class
implementation)
Copy and paste the following
three files to the path shown in the following window, and
set up the project as shown in
the same window.
//**********************************************
// queuedrivert.cpp
// ***** denotes change from
queuedriver.cpp code
#include "QueueLit.h" // ***** contains class template
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
int main( )
{
Queue<char> line; // ***** compare this
statement to that in queuedriver.cpp:
// Queue line;
char car;
cout << "First car arrives at the
pump"<<"\n";
line.enqueue('A');
cout
<< "Second car arrives at the pump"<<"\n";
line.enqueue('B');
cout << "Another car arrives at the
pump"<<"\n";
line.enqueue('C');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('D');
cout << "A car arrives at the
pump"<< "\n";
line.enqueue('E');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('F');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('G');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('H');
cout << "A car arrives at the pump"
<< "\n";
line.enqueue('I');
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "Another car arrives at the
pump" << "\n";
line.enqueue('J');
getch();
return 0 ;
}
// end of queuedrivert.cpp
//**********************************************
//***************************************************
// start of QueueLiT.h
#ifndef _QUEUELI_H_
#define _QUEUELI_H_
#include <stdlib.h>
#include "Except.h"
// Queue class -- linked list
implementation.
//
// CONSTRUCTION: with no parameters.
//
// ******************PUBLIC
OPERATIONS*********************
// void enqueue( x ) --> Insert x
// void dequeue( ) --> Return and remove
least recent item
// Object getFront( ) --> Return
least recently inserted item
// bool isEmpty( ) --> Return true if empty;
else false
// void makeEmpty( ) --> Remove all items
// int
sizeOfQueue( ) --> Returns number of items in the
Queue
//
******************ERRORS********************************
// UnderflowException thrown as
needed.
template <class Object>
class Queue
{
public:
Queue( );
Queue( const Queue & rhs );
~Queue( );
const Queue & operator= ( const Queue &
rhs );
bool isEmpty( ) const;
const Object & getFront( ) const;
void makeEmpty( );
Object dequeue( );
void enqueue( const Object & x );
int sizeOfQueue( );
private:
struct ListNode
{
Object element;
ListNode *next;
ListNode( const Object
& theElement, ListNode * n = NULL )
: element(
theElement ), next( n ) { }
};
int size;
ListNode *front;
ListNode *back;
};
#include "QueueLit.cpp"
#endif
// end of QueueLiT.h
//***************************************************
//****************************************
// start of QueueLiT.cpp
#include "QueueLit.h"
// Construct the queue.
template <class Object>
Queue<Object>::Queue( )
{
front = back = NULL;
size=0;
}
// Copy constructor.
template <class Object>
Queue<Object>::Queue( const
Queue<Object> & rhs )
{
front = back = NULL;
*this = rhs;
}
// Destructor.
template <class Object>
Queue<Object>::~Queue( )
{
makeEmpty( );
}
// Test if the queue is logically
empty.
// Return true if empty, false,
otherwise.
template <class Object>
bool Queue<Object>::isEmpty( )
const
{
return front == NULL;
}
// Make the queue logically empty.
template <class Object>
void Queue<Object>::makeEmpty( )
{
while( !isEmpty( ) )
dequeue( );
}
// Return the least recently inserted
item in the queue
template <class Object>
const Object &
Queue<Object>::getFront( ) const
{
return front->element;
}
// Return and remove the least
recently inserted item from
// the queue. Throw UnderflowException
if empty.
template <class Object>
Object Queue<Object>::dequeue( )
{
Object frontItem = getFront( );
ListNode *old = front;
front = front->next;
size--;
delete old;
return frontItem;
}
// Insert x into the queue.
template <class Object>
void Queue<Object>::enqueue(
const Object & x )
{
if
(size <15)
{
if(
isEmpty( ) )
back = front = new ListNode( x );
else
back = back->next = new
ListNode( x );
size++;
}
else
cout<<"
There are currently 15 cars at the pump, can not add anymore, The car is turned
away"<<"\n";
}
// Returns number of items in the
Queue
template <class Object>
int Queue<Object>::sizeOfQueue(
)
{
return
size;
}
// Deep copy.
template <class Object>
const Queue<Object> & Queue<Object>::operator=(
const Queue<Object> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
ListNode *rptr;
for( rptr = rhs.front;
rptr != NULL; rptr = rptr->next )
enqueue( rptr->element );
}
return *this;
}
//****************************************
// end of QueueLiT.cpp
When you compile, link and
execute the code, you will see the following window:
Notice that the output is
exactly the same as the output of the previous program which
does not use a class template.
Look at the code of QueueLiT.h which contains the class
definition. The class definition
starts with the statement:
template <class Object>
This statement tells the
compiler that the following class definition is a class template definition.
Compare the code of
QueueLiT.h with that of QueueLi.h
. The differences are the
statement: template <class Object> placed
before the class definition, and the word
Object used in place of the data
type char. And that's it.
The class template defined in
QueueLiT.h is more flexible than the class definition of
QueueLi.h because it can be used
with any data type, not just char.
Later I will show
you an example program using the
same class template definition (QueueLiT.h ), and
same class template
implementation (QueueLiT.cpp), but using int data instead of char
in the driver program.
Compare the method
implementation code of QueueLiT.cpp
with that of QueueLi.cpp.
The differences are the
statement: template <class Object> placed before each
class method definition, Queue<Object>:: used
instead of Queue:: and the word
Object used in place of the data
type char. And that's it.
Now let's try using a
different driver program (QueueDriverT2.cpp),
but use the same class template
files: QueueLiT.cpp and QueueLiT.h.
// queuedrivert2.cpp
// ***** denotes change from
queuedrivert.cpp code
#include "QueueLit.h"
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
int main( )
{
Queue<int> line; // *****
int car; // *****
cout << "First car arrives at the
pump"<<"\n";
line.enqueue(1); // *****
cout
<< "Second car arrives at the pump"<<"\n";
line.enqueue(2); // *****
cout << "Another car arrives at the
pump"<<"\n";
line.enqueue(3); // *****
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue(4); // *****
cout << "A car arrives at the
pump"<< "\n";
line.enqueue(5); // *****
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "A car arrives at the pump"
<< "\n";
line.enqueue(6); // *****
cout << "A car arrives at the pump"
<< "\n";
line.enqueue(7); // *****
cout << "A car arrives at the pump"
<< "\n";
line.enqueue(8); // *****
cout << "A car arrives at the pump"
<< "\n";
line.enqueue(9); // *****
cout << "First in line about to
leave..." << "\n\n";
car = line.dequeue( );
cout << "Car " << car <<
" leaves" << "\n\n";
cout << "Currently there are "<<
line.sizeOfQueue() << " cars at the
pump"<<"\n";
cout << "Another car arrives at the
pump" << "\n";
line.enqueue(10);
getch();
return 0 ;
}
// end of queuedrivert2.cpp
When you compile, link and
execute the code, you will see the following window:
Note that the line:
Queue<int> line;
in QueueDriverT2.cpp allows you
to create a queue of integers instead of a
queue of characters.
To create a queue of data type double
(numbers with a fractional part) you would
simply substitute the above line
with:
Queue<double> line;
This page
is: TutorialTemplates.htm, edited
using: Word 2000
Last updated:
Tuesday 6th July 2004, 8:48 PT by AHD