COMP2012H

Bonus Lab 3: Function Templates and Class Templates

Objectives

• To learn using function templates and class templates

Download

• Lab slides
• templatefunc.cpp demonstrates function templates.
• templateclass.cpp demonstrates class templates.

Motivations

Templates let you reuse the source code by providing the compiler a way of substituting type names in the body of a function or a class. This helps you in designing and using container class libraries, which play an important role in the development of object-oriented software.  It is a much more powerful way than using typdef, as it needs recompilation on your definition files and turns the class into using one type instead of multiple types.

Generic Programming

What are templates?

Templates are mechanisms for generating functions and classes based on type parameters (So, not surprisingly, templates are sometimes called "parameterized types"). Templates are relatively new additions to the C++ language. They provide a generic way to develop reusable code. There are two basic types of templates: function templates and class templates. By using templates, you can design a single class template that operates on data of many types, instead of having to create a separate class for each type.

Advantages of using templates

• Templates make coding simpler as you do not have to write several versions of very similar code for different purposes. You may create only one generic version of your class or function instead of manually creating specializations.
• Templates are easier to understand, since they can provide a straightforward way of abstracting type information.
• Templates are type-safe. This is because the types that templates act upon are known at compilation time, so the compiler can perform type checking before error occurs.
• Templates help utilizing compiler optimizations to the extreme.

Developer Tip: The bottomline is that if you are writing the same code again for two or more different data types, then you should have been using templates.

Function Templates

Working with templates

We define a function template as follows. Let us take for example a simple function that returns the minimum of two integers:

// type int

int min(const int& t1, const int& t2) {

   return t1 < t2 ? t1 : t2;

};

This function works for all integers.

Now, suppose you are required to implement again a function for finding the minimum of two real numbers:

// type double

double min(const double& t1, const double& t2) {

   return t1 < t2 ? t1 : t2;

};

Now, the template solution for this is as follows (templatefunc.cpp):

// template function

template<typename T>

T min(const T& t1, const T& t2) {

   return t1 < t2 ? t1 : t2;

};

This defines a series of functions which can act upon all data types that satisfy the operators/conditions inside the template function. Each time the template is "instantiated", we get a separate function for finding the minimum.

Instantiation

To "instantiate" a function template, call it with any of the valid data types (by "valid", we refer to a data type on which the required operators are defined).

For example (write this code in the main( ) function),

// instantiate template function with int

int i = min(10, 20);

// instantiate template function with double

double d = min(10.0, 20.0);

However, note that the compiler would not allow you to mix data types, e.g., min(4, 5.5) would give you an error. To get around it, of course sometimes you can perform type casting, or specify the instantiation of the function:

// instantiate template function with int and double

double d = min(4.5, 5);  // error

// instantiate template function explicitly

double d = min<double>(4.5, 5);

Class Templates

Working with templates

Suppose we want to implement a stack class template as follows (templateclass.cpp).

template <class T, int N>

   class Stack {

      public:

         Stack() { top = -1; }

         virtual ~Stack(){ }

         inline void Push(T var);

             T Pop(){

             cout << "Popping " << st[top] << " from ";

             cout << "top = " << top << endl << flush;

             return st[top--];

         }

      protected:

         T st[N];

         int top;

};

//Definition of a function external to the class

template <class T, int N>

void Stack<T, N>::Push(T var) {

   cout << "Pushing " << var << " at ";

   cout << "top = " << top+1 << endl << flush;

   st[++top] = var;

}             

Instantiating

When you are instantiating a class template, unlike function templates, you should explicitly instantiate the class by giving the arguments for the class template. To instantiate and test our stack class template, we have to use the following.

Stack<float, 3> floatStack;

floatStack.Push(10.0);

floatStack.Push(20.0);

floatStack.Push(40.0);

floatStack.Pop();

floatStack.Pop();

floatStack.Pop();

Lab Task

Download list.h and main.cpp.

Part I. Change to be template

The current implementation of the list class is a non-template one.  Change it to a list class based on template by modifying the list.h only.  (Do NOT change the main.cpp.)

 

Part II. Implement member functions in template

Implement the function Add, Print, and Find.

• Add e: add a new Node with element item to the head of the list
• Print: print out the whole list from head to tail
• Find: find the item in the list, and count how many elements (cost) you have visited when you find it.

After modification, you should be able to compile and run the program. The following output should be shown:

Original:

<f b h c d e g a >

Reverse:

<a g e d c h b f >

Reverse again:

<f b h c d e g a >

Enter the item you want to find: b

2