6.1 Parameterized Types

Here is a nontemplate declaration of the BTnode class in which the stored value is a string class object. I call it string_BTnode because we must define other instances that store values of type int, double, and so on.

class string_BTnode { 


public: 


    //  ... 


private: 


   string _val; 


   int _cnt; 


   int_BTnode *_lchild; 


   int_BTnode *_rchild; 


}; 

Without the template mechanism, each type would need its own separately implemented BTnode class, and each would need to be named uniquely.

The template mechanism allows us to separate the type-dependent and invariant portions of our class definition. The code that traverses the tree, inserts and removes nodes, and maintains the occurrence count is the same regardless of the value's type. This code is reused with each instance of the class template.

The value's type stored within each node changes with each instance of the class template, in one case representing a string object, in another an int or double, and so on. In a class template, type dependencies are factored into one or more parameters. In our BTnode class, the type of the data member _val is parameterized:

// forward declaration of BTnode class template 


template <typename valType> 


class BTnode; 

valType is used within the template class definition as a placeholder. We can give it any name we wish. It serves as a wild card until we specify an actual type. A type parameter can be used anywhere that an actual type, such as int or string, can be used. In the BTnode class, it is used to declare the type of _val:

template < typename valType > 


class BTnode { 


public: 


    //  ... 


private: 


   valType     _val; 


   int         _cnt; 


   BTnode     *_lchild; 


   BTnode     *_rchild; 


}; 

The BTnode class template collaborates with the BinaryTree class template in the implementation of our abstraction. The BTnode class holds the actual value, the occurrence count, and the pointers to the left and right children. Recall that collaborative class relationships usually require friendship. For each actual type of BTnode class, we want the corresponding BinaryTree instance to be its friend. Here is how we declare that:

template <typename Type> 


class BinaryTree;  // forward declaration 





template <typename valType> 


class BTnode { 


   friend class BinaryTree<valType>; 


   // ... 


}; 

To create an instance of the class template, we follow the class template name with an actual type we want to substitute for valType enclosed in angle brackets. For example, to bind valType to type int, we write

BTnode< int > bti; 

Similarly, to bind valType to the class string type, we write

BTnode< string > bts; 

bti and bts represent two definitions of BTnode: one for which _val is defined as an int, and one for which _val is defined as a string. The corresponding BinaryTree string instance is a friend to the BTnode string instance but not to the BTnode int instance.

The BinaryTree class declares one data member, a BTnode pointer to the root node of the tree:

template <typename elemType> 


class BinaryTree { 


public: 


    // ... 


private: 


    // BTnode must be qualified with its template parameter list 


    BTnode<elemType> *_root; 


}; 

How do we know when to qualify the class template name with its parameter list? The general rule is that within the definition of the class template and its members, the template class name does not need to be qualified. A template class name must otherwise be qualified with its parameter list.

When we specify an actual type for the BinaryTree parameter, such as

BinaryTree< string > st; 

_root becomes a pointer to a BTnode object holding a value of type string. Similarly, when we specify an int type,

BinaryTree< int > it; 

_root becomes a pointer to a BTnode object holding a value of type int.