Section 4 - Deeper Into Class Templates

8A.4.1 More on Class Templates

Now that we have seen an example of a template, let's review and expand our understanding of these things.

Suppose we write a queue of Galaxies (not a STL queue, but our own custom queue) in a class we call QGalaxy, and later want a queue of Cards. Before we had templates we might have taken the QGalaxy and converted it to a queue of Cards, manually, using copy/paste then changing the name of the new class to QCard, doing a global search-and-replace on the word Galaxy, replacing it with Card, cleaning up any other code manually that is not applicable to Cards. Not good.

Templates have allowed us to work smarter. We now know to implement a generic Queue by using special notation which (as we saw in our SafeArray) includes a type parameter (usually T). T can be replaced with an actual type when we are ready to apply our template to a specific class like Cards. Thus, if we make a template, Queue, we can later apply it to the Card class with notation like Queue<Card>, and if we want a queue of Galaxies, we can likewise declare that using the notation Queue<Galaxy>. If we ever need to modify the implementation of our template Queue, the changes will be reflected in the classes Queue<Galaxy>, Queue<Card>, and any other Queue classes that we might declare using Queue<Our_Class>.

Templates provide a way to re-use source code as opposed to inheritance which provides a way to re-use object code. When you create a class based on a pre-written template, you are asking the compiler to generate an entirely new class behind the scenes, but one that is, nevertheless, a kind of duplication, from scratch, of the source code in the template definition. We might not think about the difference between an inherited class (which does not generate more base class source code) and one based on a template (which does create new copies of the template source), but the difference is very real.

8A.4.2 Prototyping and Defining a Class Template

We can write class templates using the two part approach: first prototype then definition(s), just as we did with ordinary class creation. There are some differences, so let's break the process down.

8A.4.2.1 Prototyping a Class Template

A class template prototype looks like a regular class definition, except it is prefixed by a phrase like template <class T>, where the T can be any formal parameter. For example, here is the prototype of a class template for a Stack.

template <class T>
class Stack
{
public:
  const static int MAX_STACK = 100;
  Stack(int = MAX_STACK);
  ~Stack() { delete [] stackPtr; }
  bool push(const T&);
  bool pop(T&);
  int isEmpty()const { return top == -1; }
  int isFull() const { return top == (size - 1); }

 private:
  int size;  // number of elements on Stack.
  int top;
  T* stackPtr;
};

T is a type parameter and it holds the place of the specific types that we will ultimately use. In a moment, we'll see how we define an actual Stack class using this template, but for now, just think of the T as you would a function's formal parameter. You use it in the definition with the understanding that the actual value (a type argument like int or Card) will be provided when the user invokes or instantiates the template. The programmer who uses this template can provide any class in place of T or any primitive type like int or double. For the definition of the template, however, we just use the formal parameter, T in our example.

We can have any number of type parameters if it makes sense to do so. template <class T, class S>

8A.4.2.2 Implementing (Defining) Class Template Methods

While implementing class template member functions, the definitions are prefixed by the phrase template <class T>, where the T is the same formal parameter as was used in the class template prototype.

Here is the complete implementation of class template Stack. In a few moments, we will invoke the template by instantiating some actual classes.

//template class Stack<T> member functions
template <class T>
Stack<T>::Stack(int s)
{
  size = (s > 0 && s < MAX_STACK) ? s : MAX_STACK;
  top = -1;  // initialize stack
  stackPtr = new T[size];
}

// push an element onto the Stack
template <class T>
bool Stack<T>::push(const T& item)
{
  if (!isFull())
  {
    stackPtr[++top] = item;
    return true;
  }
  return false;
}

// pop an element off the Stack
template <class T>
bool Stack<T>::pop(T &popValue)
{
  if (!isEmpty())
  {
    popValue = stackPtr[top--];
    return true;
  }
  return false;
}

8A.4.2.3 Header File Issues

Before we demonstrate how we instantiate some Queue classes, I'd like to make a comment about project file organization. Defining template member functions is somewhat different than defining regular class member functions.

Important

The declarations and definitions of the class template member functions should all be in the same .h header file.

Consider the following ill-advised attempt at placing template member function implementations in a .cpp file (which is not correct).

//file b.h --------------------

template <class T>
class b
{
public:
  b();
  ~b();
};

//file b.cpp --------------------

#include "b.h"
template <class T>
b<T>::b()
{
}

template <class T>
b<T>::~b()
{
}

//file main.cpp --------------------

#include "b.h"
void main()
{
  b<int> bi;
  b<float> bf;
}

