Introduction to templates

Inheritance and composition provide a way to reuse object code. The template feature in C++ provides a way to reuse source code.

Although C++ templates are a general-purpose programming tool, when they were introduced in the language, they seemed to discourage the use of object-based container-class hierarchies. Later versions of container-class libraries are built exclusively with templates and are much easier for the programmer to use.

This chapter begins with an introduction to containers and the way they are implemented with templates, followed by examples of container classes and how to use them.

Containers & iterators

Suppose you want to create a stack. In C, you would make a data structure and associated functions, but of course in C++ you package the two together into an abstract data type. This stack class will hold ints, to keep it simple:

The class IStack is an almost trivial example of a push-down stack. For simplicity it has been created here with a fixed size, but you can also modify it to automatically expand by allocating memory off the heap. (This will be demonstrated in later examples.)

The second class, IStackIter, is an example of an iterator, which you can think of as a superpointer that has been customized to work only with an IStack. Notice that IStackIter is a friend of IStack, which gives it access to all the private elements of IStack.

Like a pointer, IStackIter's job is to move through an IStack and retrieve values. In this simple example, the IStackIter can move only forward (using both the pre- and postfix forms of the operator++) and it can fetch only values. However, there is no boundary to the way an iterator can be defined. It is perfectly acceptable for an iterator to move around any way within its associated container and to cause the contained values to be modified. However, it is customary that an iterator is created with a constructor that attaches it to a single container object and that it is not reattached during its lifetime. (Most iterators are small, so you can easily make another one.)

