Your quote here. Bjarne StroustrupYou are already familiar with polymorphism from previous chapters. Even though the concept of polymorphism is usually introduced in a chapter on Virtual Functions, you have actually studied polymorphism before -- in forms of function and operator overloading. As you have learned, the polymorphism is a great aid in programming, and here we will describe one more type of polymorphism -- parametric -- which is yet another powerful feature of C++.
Parametric polymorphism is a new feature, relatively to the rest of the language, and thus they present an improvement on the original polymorphic features of the language. They provide a way of reducing the amount of code, and at the same time of making functions and types really generic, independent on the argument types (for functions) and contained types (for types).
While that is polymorphism -- in C++ these functions, coexisting in one
program, would be understood by the compiler as overloaded function
swap, which would swap objects of type char
,
float
and int
, -- that is not
really generic. The only argument types acceptable are those for which the
function was defined -- namely, char
,
float
and int
. To make the
function work for other types of arguments, you'll have to add other
versions of it, one for each new type.
As we see, the polymorphism provided by overloaded functions has two flaws. One, it does not provide an easy way to write really generic functions that would once and for all work for various types. And two, the attempts to make a function more general result in longer and longer lists of similar functions. There definitely is a place for improvement here. Enter templates.
Let us examine the new function. It begins with keyword template
,
followed by a list of arguments in angle brackets. In our case, the
argument is class T
,
which is a dummy class -- it is not yet defined,
but can nevertheless be used to define our function. Because it is not
yet defined, the function is not compiled now, but is stored as a
template. Later the function can be used by associating it with a
defined data type (the proper type is the type of actual arguments),
and then a copy of it is compiled -- instantiated --
for that type. A way to think about it is as follows: we define a
function template, which takes as a parameter -- hence "parametric
polymorphism" -- a class (or type) to substitute for the dummy class
T
, and instantiates the function for that parameter.
Of course, a type for which a function is instantiated must be defined
beforehand, and the programmer should ensure that all operations
performed on class T
in the definition of the template function
are defined for the actual type.
#define
to ensure one-time
#include
into the
program as it was done in previous examples in the textbook. The
difference is in the use of keyword template
right before
the declaration. Just as we used it before defining a generic procedure,
we use it before class declaration to make it polymorphic. When we
instantiate the class for a type, the real type will be used instead of
T
.
It should be noted that there is a difference in instantiation
between classes and functions: which type of to use function is "understood"
based on the types of the arguments, whereas a class should be explicitly
instantiated when an object of it is declared, e.g.
List<int>
foo;.
Another thing to notice is the use of
List<T>
-- not List
-- as type of,
in this case, the argument to the private
function
copy (line 23).
This is because the type used will indeed be
List<T>
-- the already instantiated list, as
explained in the above paragraph.
The rest of the definition is no different -- it's just a C++ class
definition
for implementing linked lists, and at this point you should
be able to understand how it works. The operations implemented are
functions empty
,
append
,
flush
,
rewind
,
current
,
advance
,
hascur
,
and assignment operator.
The function current()
returns the value of the
current node in the list; rewind()
makes the
first node current, advance()
makes the node
immediately after the current node current, and hascur()
returns a nonzero value if there is a current element. The function
empty()
returns nonzero if the list is empty;
flush()
deletes all entries from the list.
So List<T>
is the type of the class --
linked list, of elements of type T
.
You should be able to understand how the class is implemented by now.
Compile the class, and use it in some test programs of yours.
An example client routine is
lmain.cc
.
Sometimes it is useful to provide a special, hand-coded instance of a
function of a parameterized class, because one might want to take
advantage of some type-specific features that may optimize the
implementation, but are not general enough to provide in general
instances. In that case, the declaration just uses that type name
instead of the generic T
(for example,
int
), and, of course,
List<type>
(e.g.
List<int>
)
instead of List<T>
. The definitions of these more
specific functions will, obviously, override the more general ones.
Several parameters may be given to the template
keyword. They may
include types and expressions. You have seen the case with types -- a special
case, with only one generic type T
.
A template
may be declared with
types T1
and
T2
as well, and at the instantiation the real types must be
provided (e.g. foo<int, float *>
).
Expressions may be used as arguments as
well -- but only those whose values can be computed at compile time.
Two template class objects refer to the same type if their template
names are identical and their arguments have identical values. This is
an issue to consider only if you use expressions in the arguments to
your templates, because it is quite obvious that objects instantiated to
be of a parameterized class with different arguments as types are
different (
List<int>
is obviously not the same type as
List<float>
).
A parameterized class can be treated just like other classes. For example, that it can be either a derived or a base class.
Of course, there still are, it's C++ after all. But they are rather obvious. The main one is that error detection is postponed to the late possible moment. For example, there are no restrictions on what types can match a parameter type. This gives a lot of needed flexibility, but the errors might not be detected until link time. The responsibility of checking for and preventing these errors is thus mainly assigned to the programmer.
Another problem may arise from the fact that it is up to the implementation to find the definitions of templates and classes needed for generating the definitions. Some feel that the mechanisms should be defined as part of the language, but as they are not now, one has to deal with however the implementation decides to handle the generation of template functions for some arguments.
String
data type,
to handle various string manipulations, such as concatenation, comparing,
sorting, etc. Note that
this is not as easy as it seems, if you want to write a really useful
class, but it's a very good exercise in templates, and other aspects of
C++.
Text written for the course by Cristobal Joseevich Junta
<grisha@mit.edu>
list.*
sample files by
Peter Müller and
Laura Pearlman.
C++ Course Index /
Textbook Index /
Prev: Potpourri of Paradigms /
Next: Exceptions (Additional Reading)