When compiling b.cpp, the compiler has both the declarations and the definitions available. At this point the compiler does not need to generate any definitions for template classes, since there are no instantiations. But, when the compiler compiles main.cpp, there are two instantiations: template class b<int> and b<float>. At this point the compiler has the declarations but no definitions! This is where it becomes important to remember that the compiler needs to recreate (in a way: duplicate) the template source for each instance or invocation of the template. If there is no implementation visible (and the contents of the .cpp files normally are not) then the compiler can't do it.

Typically, the template prototypes are placed at the top of the template file, and the implementation or definitions are placed below, with a #pragma once directive placed after the prototype and before the member function definitions.

8A.4.2.4 Instantiating a Class Template

We've already seen that using a class template is easy. Create the required classes by plugging in the actual type for the type parameter(s). This process is commonly known as "Instantiating the class." Here is a sample client main() that uses the Stack class template.

#include <iostream>
using namespace std;
void main()
{
  typedef Stack<float> FloatStack;
  typedef Stack<int> IntStack;

  FloatStack floatStack(5);
  IntStack intStack;

  int i;
  float f;

  cout << "Pushing elements onto floatStack" << endl;
  f = 1.1;
  while (floatStack.push(f))
  {
    cout << f << ' ';
    f += 1.1;
  }
  cout << endl << "Stack Full." << endl;

  cout << endl << "Popping elements from floatStack" << endl;
  while (floatStack.pop(f))
    cout << f << ' ';
  cout << endl << "Stack Empty" << endl << endl;

  cout << "Pushing elements onto intStack" << endl;
  i = 1.1;
  while (intStack.push(i))
  {
    cout << i << ' ';
    i += 1;
  }
  cout << endl << "Stack Full" << endl;

  cout << endl << "Popping elements from intStack" << endl;
  while (intStack.pop(i))
    cout << i << ' ';
  cout << endl << "Stack Empty" << endl;
}

Program Output

Pushing elements onto floatStack
1.1 2.2 3.3 4.4 5.5
Stack Full.

Popping elements from floatStack
5.5 4.4 3.3 2.2 1.1
Stack Empty

Pushing elements onto intStack
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5
7 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Stack Full

Popping elements from intStack
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 7
4 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48
47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Stack Empty
Press any key to continue . . .

8A.4.3 Using Typedef with Template Instantiation

A good programming practice -- and one that we demonstrated above -- is to use typedef while instantiating template classes. Then throughout the program, one can use the typedef name. There are two advantages:

typedef's are very useful when "templates of templates" come into usage. For example, when instantiating an STL vector of int's, you could use:
```
typedef vector<int, allocator<int> > INTVECTOR;
```
Then, throughout your code, you could easily create vectors of ints like this with the shortened notation:
```
INTVECTOR intVec1;
```
If the template definition needs to be modified in the future, simply change the typedef definition. For example, the definition of template class vector, above, required a second parameter. But if we decide to change it so that it only takes one parameter like so
```
typedef vector<int> INTVECTOR;
```
then all the previous instantiations are still correct:
```
INTVECTOR intVec1;
```

Imagine how many changes would be required if there was no typedef.

8A.4.4 Using Multiple Class Parameters

We can have more than one class parameter. Let's create a template that allows us to have ordered pairs of objects of different types. For instance, we might have ordered pairs of ints, (3, 5), (-4, 12), or ordered pairs of a string and a double ("mom". 0.32), ("dad", -99.32). The idea is that we might want different class types for the first and second component of what we will call the OrderedPair class template.

Here is a prototype of such a class. Study it for a moment and notice that we are allowing virtually any class to be used in each of the positions:

template <class S, class T>
class OrderedPair
{
  private:
  S first;
  T second;
  public:
  OrderedPair(const S& first = S(), const T& second = T()  );
  bool setFirst(const S&);
  bool setSecond(const T&);
  bool setBoth(const S&, const T&);
  S getFirst()const { return first; }
  T getSecond()const { return second; }
  void show(ostream &out) const;
};

The prototype shows a constructor and mutators that take objects of the two classes S and T in various places. There are mutators that return S and T objects, as well. We have not yet shown the implementation of these methods, but before we do, let's see how we might instantiate two different classes using this template:

void main()
{
  typedef OrderedPair<int, int> IntPair;
  typedef OrderedPair<string, double> MixedPair;

  IntPair intPr(3, -59), intPrArray[20];
  MixedPair mixedPr("teach", 21), mixedPrArray[10];

  // ... the rest of the program
}

As you can see, we created two different classes, one that consists of pairs of ints and another that consists of pairs, the first of which is a string and the second of which is a double.

Here is the implementation of these methods along with a trial run. There are a few things that we will discuss in a moment, but the main thing to notice is that we use the two class parameters S and T as we would any formal parameters, placing them in position wherever we would use an ordinary class name (besides, of course, the special template notation that precedes the class name and function signatures).

