Previous Section
 < Free Open Study > 
Next Section


4.2 More about Generics: C++ Templates

In Chapter 3, we defined a generic data type as a type for which the operations are defined but the types of the items being manipulated are not. We have demonstrated how the list and stack types can be generic by defining the type of the items included in the structure in a separate file, ItemType.h, and then having ListType.h and StackType. h include that file. This technique works for any language that allows you to include or access other files. Some languages, however, have special constructs that allow you to define generic data types. In C++, this construct is called a template. A template allows you to write a description of a class type with "blanks" left to be filled in by the client code. Just as variables serve as the parameters to functions, types serve as the parameters to templates.

Template A C++ language construct that allows the compiler to generate multiple versions of a class type or a function by allowing parameterized types

Let's look at how this construct works using the Stack ADT.

template<class ItemType>
class StackType
{
public:
  StackType();
  bool IsEmpty() const;
  bool IsFull() const;
  void Push(ItemType item);
  void Pop();
  ItemType Top() const;
private:
  int top;
  ItemType items[MAX_ITEMS];
};

This code is known as a class template. The definition of StackType begins with template<class ItemType>, and ItemType is called the formal parameter to the template. (You could use any identifier for the formal parameter; we use ItemType in this example.) The client program uses code like the following to create several stacks whose components are of different data types:

// Client code
StackType<int> myStack;
StackType<float> yourStack;
StackType<StrType> anotherStack;
myStack.Push(35);
yourStack.Push(584.39);

In the definitions of myStack, yourStack, and anotherStack, the data type name enclosed in angle brackets is the actual parameter (or argument) to the template. At compile time, the compiler generates (instantiates) three distinct class types and gives its own internal name to each type. You might imagine that the definitions are transformed internally into something like this:

StackType_int myStack;
StackType_flo yourStack;
StackType_str anotherStack:

In C++ terminology, the three new class types are called template classes (as opposed to the class template from which they were created).

When the compiler instantiates a template, it literally substitutes the actual parameter for the formal parameter throughout the class template, just as you would perform a search-and-replace operation in a word processor or text editor. For example, when the compiler encounters StackType<float> in the client code, it generates a new class by substituting float for every occurrence of ItemType in the class template. The result is the same as if we had written the following:

class StackType_float
{
  
  void Push(float item);
  void Pop();
  float Top() const;
private:
  int top;
  float items[MAX_ITEMS];
};

A useful perspective on templates is this: An ordinary class definition is a pattern for stamping out individual variables or objects, whereas a class template is a pattern for stamping out individual data types.

There are two things to note about parameters to templates. First, the class template uses the word class in its formal parameter list: template<class ItemType>. However, the use of class is simply required syntax and does not mean that the client's actual parameter must be the name of a class. The actual parameter can consist of the name of any data type, built-in or user-defined. In the client code just shown, we used int, float, and StrType as actual parameters. Second, observe that when the client passes a parameter to the StackType template (as in StackType<int>), the parameter is a data type name, not a variable name. This usage seems strange at first, because when we pass parameters to functions, we always pass variable names or expressions, not data type names. Furthermore, note that passing a parameter to a template has an effect at compile time, whereas passing a parameter to a function has an effect at run time.

Now that we've seen how to write the definition of a class template, how do we handle the definitions of the member functions? We need to write them as function templates so that the compiler can associate each one with the proper template class. For example, we code the Push function as the following function template:

template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

Just as with the class template, we begin the function definition with template<class ItemType>. Next, every occurrence of the word StackType must have <ItemType> appended to it. If the client has declared a type StackType<float>, the compiler generates a function definition similar to the following:

void StackType<float>::Push(float newItem)
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

Finally, when working with templates, we change the ground rules regarding the file(s) into which we put the source code. Previously, we placed the class definition into a header file StackType. h and the member function definitions into StackType. cpp. As a result, we could compile StackType.cpp into object code independently of any client code. This strategy won't work with templates. The compiler cannot instantiate a function template unless it knows the actual parameter to the template, and this actual parameter appears in the client code. Different compilers use different mechanisms to solve this problem. One general solution is to compile the client code and the member functions at the same time. A popular technique is to place both the class definition and the member function definitions into the same file: StackType.h. Another technique involves giving the include directive for the implementation file at the end of the header file. Either way, when the client code specifies #include "StackType.h", the compiler has all the source code-both the member functions and the client code-available to it at once. The following code lists the contents of both the class definition and the function implementations. Pay close attention to the required syntax of the member function definitions.

// The class definition for StackType using templates.

class FullStack
// Exception class used by Push when stack is full.
{};

class EmptyStack
// Exception class used by Pop and Top when stack is empty.
{}:

#include MaxItems.h
// MaxItems.h must be provided by the user of this class.
// This file must contain the definition of MAX_ITEMS,
// the maximum number of items on the stack.

template<class ItemType>
class StackType
{
public:
  StackType();
  bool IsEmpty() const;
  bool IsFull() const;
  void Push(ItemType item);
  void Pop();
  ItemType Top() const;
private:
  int top;
  ItemType items[MAX_ITEMS];
};

// The function definitions for class StackType.
template<class ItemType>
StackType<ItemType>::StackType()
{
  top = -1;
}

template<class ItemType>
bool StackType<ItemType>::IsEmpty() const
{
  return (top = = -1) ;
}

template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
  return (top = = MAX_ITEMS-1);
}
template<class ItemType>
void StackType<ItemType>::Push(ItemType newItem)
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

template<class ItemType>
void StackType<ItemType>::Pop()
{
  if (IsEmpty())
    throw EmptyStack();
  top--;
}

template<class ItemType>
ItemType StackType<ItemType>::Top() const
{
  if (IsEmpty())
    throw EmptyStack();
  return items [top] ;
}


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)