Writing a Class Template

Problem

You have a class whose members need to be different types in different situations, and using conventional polymorphic behavior is cumbersome or redundant. In other words, as the class designer, you want a class user to be able to choose the types of various parts of your class when he instantiates it, rather than setting them all in the original definition of the class.

Solution

Use a class template to parameterize types that can be used to declare class members (and much more). That is, write your class with placeholders for types; thus, leaving it to the user of the class template to choose which types to use. See Example 8-12 for an example of a tree node that can point to any type.

Example 8-12. Writing a class template

#include 
#include 

using namespace std;

template
class TreeNode {
public:
 TreeNode(const T& val) : val_(val), left_(NULL), right_(NULL) {}
 ~TreeNode( ) {
 delete left_;
 delete right_;
 }

 const T& getVal( ) const {return(val_);}
 void setVal(const T& val) {val_ = val;}
 void addChild(TreeNode* p) {
 const T& other = p->getVal( );
 if (other > val_)
 if (right_)
 right_->addChild(p);
 else
 right_ = p;
 else
 if (left_)
 left_->addChild(p);
 else
 left_ = p;
 }
 const TreeNode* getLeft( ) {return(left_);}
 const TreeNode* getRight( ) {return(right_);}

private:
 T val_;
 TreeNode* left_;
 TreeNode* right_;
};

int main( ) {

 TreeNode node1("frank");
 TreeNode node2("larry");
 TreeNode node3("bill");

 node1.addChild(&node2);
 node1.addChild(&node3);
}

 

Discussion

Class templates provide a way for a class designer to parameterize types, so that they can be supplied by a user of the class at the point the class is instantiated. Templates might be a bit confusing though, so let me go through the example before coming back to how it works.

Consider the declaration of the treeNode class template in Example 8-12:

template
class TreeNode { //...

The template part is what makes this a class template and not an ordinary class. What this line says is that T is the name of a type that will be given when the class is used, but not right now where it is declared. The parameter T can then be used throughout the declaration and definition of TReeNode as if it were any other type, native or user defined. For example, I have a private member named val_ that I want to be of type T, so I declare it like this:

T val_;

This simply declares a class member named val_ of some type that will be determined later in the same way I would declare an int, float, MyClass, or string named val_. In this respect, you can think of it as something like a macro (i.e., using #define), although the similarity with macros is little more than that.

Your type parameter can be used in any way you would use an ordinary parameter: return values, pointers, member function parameters, and so on. Consider my getter and setter methods for val_:

const T& getVal( ) const {return(val_);}
void setVal(const T& val) {val_ = val;}

getVal returns a const reference to val_, which is of type T, and setVal takes a reference to a T and sets val_ equal to it. Things get a little messier when it comes to the getLeft and getright member functions, so I'll come back to those in a minute. Bear with me.

Now that treeNode has been declared with a type placeholder, some client code somewhere has to use it. Here's how.

TReeNode is a simple implementation of a binary tree. To create a tree that stores string values, create your nodes like this:

TreeNode node1("frank");
TreeNode node2("larry");
TreeNode node3("bill");

The type between the angle brackets is what gets used for T when this class template is instantiated. Template instantiation is the process the compiler goes through when it builds a version of treeNode where T is string. A binary, physical representation of TReeNode is created when it is instantiated (and only when it is instantiated). What you get is a memory layout that is equivalent to if you had just written treeNode without the template keyword and type parameter, and used a string everywhere you used a T.

Instantiation of a template for a given type parameter is analogous to instantiation of an object of a class. The key difference is that template instantiation occurs at compile time, while object instantiation occurs at runtime. This means that if, instead of a string, you wanted your binary tree to store ints, you would declare nodes like this:

TreeNode intNode1(7);
TreeNode intNode2(11);
TreeNode intNode3(13);

As with the string version, a binary entity is created for the treeNode class template using int as the internal type.

A minute ago, I said I would revisit the getLeft and getright member functions. Now that you are familiar with template instantiations (if you weren't already), the declaration and definition of getLeft and getright may make more sense:

const TreeNode* getLeft( ) {return(left_);}
const TreeNode* getRight( ) {return(right_);}

What this says is that each of these member functions returns a pointer to an instantiation of treeNode for T. Therefore, when treeNode is instantiated for, say, a string, getLeft and getright are instantiated like this:

const TreeNode* getLeft( ) {return(left_);}
const TreeNode* getRight( ) {return(right_);}

You aren't limited to one template parameter though. You can use a bunch of them, if you like. Imagine that you want to keep track of the number of children below a given node, but users of your class may be pressed for space and not want to use an int if they can get away with a short. Similarly, they may want to supply something other than a simple, built-in type to tally the node usage, like their own number class. In any case, you can allow them to do so with another template parameter:

template
class TreeNode {
// ...
 N getNumChildren( );

private:
 TreeNode( ) {}
 T val_;
 N numChildren_;
// ...

This way, the person using your class can supply an int, short, or anything else he wants to keep track of subtree size on each node.

You can also supply default arguments for template parameters, as I just did in the example, with the same syntax you would use to declare default function parameters:

template

As with default function arguments, you can only supply them for a given parameter if it is either the last parameter or each parameter to the right of it has a default argument.

In Example 8-12, the definition for the template is given in the same place as the declaration. Usually, I do this to conserve space in example code, but, in this case, there is another reason. Templates (classes or functionssee Recipe 8.12) are only compiled into binary form when they are instantiated. Thus, you cannot have the template declaration in a header file and its implementation in a source file (i.e., .cpp). The reason is that there is nothing to compile! There are exceptions to this, but, generally speaking, if you are writing a class template, you should put its implementation in the header file or in an inline file that is included by the header.

If you do this, you will need to use a syntax that is a little unfamiliar. Declare the member functions and the rest of the class template as you would an ordinary class, but when you are defining the member functions, you have to include some extra tokens to tell the compiler that this is for a class template. For example, you would define getVal like this (compare this to Example 8-12):

template
const T& TreeNode::getVal( ) const {
 return(val_);
}

The body of the function looks the same.

Be careful with templates though, because if you write one that is used everywhere, you can get code bloat, which is what happens when the same template with the same parameters (e.g., treeNode) is compiled into separate object files. Essentially, the same binary representation of an instantiated template is in multiple files, and this can make your library or executable much larger than it needs to be.

One way to avoid this is to use explicit instantiation, which is a way to tell the compiler that it needs to instantiate a version of the class template for a particular set of template arguments. If you do this in a place that is a common location that will be linked to by multiple clients, you can avoid code bloat. For example, if I know that throughout my application I will be using treeNode, I would put a line like this in a common source file:

// common.cpp
template class TreeNode;

Build a shared library with that file and then code that uses TReeNode can use the library dynamically without having to contain its own compiled version. Other code can include the header for the class template, then link to this library and therefore avoid needing its own copy. This requires some experimentation though, because not all compilers have the same problems with code bloat to the same degree, but this is the general approach you can use to minimize it.

C++ templates (both class and function) are a vast subject, and there is a long list of mind-bending techniques for powerful, efficient designs that use templates. A great example of applications of class templates is the standard library containers, e.g., vector, list, set, etc., which is the subject of Chapter 15. Most of the interesting developments that are happening in the C++ literature have to do with templates. If you are interested in the subject, you should check out the newsgroups comp.lang.std.c++ and comp.lang.c++. There are always interesting questions and answers there.

See Also

Recipe 8.12