template <class S, class T>
ostream& operator<<(ostream& output, const OrderedPair<S,T>& op)
{
  op.show(output);
  return output;
}

void main()
{
  typedef OrderedPair<int, int> IntPair;
  typedef OrderedPair<string, double> MixedPair;

  IntPair intPr(3, -59), intPrArray[20];
  MixedPair mixedPr("teach", 21.96), mixedPrArray[10];

  cout << "Individual pairs: " << intPr << mixedPr << endl << endl;

  // build the int pair array and show
  for (int k = 0; k < 20; k++)
    intPrArray[k].setBoth(k, k);
  cout << "Int Pair Array: " << endl;
  for (int k = 0; k < 20; k++)
    cout << intPrArray[k];
  cout << endl;

  // build the mixed pair array and show
  for (int k = 0; k < 10; k++)
  {
    ostringstream cnvrt;
    cnvrt << k;
    mixedPrArray[k].setBoth("CIS " + cnvrt.str(), k/10.);
  }
  cout << "Mixed Pair Array: " << endl;
  for (int k = 0; k < 10; k++)
    cout << mixedPrArray[k];
  cout << endl;
}


//template class OrderedPair<S,T> member functions

template <class S, class T>
OrderedPair<S,T>::OrderedPair(const S &first, const T &second)
{
  setBoth(first, second);
}

template <class S, class T>
bool OrderedPair<S,T>::setFirst(const S& first)
{
  this->first = first;
  return true;
}

template <class S, class T>
bool OrderedPair<S,T>::setSecond(const T& second)
{
if (second > 0)
{
  this->second = second;
  return true;
}
  this->second = 0;
  return false;
}

template <class S, class T>
bool OrderedPair<S,T>::setBoth(const S& first, const T& second)
{
  return ( setFirst(first) && setSecond(second) );
}

template <class S, class T>
void OrderedPair<S,T>::show(ostream &out) const
{
  out << "(" << first << ", " << second << ") ";
}


/* ------------------- Run -----------------------

Individual pairs: (3, 0) (teach, 21.96)

Int Pair Array:
(0, 0) (1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (6, 6) (7, 7) (8, 8) (9, 9) (10, 10) (
11, 11) (12, 12) (13, 13) (14, 14) (15, 15) (16, 16) (17, 17) (18, 18) (19, 19)

Mixed Pair Array:
(CIS 0, 0) (CIS 1, 0.1) (CIS 2, 0.2) (CIS 3, 0.3) (CIS 4, 0.4) (CIS 5, 0.5) (CIS
6, 0.6) (CIS 7, 0.7) (CIS 8, 0.8) (CIS 9, 0.9)
Press any key to continue . . .
------------------------------------------------- */

I overloaded the insertion operator to allow for a clean main(); this is an example of a template function which we will discuss in an upcoming section.

8A.4.5 Template "Concepts"

There is one curious aspect of the OrderedPair template example above. Note that in the mutator for the second coordinate, I had a test:

if (second > 0)

The compiler doesn't care if we do things like this when we are designing and compiling the template, because nothing is being instantiated yet - no real code is created. However, when we commit to some actual classes for S and T, then we will have actual code generated and this if statement might not make sense! What if the second class parameter, T, for which second is an object, does not have a operator> available to it that takes an int as the right operand, as in "second > 0"? If we attempted this with a string in the second position, as in:

typedef OrderedPair<string, string> StringPair;
StringPair sp("hi", "mom");

we would get a compiler error. Why? The compiler can't make sense out of the condition "mom" > 0. And this non-sense is not discovered until the instantiation is attempted. When it is, the compiler complains.

There can be many implied requirements of the classes that the template uses. Another requirement of both classes S and T in our design above is the idea that the << operator is overloaded as is commonly done with an ostream reference (see the show() method). Taken together, all the requirements implied by the template definition are called the template "concepts". Any class that wishes to be used in an instantiation of a template must satisfy all the template concepts or the instantiation will fail.

Concepts are not formalized or easily seen. They are merely requirements implied by the template design. After designing a template, scan it for unintended concepts and decide if you need to remove any of them. If you get unexpected compiler errors when you instantiate a template, always suspect that a concept is being enforced. If you make too many assumptions about your classes when you design a template, you will be creating a restrictive set of concepts that the users of the template will be unable to meet, thus limiting the template's use. On the other hand, if you really don't want the template to be used unless certain concepts are satisfied by the target classes, then these implicit requirements can be useful - they help the compiler tell the client programmer that he is attempting to instantiate the template with an unacceptable class.