Dan Saks is the president of Saks & Associates, which offers consulting and training in C++ and C. He is secretary of the ANSI and ISO C++ committees. Dan is coauthor of C++ Programming Guidelines, and codeveloper of the Plum Hall Validation Suite for C++ (both with Thomas Plum). You can reach him at 393 Leander Dr., Springfield OH, 45504-4906, by phone at (513)324-3601, or electronically at dsaks@wittenberg.edu.
This is the sixth and final installment of my series on designing and implementing generic container classes. A generic container class is a single definition for a particular kind of container class that you can adapt to hod objects of different types.
As I have throughout this series, in this installment I build on my example of a generic first-in-first-out queue with elements of type T. This generic queue began in Part 1 (CUJ, June 1994) as a class called genq that implemented a container with elements of type void *. Using void *as the element type relaxes static type checking enough so that a genq can hold the address of any type of data object. Unfortunately, using void * sacrifices too much safety and ease of use.
Part 2 (August, 1994) showed how a type-specific wrapper class can make a genq much safer and easier to use. It also explored different forms of iteration functions as a way to visit (iterate over) all the elements in a container and, in the process, apply some operation to each element. Part 3 (September, 1994) introduced iterator objects as a more general mechanism tor iterating through a container. An iterator is not part of its associated container, but it "knows" enough about the container's internals to be able to step from one object in the container to the next.
In Part 4 (October, 1994) I considered, and rejected, using polymorphism (inheritance and virtual functions) instead of wrapper classes as a way to provide a generic container with type information about the objects in the container. That is, I rewrote genq as comq, a queue with elements of type common * instead of void *, where common is an abstract base class for containable objects. It just didn't pan out.
Last month's Part 5 (November, 1995) explored the preprocessor as a tool for instantiating type-specific wrapper classes. The commonly available (but non-standard) header generic.h defines a small set of macros for automating the production of type-specific wrapper classes. The author of a generic class fashions additional macros that work with the generic.h macros so that users (application programmers) need only a few simple macro calls to instantiate and use the generic class for a particular type parameter T.
The general approach of using macros to instantiate generics shows a lot of promise, but still comes up short. While writing the macro calls that instantiate the generics is pretty easy and instantiated classes are indeed type-safe, the resulting code can be extremely hard to debug.
The crux of the problem is that each macro call expands on a single logical line. If you call the macro with an invalid argument, or there's a bug in the macro itself, the best that most compilers can do is tell you there's an error somewhere in the macro expansion. Furthermore, some (possibly many) symbolic debuggers won't let you set more than one breakpoint per line, or set a breakpoint in the interior of a line, making it hard to isolate problems in the member function bodies.
Templates to the Rescue
C++ programmers lived with these macros through the mid-1980s, but by the end of the decade, many felt they needed something better. In the fall of 1988, Bjarne Stroustrup (the inventor of C++) proposed adding a new language feature called templates, specifically for writing generic classes with compile-time type parameters [1]. The Annotated Reference Manual (ARM) [2] described templates as part of C++, but only as an experimental feature. The ANSI C++ standards committee added the ARM's description of templates (with minor changes) to the draft standard in July 1990, but template implementations weren't available to the general public until 1991.Templates are now available in many, but not all, C++ implementations. However, there's still so much variation among compilers that writing portable templates is, to say the least, a challenge. I'm not sure if it will ever be easy. The standards committee recently approved a major overhaul of the rules for templates. Most of the changes are clarifications, which should bring implementations into agreement. But some of the changes are new features, which usually cause more disagreements, at least temporarily.
This month, I provide my final example of a design approach for implementing generic queues — this time via templates. Along the way I explain how templates work and how to use them. I present a variety of styles for writing generic classes with templates, along with some thoughts on why you might prefer one style over another. I also alert you to some of the ways that templates vary across implementations.
Template Basics
In many ways, templates are like macros, but they're part of the language itself, not the preprocessor. Therefore, they offer implementers the opportunity to produce better compile-time diagnostics for erroneous instantiations, and better symbolic information for browsers, linkers, debuggers, profilers, and other development tools.A class template definition looks very much like any other class definition, except a class template begins with a heading of the form
template < parameter-list >template is a keyword in C++. The < > are delimiters (called "angle brackets" in this context) that enclose the template parameter list. The template parameter list is typically a type declaration of the form
class Tindicating that the class template accepts a single argument that names a type. For example, a declaration of the form
template <class T> class queue { ... };defines queue as a class template with type parameter T. A template parameter list can have more than one parameter (separated by commas), and other forms of parameters, but for now, we'll consider just this one simple form.The T in <class T> is the formal type parameter name. You use T as needed in the body of the template to refer to the actual type argument. (You can use any identifier instead of T; T is just a very popular choice.) The keyword class seems to suggest that T must be a class type, but it can be absolutely any type.
Once you've defined a queue template, queue<t> becomes a type name designating an instantiation of the template for some actual type t. For example, queue<int> is the type name for a queue with elements of type int. This notation is remarkably similar to that used with the generic.h macros. With the macros, you write queue<t> as queue(t).
You can use an instantiated template class name anywhere you can use any other type name. For instance,
queue<str> q;declares q as an object of type queue<str>. You can also use queue<str> in other contexts, such as
void reverse(queue<str> &q);or
typedef queue<str> str_queue;The construct queue<str> really is just another type name.
A Queue Class Template
With this general background, let's look at a real class template. Listing 1 shows header queue9.h containing a complete definition for a queue class template. (The 9 in queue9.h indicates that this is the 9th version of the generic queue class since the start of this series.) As with the last version of the macro-based generic queue class (Listing 5 from Part 5), this queue is not a wrapper around a genq.genqs contained pointers to objects, but the cells in this queue hold objects rather than pointers.Before we get too involved in the innards of the template, you might want to see how to use it. Listing 2 contains my test program for generic queues rewritten using the queue class template. The function test contains the declaration
queue<str> q[4];which declares q as an array with four elements of type queue(str).test doesn't contain any more explicit uses of the template notation, but the last line in the function
cout << i << ':' << q[i] << '\n';calls the operator<< declared near the top of the listing to put q[i] to cout.Said output operator uses the template twice, in the parameter list:
ostream &operator<<(ostream &os, queue<str> &q)and in the object declaration:
queue<str>::iterator sqi (q);The latter declares sqi as an object of type queue<str>::iterator, constructed to iterate through the queue<str> referenced by q. Class iterator is defined in Listing 1 as a public member of queue<T>. iterator is a member of a template; it is not a template itself. Therefore, you can't write the declaration as
queue::iterator<str> sqi(q);Now let's return to the template definition in Listing 1. The queue template uses T in various places to refer to the type argument. For example, the nested cell type:
struct cell { cell *next; T element; cell(const T &e, cell *p) : element(e), next(p) { } };has a data member of type T, and a constructor with a parameter of type const T &. The queue template even uses queue<T> to refer to another queue of the same type. For example, the nested iterator class has a constructor with a parameter of type
const queue<T> &This means that the argument to the iterator for a queue<T> must also be an object (or reference to an object) of type queue<T>.Note that the queue class template's constructor and destructor are declared as
queue(); ~queue();not as
queue<T>(); ~queue<T>();In both cases, you need not supply the type argument because the compiler can infer it from the context. Unfortunately, the ARM never explicitly stated when it was okay to omit the type parameter after the template name, and whether the omission was optional or mandatory. Compiler writers had to infer the rules from the examples and commentary. Needless to say, they inferred differently.The current working draft standard for C++ now says that within the scope of
template <class T> class X { ... };X and X<T> are equivalent. Thus, you can write the constructor for X as either X() or X<T>().A template definition can refer explicitly to an instantiation of the template for some other type U, by writing X<U>. For example,
template <class T> class X { X *p1; X<T> *p2; X<int> *p3; };defines class template X with three data members. p1 and p2 both have type X<T> *, but p3 has type X<int> *. Thus, if you declare
X<str> a;then both a.p1 and a.p2 have type X<str> *, but a.p3 has type X<int> *.This clarification of the rules for templates is fairly recent. I haven't yet seen a compiler that behaves accordingly. For the time being, it appears that your safe bet is to
- omit the template argument(s) after the template name when it's used to form the name of the constructor or destructor,
- use the template argument(s) after the template name when it's used in all other contexts.
Template Member Definitions
As with any other class definition, a class template definition contains member function declarations. You can define a member function in situ (by including the function body as part of the function declaration), but that leads to cluttered class definitions. I recommend writing the function definitions elsewhere.Every member function definition for a class template must begin with
template <class T>and must include the <T> after the template name in the fully-qualified function name. For example,
template <class T> void queue<T>::append(const T &e) { ... }defines the append function for queue<T>. To declare the function as inline, add the keyword inline after the template parameter list, as in
template <class T> inline queue<T>::~queue() { clear(); }Just as I prefer writing member function definitions outside the class, I prefer writing nested class definitions outside their enclosing class too. Unfortunately, forward-declared nested classes don't seem to work with class templates. I can't find a compiler that will let me declare queue<T>::cell or queue<T>::iterator as forward-declared nested classes, as I tried to do in Listing 3. My reading of the draft C++ standard is that the forward-declarations should work, but maybe I missed something.I encountered a similar problem in writing the function definitions for member functions of classes nested within the class template. In particular, I tried defining the body of the cell constructor outside the queue class template definition, as shown in Listing 4. Again, none of the half dozen compilers I use (under DOS/Windows) would accept it. I don't mind so much defining the cell and iterator constructors in situ; they're short enough. However, iterator::next() is much longer, and I really don't like defining it in situ.
Given the current state of C++ compilers, your safest bet might be to avoid mixing nested classes and templates. Rather than implement the cell and iterator types as members of the queue class template, implement them as separate class templates queue_cell<T> and queue_iterator<T>, respectively. The header queue10.h in Listing 5 shows the definition for queue<T> rewritten using queue_cell<T> and queue_iterator<T>.
When an application includes queue9.h (which uses nested cell and iterator classes), queue9.h introduces only one name, queue, into the application's global namespace. The application can access queue<T>::iterator because iterator is a public member. This is as it should be; the iterator is part of the queue interface. The application can't access queue<T>::cell because cell is private. This too is as it should be because the cell type is an implementation detail, which should be inaccessible to the application.
In contrast, including queue10.h (which avoids nested classes) introduces three global names: queue_cell and queue_iterator, as well as queue. Declaring queue_iterator as a global name doesn't really make it any more accessible than when it was a public nested class. However, declaring queue_cell as global is akin to declaring the cell type as part of the queue's public interface. This is not good.
The solution to this problem is a technique I introduced in Part 1 of this series (June 1994). That is, declare all of queue_cell's members, including the constructor, as private. Hence, an application can't create objects of type queue_cell<T> because the constructor is inaccessible. This effectively removes queue_cell from the queue interface. But the members of queue<T> and queue_iterator<T> must be able to create queue_cell<T> objects, so queue_cell<T> declares both queue<T> and queue_iterator<T> as friend classes.
Template Instantiation
The generic.h macros provide two macros, declare and implement, for explicitly instantiating templates. A macro call of the form
declare(C, T)generates the class and inline member function definitions for genetic class C instantiated with type argument T. For example, if queue is a generic class, then
declare(queue, int)instantiates the class definition for a queue of int. A macro call of the form
implement(C, T)instantiates the non-inline parts of the implementation for generic class C with type argument T. For example,
declare(queue, str)instantiates the non-inline member functions for a queue of str. Listing 1 and Listing 5 both contain comments to indicate which parts of the template definition correspond to the declarations that would be generated by the declare and implement macros, respectively.Template classes do not require explicit instantiation. The translator instantiates the templates automatically. C++ implementations differ in the way they instantiate templates, but most follow a common conceptual model.
When the compiler encounters the name of a template instantiation such as queue<str> for the first time in a compilation unit, it automatically instantiates the class definition (the "declare" part) for queue<str>. When the linker combines all the compilation units into a single program, it must insure that there's exactly one copy of the non-inline member function definitions and static data member definitions (the "implement" part) for each instantiation of the template anywhere in the program.
Some compilers require you to put both the "declare" and "implement" parts of the template definition in the header (as in Listing 1 and Listing 5) . When the compiler sees a template instantiation such as queue<str>, it generates a class definition and code for the member functions of queue<str>. In other words, it generates both the "declare" and "implement" parts of the template class as part of the current object module. When the linker combines the object modules, it merges all the duplicate copies of a template class member function into a single function. (If you prefer, you can say the linker throws away the duplicates.)
Other compilers allows you to put only the "declare" part of the template definition in the header, and put the "implement" part in a separate source file. (The compiler might insist that the header and source file have the same file name but different file extensions.) When the compiler encounters a template instantiation, it generates the "declare" part of the template, and makes a notation in the object code that it will need a copy of the "implement" part somewhere along the line. As the linker combines the object modules, it locates the "implement" parts it needs and links them in.
Many compilers offer more than one strategy for instantiating templates, and provide compiler switches or pragmas that let you choose. Everybody does it differently. Read your user's guide.
Code Bloat
Each instantiation of a template for a different type argument generates an entirely new copy of the member functions. For example, queue<int> instantiates one copy of the template member functions, and queue<str> generates another.Templates share source code, but they generally do not share object code. Thus, if a single program instantiates a template with many different type arguments, the program may become bloated with many copies of nearly identical code.
You can reduce this bloating by extracting the code that's common to every instantiation and placing it in a separate class. Then you rewrite the template member functions as shorter functions that delegate work to an object of this common type. If this approach sounds familiar, that's because it is. It's essentially a wrapper class design.
Listing 6 shows class queue as a template for a generic queue implemented as a wrapper around a genq. genq captures much of the logic common to every queue instantiation. As a consequence, each template instantiation generates less code.
That's a Wrap
Despite their imperfections, templates are extremely useful. Dare I say they may be more useful than virtual functions. I think they are the right tool for implementing many common data structures. As with any relatively new feature, use templates conservatively and cheek your templates against more than one compiler.
References
[1] Bjarne Stroustrup. "Parameterized Types for C++," appearing in both Proceedings of the USENIX C++ Conference, Denver, CO, October: 1988, and in USENIX Computer Systems, Vol. 2, No. 1, Winter: 1989.[2] Margaret Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual. (Addison-Wesley, 1990).