C++ Course Index / Textbook Index / Prev: Potpourri of Paradigms / Next: Exceptions (Additional Reading)

Parametric Polymorphism

Last changed: October 23


                    			Your quote here.
					Bjarne Stroustrup
You 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).

Contents:

  1. Function overloading revisited
  2. Adding "parametric" to "parametric polymorphism"
  3. Container types
  4. Implementing container types with templates
  5. Other stuff on templates
  6. Templates: pros and cons
  7. Programming exercises
  8. Summary

  1. Function overloading revisited (empty) (up to ToC)

  2. As you saw in previous chapters, function overloading presents a way to develop more or less generic functions to perform a task on objects of various types. Let us consider, as a simple example, that a programmer wants to create a function for swapping two objects that will work for objects of different types. The programmer would then have to write something like swap1.cc functions.

    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.


  3. Adding "parametric" to "parametric polymorphism" (empty) (up to ToC)

  4. The method of templates is a way to eliminate both of the above flaws by using what is known as "parametric polymorphism." See swap2.cc -- this is how the generic swap would be implemented with templates. The code turns out to be much more readable, and concise.

    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.


  5. Container types (empty) (up to ToC)

  6. The template method works very well for creating functions performing the same task for objects of various types. It also provides a way of creating generic container types. Objects of container types are repositories of other objects (such as stacks, queues, lists, sets). The feature of such types is that type of contained objects should not be relevant to the implementor of the container, but crucial to the user. Templates are thus a natural tool for implementing real generic container types.


  7. Implementing container types with templates (empty) (up to ToC)

  8. Let's consider a common container -- a linked list. Consider first list.h for a class definition. This is a normal class definition -- with #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.


  9. Other stuff on templates (empty) (up to ToC)

  10. What you have learned from this chapter is almost all there is to know about templates and implementing polymorphism in C++. There are also several other features of templates of which we will speak here.

    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.


  11. Templates: pros and cons (empty) (up to ToC)

  12. As with using any feature, there surely must be things to consider before using it that are for or against using templates, especially since it is a rather powerful feature of C++. But there are not many of those, because templates are a rather abstract feature of the language, and there are fewer ways to shoot yourself in the foot as with a regular C program.

    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.


  13. Programming exercises (empty) (up to ToC)

  14. To become comfortable with templates, I suggest the following exercises.
    1. To see how the template classes can be used in inheritance, define a stack and queue classes based on the List class defined here.
    2. Try implementing a generic 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++.

  15. Summary (empty) (up to ToC)

  16. You have learned about templates as a way to implement parametric polymorphism in C++. Using templates, one can create functions that work on various types without specifying the types before the functions are actually used, and generic container types, which can be used to store objects of various types, again without specifying the actual type of the elements contained before instantiation of a container object. The templates are thus a very good tool for data abstraction, which is what C++ is about.

Text written for the course by Cristobal Joseevich Junta <grisha@mit.edu>
list.* sample files by Peter Müller and Laura Pearlman.


Now, you may first want to have a look at "exceptions" and other extensions to the course tutorial.

C++ Course Index / Textbook Index / Prev: Potpourri of Paradigms / Next: Exceptions (Additional Reading)