Thursday, October 26, 2006

Templates

Topics

Templates

- What if we need both a stack of floats and a stack of ints?
- Also consider other classes such as lists, or collections, arrays, sets, etc...  There are many classes where the basic implementation is the same, but type is different.
- C++ Templates is a facility to provide abstraction across different types
- Templates provide a mechanism to avoid repetitive code that is applicable with many different types.
- Feature added in mid-1990's, after the initial development of C++, in 1983, at AT&T Bell labs
- One of the most powerful features of C++ providing reuse
- Template is a parameterized class type
- The parameter is the type that we wish to vary
- Type can be a parameter in the definition of a class or a function
- Parameters specify customization of a "generic" template to create specific functions/classes
- Templates are a compile-time mechanism so that use incurs no run-time overhead
- Important: Since the compiler does not actually create a class from a template until one is declared in the .C file, all the template code must be in the .h file, even the function definitions.  This is a violation of normal C++ style.   
 

Class Templates

Example Syntax

template < class T >
class Stack
{
public:
    Stack(int);
    bool push( T& );
    bool pop( T& );
    ...

private:
    T* array;
    ...

};

template < class T >
    - Specifies that a template is being declared
    - Specifies that a "type argument" (T) will be used in the declaration

- Note that T is used exactly like other type names (i.e. float, int, other classes, ...)
  T *array;  // pointer to a T -- will hold the array
 bool push( T& ); // method, parameter is ref to T
 bool pop( T& );  // method, parameter is ref to T
 

- We wish to create multiple types of stacks (stack of int's, stack of float's, etc...)
- We denote our class to be a template class with a type parameter T
- We can name our parameter anything, doesn't have to be T
- When referring to the type in our class, we now use T
- Template class can serve as a both a base and a derived class
 

Example - "templated" stack class

#include <iostream>

#define DEFAULT_SIZE 10

using namespace std;

template<class T>
class Stack
{
public:

 // Construction
 Stack(int s);
 ~Stack();

 // Push on top of stack
 bool push(T&);

 // Pop off top of stack
 bool pop(T&);

 // Is stack empty?
 bool isEmpty();
 

private:
 T *array;   // holds stack values
 int size;   // size of stack
 int top;    // top position on stack

};

// Constructor
template<class T>
Stack<T>::Stack(int s)
{
 if (s > 0)
   size = s;
 else
   size = DEFAULT_SIZE;
 array = new T[size];
 top = -1;
}

// Destructor
template<class T>
Stack<T>::~Stack()
{
 if( array ) delete[] array;
}

// push method
template<class T>
bool Stack<T>::push(T& value)
{
 if( top < size-1 )
 {
  // Assign value to top position
  array[ ++top ] = value;
  return true;
 }
 else
 {
  // Cannot push any more values
  cout << "  Warning: stack overflow!" << endl;
  return false;
 }
}

// pop method
template<class T>
bool Stack<T>::pop(T& value)
{
 if( top >= 0 )
 {
   // Return top of stack, decrement top index
   value = array[ top-- ];
   return true;
 }
 else
 {
  // Cannot return any more values
  cout << "  Warning: stack underflow!" << endl;
  return false;
 }

}
 

// isEmpty method
template<class T>
bool Stack<T>::isEmpty()
{
 return (top == -1) ? true : false;
}

 

Example 1 - stack of integers

void main()
{
 Stack<int> intstack(3);
 int value = 77;
 int i;

 // Pushing on stack
 for( i = 0; i < 3; ++i, value += 1 )
 {
  cout << "Pushing value: " << value << endl;
  intstack.push(value);
 }

 // Popping off stack
 for( i = 0; i < 3; ++i )
 (
   if (intstack.pop(value))
    cout << "Popped off value: " << value << endl;
 }
}

Output
Pushing value: 77
Pushing value: 78
Pushing value: 79
Popped off value: 79
Popped off value: 78
Popped off value: 77
 
 

Example 2 - stack of floats

void main()
{
 Stack<float> floatstack(3);
 float value = 77.34;
 int i;

 // Pushing on stack
 for( i = 0; i < 3; ++i, value += 1.0 )
 {
  cout << "Pushing value: " << pv << endl;
  floatstack.push(value);
 }

 // Popping off stack
 for( i = 0; i < 3; ++i )
 {
  if(floatstack.pop(value))
    cout << "Popped off value: " << value << endl;
 }
}
 

Output
Pushing value: 77.34
Pushing value: 78.34
Pushing value: 79.34
Popped off value: 79.34
Popped off value: 78.34
Popped off value: 77.34
 
 

Example 3 - stack of Points!

// Point class
class Point
{
 friend ostream &operator<<(ostream &strm, Point &);

protected:
 float x, y, z;
 float size;

public:

 // Constructor
 Point( float c1=0.0, float c2=0.0, float c3=0.0 )
 {
  x = c1;
  y = c2;
  z = c3;
  size = 0.0;
 }

 Point &operator+=(Point &);
 
 

 // Access methods
 float setSize( float f ) { size = f; }
 float getSize() { return size; }
};

// Overloaded output stream operator
ostream &::operator<<(ostream &strm, Point &t)
{
 strm << "  x, y, z: " << t.x << "," << t.y << "," << t.z;
 return strm;
}
Point &Point::operator+=(Point &t)
{
 x += t.x;
 y += t.y;
 z += t.z;
 return *this;
}
 

// Application - stack of Points!
void main()
{
 Stack<Point> pointstack(3);
 Point pv(1,2,3);
 Point pi(1,1,1);
 int i;

 // Pushing on stack
 for( i = 0; i < 3; ++i, pv += pi )
 {
  cout << "Pushing value: " << pv << endl;
  floatstack.push(pv);
 }

 // Popping off stack
 for( i = 0; i < 3; ++i )
 {
  if (floatstack.pop(pv))
      cout << "Popped off value: " << pv << endl;
 }
}
 

Output
Pushing value:   x, y, z: 1,2,3
Pushing value:   x, y, z: 2,3,4
Pushing value:   x, y, z: 3,4,5
Popped off value:   x, y, z: 3,4,5
Popped off value:   x, y, z: 2,3,4
Popped off value:   x, y, z: 1,2,3

- Compiler associates types with parameter T
- Programmer doesn't need to generate additional code!
 
 

Function templates
- Individual functions/methods can be constructed as a template
- Similar to function overloading when type is the only thing that changes
- Might consider a function template instead of multiple overloaded functions
- Similar syntax to class templates

 
#include <iostream.h>

// Function template
template< class T >
void printArray( T *array, int count )
{
 for( int i = 0; i < count; ++i )
  cout << array[i] << endl;
}

void main()
{
 int ival[3] = { 0, 1, 2 };
 char cval[6] = { 'c', 's', 'c', '1', '2', '5' };

 printArray( ival, 3 );
 printArray( cval, 6 );
}
 

Readings

Deitel & Deitel Fourth Edition: 11.1 - 11.4