To make the example more interesting, the fibonacci( ) function generates the traditional rabbit-reproduction numbers. This is a fairly efficient implementation, because it never generates the numbers more than once. (Although if you've been out of school awhile, you've probably figured out that you don't spend your days researching more efficient implementations of algorithms, as textbooks might lead you to believe.)

In main( ) you can see the creation and use of the stack and its associated iterator. Once you have the classes built, they're quite simple to use.

The need for containers

Obviously an integer stack isn't a crucial tool. The real need for containers comes when you start making objects on the heap using new and destroying them with delete. In the general programming problem, you don't know how many objects you're going to need while you're writing the program. For example, in an air-traffic control system you don't want to limit the number of planes your system can handle. You don't want the program to abort just because you exceed some number. In a computer-aided design system, you're dealing with lots of shapes, but only the user determines (at runtime) exactly how many shapes you're going to need. Once you notice this tendency, you'll discover lots of examples in your own programming situations.

C programmers who rely on virtual memory to handle their "memory management" often find the idea of new, delete, and container classes disturbing. Apparently, one practice in C is to create a huge global array, larger than anything the program would appear to need. This may not require much thought (or awareness of malloc( ) and free( )), but it produces programs that don't port well and can hide subtle bugs.

In addition, if you create a huge global array of objects in C++, the constructor and destructor overhead can slow things down significantly. The C++ approach works much better: When you need an object, create it with new, and put its pointer in a container. Later on, fish it out and do something to it. This way, you create only the objects you absolutely need. And generally you don't have all the initialization conditions at the start-up of the program; you have to wait until something happens in the environment before you can actually create the object.

So in the most common situation, you'll create a container that holds pointers to some objects of interest. You will create those objects using new and put the resulting pointer in the container (potentially upcasting it in the process), fishing it out later when you want to do something with the object. This technique produces the most flexible, general sort of program.

Overview of templates

Now a problem arises. You have an IStack, which holds integers. But you want a stack that holds shapes or airliners or plants or something else. Reinventing your source-code every time doesn't seem like a very intelligent approach with a language that touts reusability. There must be a better way.

There are three techniques for source-code reuse: the C way, presented here for contrast; the Smalltalk approach, which significantly affected C++; and the C++ approach: templates.

The C approach

Of course you're trying to get away from the C approach because it's messy and error prone and completely inelegant. You copy the source code for a Stack and make modifications by hand, introducing new errors in the process. This is certainly not a very productive technique.

The Smalltalk approach

Smalltalk took a simple and straightforward approach: You want to reuse code, so use inheritance. To implement this, each container class holds items of the generic base class object. But, as mentioned before, the library in Smalltalk is of fundamental importance, so fundamental, in fact, that you don't ever create a class from scratch. Instead, you must always inherit it from an existing class. You find a class as close as possible to the one you want, inherit from it, and make a few changes. Obviously this is a benefit because it minimizes your effort (and explains why you spend a lot of time learning the class library before becoming an effective Smalltalk programmer).

But it also means that all classes in Smalltalk end up being part of a single inheritance tree. You must inherit from a branch of this tree when creating a new class. Most of the tree is already there (it's the Smalltalk class library), and at the root of the tree is a class called object - the same class that each Smalltalk container holds.

This is a neat trick because it means that every class in the Smalltalk class hierarchy is derived from object, so every class can be held in every container, including that container itself. This type of single-tree hierarchy based on a fundamental generic type (often named object) is referred to as an "object-based hierarchy." You may have heard this term before and assumed it was some new fundamental concept in OOP, like polymorphism. It just means a class tree with object (or some similar name) at its root and container classes that hold object.

Because the Smalltalk class library had a much longer history and experience behind it than C++, and the original C++ compilers had no container class libraries, it seemed like a good idea to duplicate the Smalltalk library in C++. This was done as an experiment with a very early C++ implementation, and because it represented a significant body of code, many people began using it. In the process of trying to use the container classes, they discovered a problem.

The problem was that in Smalltalk, you could force people to derive everything from a single hierarchy, but in C++ you can't. You might have your nice object-based hierarchy with its container classes, but then you might buy a set of shape classes or airline classes from another vendor who didn't use that hierarchy. (For one thing, the hierarchy imposes overhead, which C programmers eschew.) How do you shoehorn a separate class tree into the container class in your object-based hierarchy? Here's what the problem looks like:

Because C++ supports multiple independent hierarchies, Smalltalk's object-based hierarchy does not work so well.

The solution seemed obvious. If you can have many inheritance hierarchies, then you should be able to inherit from more than one class: Multiple inheritance will solve the problem. So you do the following:

Now oshape has shape's characteristics and behaviors, but because it is also derived from object it can be placed in container.

But multiple inheritance wasn't originally part of C++. Once the container problem was seen, there came a great deal of pressure to add the feature. Other programmers felt (and still feel) multiple inheritance wasn't a good idea and that it adds unneeded complexity to the language. An oft-repeated statement at that time was, "C++ is not Smalltalk," which, if you knew enough to translate it, meant "Don't use object based hierarchies for container classes." But in the end the pressure persisted, and multiple inheritance was added to the language. Compiler vendors followed suit by including object-based container-class hierarchies, most of which have since been replaced by template versions. You can argue that multiple inheritance is needed for solving general programming problems, but you'll see in the next chapter that its complexity is best avoided except in certain cases.

The template approach

Although an object-based hierarchy with multiple inheritance is conceptually straightforward, it turns out to be painful to use. In his original book Stroustrup demonstrated what he considered a preferable alternative to the object-based hierarchy. Container classes were created as large preprocessor macros with arguments that could be substituted for your desired type. When you wanted to create a container to hold a particular type, you made a couple of macro calls.

Unfortunately, this approach was confused by all the existing Smalltalk literature, and it was a bit unwieldy. Basically, nobody got it.

In the meantime, Stroustrup and the C++ team at Bell Labs had modified his original macro approach, simplifying it and moving it from the domain of the preprocessor into the compiler itself. This new code-substitution device is called a template , and it represents a completely different way to reuse code: Instead of reusing object code, as with inheritance and composition, a template reuses source code. The container no longer holds a generic base class called object, but instead an unspecified parameter. When you use a template, the parameter is substituted by the compiler, much like the old macro approach, but cleaner and easier to use.

Now, instead of worrying about inheritance or composition when you want to use a container class, you take the template version of the container and stamp out a specific version for your particular problem, like this:

The compiler does the work for you, and you end up with exactly the container you need to do your job, rather than an unwieldy inheritance hierarchy. In C++, the template implements the concept of a parameterized type. Another benefit of the template approach is that the novice programmer who may be unfamiliar or uncomfortable with inheritance can still use canned container classes right away.

Template syntax

The template keyword tells the compiler that the following class definition will manipulate one or more unspecified types. At the time the object is defined, those types must be specified so the compiler can substitute them.

Here's a small example to demonstrate the syntax:

You can see that it looks like a normal class except for the line

which says that T is the substitution parameter, and it represents a type name. Also, you see T used everywhere in the class where you would normally see the specific type the container holds.

In Array, elements are inserted and extracted with the same function, the overloaded operator[ ]. It returns a reference, so it can be used on both sides of an equal sign. Notice that if the index is out of bounds, the require( ) function is used to print a message. This is actually a case where throwing an exception is more appropriate, because then the class user can recover from the error, but that topic is not covered until Chapter XX.

In main( ), you can see how easy it is to create Arrays that hold different types of objects. When you say

the compiler expands the Array template (this is called instantiation) twice, to create two new generated classes, which you can think of as Array_int and Array_float. (Different compilers may decorate the names in different ways.) These are classes just like the ones you would have produced if you had performed the substitution by hand, except that the compiler creates them for you as you define the objects ia and fa. Also note that duplicate class definitions are either avoided by the compiler or merged by the linker.

Non-inline function definitions

Of course, there are times when you'll want to have non-inline member function definitions. In this case, the compiler needs to see the template declaration before the member function definition. Here's the above example, modified to show the non-inline member definition:

Notice that in the member function definition the class name is now qualified with the template argument type: Array<T>. You can imagine that the compiler does indeed carry both the name and the argument type(s) in some decorated form.

Header files

Even if you create non-inline function definitions, you'll generally want to put all declarations and definitions for a template in a header file. This may seem to violate the normal header file rule of "Don't put in anything that allocates storage" to prevent multiple definition errors at link time, but template definitions are special. Anything preceded by template<...> means the compiler won't allocate storage for it at that point, but will instead wait until it's told to (by a template instantiation), and that somewhere in the compiler and linker there's a mechanism for removing multiple definitions of an identical template. So you'll almost always put the entire template declaration and definition in the header file, for ease of use.

There are times when you may need to place the template definitions in a separate cpp file to satisfy special needs (for example, forcing template instantiations to exist in only a single Windows dll file). Most compilers have some mechanism to allow this; you'll have to investigate your particular compiler's documentation to use it.

The stack as a template

Here is the container and iterator from Istack.cpp, implemented as a generic container class using templates:

Notice that anywhere a template's class name is referred to, it must be accompanied by its template argument list, as in Stackt<T>& s. You can imagine that internally, the arguments in the template argument list are also being decorated to produce a unique class name for each template instantiation.

Also notice that a template makes certain assumptions about the objects it is holding. For example, Stackt assumes there is some sort of assignment operation for T inside the push( ) function. You could say that a template "implies an interface" for the types it is capable of holding.

Here's the revised example to test the template:

The only difference is in the creation of is and it: You specify the type of object the stack and iterator should hold inside the template argument list.

Constants in templates

Template arguments are not restricted to class types; you can also use built-in types. The values of these arguments then become compile-time constants for that particular instantiation of the template. You can even use default values for these arguments:

Class Mblock is a checked array of objects; you cannot index out of bounds. (Again, the exception approach in Chapter XX may be more appropriate than assert( ) in this situation.)

The class Holder is much like Mblock except that it has a pointer to an Mblock instead of an embedded object of type Mblock. This pointer is not initialized in the constructor; the initialization is delayed until the first access. You might use a technique like this if you are creating a lot of objects, but not accessing them all, and want to save storage.

Stash and stack
as templates

It turns out that the Stash and Stack classes that have been updated periodically throughout this book are actually container classes, so it makes sense to convert them to templates. But first, one other important issue arises with container classes: When a container releases a pointer to an object, does it destroy that object? For example, when a container object goes out of scope, does it destroy all the objects it points to?

The ownership problem

This issue is commonly referred to as ownership. Containers that hold entire objects don't usually worry about ownership because they clearly own the objects they contain. But if your container holds pointers (which is more common with C++, especially with polymorphism), then it's very likely those pointers may also be used somewhere else in the program, and you don't necessarily want to delete the object because then the other pointers in the program would be referencing a destroyed object. To prevent this from happening, you must consider ownership when designing and using a container.

Many programs are very simple, and one container holds pointers to objects that are used only by that container. In this case ownership is very straightforward: The container owns its objects. Generally, you'll want this to be the default case for a container because it's the most common situation.

The best approach to handling the ownership problem is to give the client programmer the choice. This is often accomplished by a constructor argument that defaults to indicating ownership (typically desired for simple programs). In addition there may be read and set functions to view and modify the ownership of the container. If the container has functions to remove an object, the ownership state usually affects that removal, so you may also find options to control destruction in the removal function. You could conceivably also add ownership data for every element in the container, so each position would know whether it needed to be destroyed; this is a variant of reference counting where the container and not the object knows the number of references pointing to an object.

Stash as a template

The "stash" class that has been evolving throughout the book (last seen in Chapter XX) is an ideal candidate for a template. Now an iterator has been added along with ownership operations:

The enum owns is global, although you'd normally want to nest it inside the class. Here it's more convenient to use, but you can try moving it if you want to see the effect.

The storage pointer is made protected so inherited classes can directly access it. This means that the inherited classes may become dependent on the specific implementation of TStash, but as you'll see in the Sorted.cpp example, it's worth it.

The own flag indicates whether the container defaults to owning its objects. If so, in the destructor each object whose pointer is in the container is destroyed. This is straightforward; the container knows the type it contains. You can also change the default ownership in the constructor or read and modify it with the overloaded owns( ) function.

You should be aware that if the container holds pointers to a base-class type, that type should have a virtual destructor to ensure proper cleanup of derived objects whose addresses have been upcast when placing them in the container.

The TStashIter follows the iterator model of bonding to a single container object for its lifetime. In addition, the copy-constructor allows you to make a new iterator pointing at the same location as the existing iterator you create it from, effectively making a bookmark into the container. The forward( ) and backward( ) member functions allow you to jump an iterator by a number of spots, respecting the boundaries of the container. The overloaded increment and decrement operators move the iterator by one place. The smart pointer is used to operate on the element the iterator is referring to, and remove( ) destroys the current object by calling the container's remove( ).

The following example creates and tests two different kinds of Stash objects, one for a new class called Int that announces its construction and destruction and one that holds objects of the class String from Chapter XX.

In both cases an iterator is created and used to move through the container. Notice the elegance produced by using these constructs: You aren't assailed with the implementation details of using an array. You tell the container and iterator objects what to do, not how. This makes the solution easier to conceptualize, to build, and to modify.

stack as a template

The Stack class, last seen in Chapter XX, is also a container and is also best expressed as a template with an associated iterator. Here's the new header file:

You'll also notice the class has been changed to support ownership, which works now because the class knows the exact type (or at least the base type, which will work assuming virtual destructors are used). As with TStash, the default is for the container to destroy its objects but you can change this by either modifying the constructor argument or using the owns( ) read/write member functions.

The iterator is very simple and very small - the size of a single pointer. When you create a TStackIterator, it's initialized to the head of the linked list, and you can only increment it forward through the list. If you want to start over at the beginning, you create a new iterator, and if you want to remember a spot in the list, you create a new iterator from the existing iterator pointing at that spot (using the copy-constructor).

To call functions for the object referred to by the iterator, you can use the smart pointer (a very common sight in iterators) or a function called current( ) that looks identical to the smart pointer because it returns a pointer to the current object, but is different because the smart pointer performs the extra levels of dereferencing (see Chapter XX). Finally, the operator int indicates whether or not you are at the end of the list and allows the iterator to be used in conditional statements.

The entire implementation is contained in the header file, so there's no separate cpp file. Here's a small test that also exercises the iterator:

A TStack is instantiated to hold String objects and filled with lines from a file. Then an iterator is created and used to move through the linked list. The tenth line is remembered by copy-constructing a second iterator from the first; later this line is printed and the iterator - created dynamically - is destroyed. Here, dynamic object creation is used to control the lifetime of the object.

This is very similar to earlier test examples for the Stack class, but now the contained objects are properly destroyed when the TStack is destroyed.

Polymorphism & containers

It's common to see polymorphism, dynamic object creation and containers used together in a true object-oriented program. Containers and dynamic object creation solve the problem of not knowing how many or what type of objects you'll need, and because the container is configured to hold pointers to base-class objects, an upcast occurs every time you put a derived-class pointer into the container (with the associated code organization and extensibility benefits). The following example is a little simulation of trash recycling. All the trash is put into a single bin, then later it's sorted out into separate bins. There's a function that goes through any trash bin and figures out what the resource value is. Notice this is not the most elegant way to implement this simulation; the example will be revisited in Chapter XX when Run-Time Type Identification (RTTI) is explained:

This uses the classic structure of virtual functions in the base class that are redefined in the derived class. The container TStack is instantiated for Trash, so it holds Trash pointers, which are pointers to the base class. However, it will also hold pointers to objects of classes derived from Trash, as you can see in the call to push( ). When these pointers are added, they lose their specific identities and become simply Trash pointers (they are upcast). However, because of polymorphism the proper behavior still occurs when the virtual function is called through the tally and sorter iterators. (Notice the use of the iterator's smart pointer, which causes the virtual function call.)

The Trash class also includes a virtual destructor, something you should automatically add to any class with virtual functions. When the bin container goes out of scope, the container's destructor calls all the virtual destructors for the objects it contains, and thus properly cleans everything up.

Because container class templates are rarely subject to the inheritance and upcasting you see with "ordinary" classes, you'll almost never see virtual functions in these types of classes. Their reuse is implemented with templates, not with inheritance.

[BE1] Summary

Container classes are an essential part of object-oriented programming; they are another way to simplify and hide the details of a program and to speed the process of program development. In addition, they provide a great deal of safety and flexibility by replacing the primitive arrays and relatively crude data structure techniques found in C.

Because the client programmer needs containers, it's essential that they be easy to use. This is where the template comes in. With templates the syntax for source-code reuse (as opposed to object-code reuse provided by inheritance and composition) becomes trivial enough for the novice user. In fact, reusing code with templates is notably easier than inheritance and composition.

Although you've learned about creating container and iterator classes in this book, in practice it's much more expedient to learn the containers and iterators that come with your compiler or, failing that, to buy a library from a third-party vendor. The standard C++ library includes a very complete but nonexhaustive set of containers and iterators.

The issues involved with container-class design have been touched upon in this chapter, but you may have gathered that they can go much further. A complicated container-class library may cover all sorts of additional issues, including persistence (introduced in Chapter XX) and garbage collection (introduced in Chapter XX), as well as additional ways to handle the ownership problem.

Exercises

1. Modify the result of Exercise 1 from Chapter XX to use a TStack and TStackIterator instead of an array of Shape pointers. Add destructors to the class hierarchy so you can see that the Shape objects are destroyed when the TStack goes out of scope.

2. Modify the Sshape2.cpp example from Chapter XX to use TStack instead of an array.

3. Modify Recycle.cpp to use a TStash instead of a TStack.

4. Change SetTest.cpp to use a SortedSet instead of a set.

5. Duplicate the functionality of Applist.cpp for the TStash class.

6. You can do this exercise only if your compiler supports member function templates. Copy Tstack.h to a new header file and add the function templates in Applist.cpp as member function templates of TStack.

7. (Advanced) Modify the TStack class to further increase the granularity of ownership: add a flag to each link indicating whether that link owns the object it points to, and support this information in the add( ) function and destructor. Add member functions to read and change the ownership for each link, and decide what the _owns flag means in this new context.

8. (Advanced) Modify the TStack class so each entry contains reference-counting information (not the objects they contain), and add member functions to support the reference counting behavior.

9. (Advanced) Change the underlying implementation of Urand in Sorted.cpp so it is space-efficient (as described in the paragraph following Sorted.cpp) rather than time-efficient.

10. (Advanced) Change the typedef cntr from an int to a long in Getmem.h and modify the code to eliminate the resulting warning messages about the loss of precision. This is a pointer arithmetic problem.

11. (Advanced) Devise a test to compare the execution speed of an SString created on the stack versus one created on the heap.