Introduction to Templates

Introduction

One thing you should have noticed about linked-lists and queues and stacks: A stack of ints is the same as a stack of strings, a list of doubles is the same as a list of objects of class Point, a queue of chars is the same as a queue of bools, etc. However, with what we know so far, you need to create an entirely new list class whenever you want lists containing some new type of object. This is a pain in the neck! This is also prone to error, since you have a million different copies of what is essentially the same thing running around. One of the most basic rules not just of programming but even of using computers is to never keep multiple copies of the same data!

We're going to look at using the mechanism of templates to avoid this problem. A single templated class list can be used to create lists of any kind of object. You've been users of templates for several weeks now - with the Stack, Queue and List classes we've given you. We gave you just one class Stack, and you were able to use it for stacks of ints (remember, Stack<int>), or stacks of strings (remember, Stack<string>), or stacks of anything else you wanted. We're going to look under the hood at how that works!

The important thing here is to give you the understanding of templates you need in order to be an intelligent user of templated classes and functions. We're not so much interested right now in you being sophisticated implementers of templated classes and functions.

Simple list classes for ints, chars, etc

Consider a simple list class providing initialization, cleanup, add2front, and print capabilities. This is certainly a step back from our list class with iterators, etc., but we're keeping it simple to illustrate a point. Below are implementations of this simple class for ints, chars and doubles.

class List {
private:
  class Node {
  public:
    int data;
    Node *next;
    Node(int val, Node* p) {
      data = val;
      next = p;
    }
  }; //end class Node

  Node *head;

public:
  List() {
    head = 0;
  }

  ~List() {
    for(Node *p = head, *q = head; p != 0; q = p) {
      p=p->next;
      delete q;
    }
  }

  void add2front(int val) {
    head = new Node(val,head);
  }

  void print() {
    for(Node *p = head; p != 0; p = p->next)
      cout << p->data << endl;
  }
}; //end class List

class List {
private:
  class Node {
  public:
    char data;
    Node *next;
    Node(char val, Node* p) {
      data = val;
      next = p;
    }
  }; //end class Node

  Node *head;

public:
  List() {
    head = 0;
  }

  ~List() {
    for(Node *p = head, *q = head; p != 0; q = p) {
      p=p->next;
      delete q;
    }
  }

  void add2front(char val) {
    head = new Node(val,head);
  }

  void print() {
    for(Node *p = head; p != 0; p = p->next)
      cout << p->data << endl;
  }
}; //end class List

class List {
private:
  class Node {
  public:
    double data;
    Node *next;
    Node(double val, Node* p) {
      data = val;
      next = p;
    }
  }; //end class Node

  Node *head;

public:
  List() {
    head = 0;
  }

  ~List() {
    for(Node *p = head, *q = head; p != 0; q = p) {
      p=p->next;
      delete q;
    }
  }

  void add2front(double val) {
    head = new Node(val,head);
  }

  void print() {
    for(Node *p = head; p != 0; p = p->next)
      cout << p->data << endl;
  }
}; //end class List

What's different about the int version, the char version and the double version? Almost nothing! The only thing that changes is that wherever you see char, for instance, you put double, or int. In fact, you remember from SI204 about a keyword that could help us with this, typedef to be exact! Therefore, you argue that we could say something like this:

class List {
private:
  class Node {
  public:
    typedef /* FILL ME IN */ DataType;
    DataType data;
    Node *next;
    Node(DataType val, Node* p) {
      data = val;
      next = p;
    }
  }; //end class Node

  Node *head;

public:
  List() {
    head = 0;
  }

  ~List() {
    for(Node *p = head, *q = head; p != 0; q = p) {
      p = p->next;
      delete q;
    }
  }

  void add2front(DataType val) {
    head = new Node(val,head);
  }

  void print() {
    for(Node *p = head; p != 0; p = p->next)
      cout << p->data << endl;
  }
}; //end class List

You'd be right in your assessment and we could go about our day knowing that you solved the mystery! A List of doubles? "Piece of cake", you proclaim. However, there's one big catch with your solution: you can only have one type of List if you use typedef in the class since every class you instantiate in the program must use the actual data type associated with DataType.

Luckily for us C++ has a mechanism we can use to bypass this limitation. It's called templates. A template allows you to say "DataType stands for a type, and the user of the class I'm defining will specify which type he means by putting it in < >'s after the name of my class." The compiler will automatically take whatever the user of your class puts in < >'s and replace every occurence of DataType with it. Now, to tell the compiler that DataType stands for a type you simply write template<class DataType>. This defines DataType as a template parameter, i.e. as a variable that stands for a type, rather than a variable that stands for an object. This declaration of the "type variable" DataType has a scope, just like regular variables, if you place the declaration right before a class definition, it extends to the end of the class. Here's an example for defining a simple templated class for storing pairs of objects. It offers a constructor and a print function.

template<class DataType>
class Pair {
public:
  DataType first, second;

  Pair(DataType a, DataType b) {
    first = a;
    second = b;
  }

  void printline() {
    cout << '(' << first << ',' << second << ')' << endl;
  }
}; //end class Pair

Now, the important thing to note is that Pair on its own is not a type! You also need to specify what DataType is to have a complete type name. Thus, Pair<int> is a type, Pair<double> is a type, even Pair< Pair<char> > is a type, but Pair isn't. If you try to declare a variable of typePair in a program, you'll get the error message "Pair undeclared", because you haven't completely specified the type. Here's a sample program that uses the templated class Pair:

int main() {
  Pair<int> A(3,5);
  Pair<double> B(0.5,-2.25);
  Pair<char> C('X','@');

  A.printline();
  B.printline();
  C.printline();

  return 0;
}

$ g++ -o go ex5.cpp
$ go
(3,5)
(0.5,-2.25)
(X,@)
$

Notice, there's no conflict in having pairs of different types of objects living in the same program - Pair<int> is a totally different type from Pair<double> which is a totally different type Pair<char>

Requirements implied by a template definition

The main issue with templates is that your template definition will place requirements on the type you use for the template parameter. Suppose that we have an exisiting class Card and we want to use the Pair class from the previous section. We might write something like this:

#include <iostream>
using namespace std;

template<class DataType>
class Pair {
public:
  DataType first, second;

  Pair(DataType a, DataType b) {
    first = a;
    second = b;
  }

  void printline() {
    cout << '(' << first << ',' << second << ')' << endl;
  }
}; //end class Pair

class Card {
public:
  int face;
  char suit;

  Card() {
    face = 2;
    suit = 'S';
  }

  Card(int f, char s) {
    face = f;
    suit = s;
  }
}; //end class Card

#include <iostream>

int main() {
  Card c1(9,'C'), c2(3,'D');
  Pair<Card> P(c1,c2);
  P.printline();

  return 0;
}

When you try to compile main.cpp, you'll get a boatload of errors, starting with the following:

$ g++ -o main main.cpp
main.cpp: In member function 'void Pair<DataType>::printline() [with DataType = Card]':
main.cpp:44:   instantiated from here
main.cpp:18: error: no match for 'operator<<'

What the error is telling you is that the compiler doesn't know how to print out a Card using the << operator. Why does it feel it needs to know that? Well, when you call P.printline() it attempts to execute the line:

cout << '(' << first << ',' << second << ')' << endl;

Since first and second have type Card, the compiler needs to know how to "cout <<" an object of type Card, and it complains because it doesn't. So you see, the definition of printline placed the constraint that whatever type you use in place of DataType will have to overload the operator<< for output!

Some constraints are a little more subtle! For example, you may have noticed that there is a default constructor in the definition of the class Card. Was that really necessary? Yes! If you look at the way the constructor for class Pair is defined, you see that the values of first and second are set after they are created via assignment, as opposed to set while they are created via intitialization (i.e. via a copy constructor). That means that first and second are created with the default constructor for type DataType and then set afterwards by assignment. Thus, we need to have a default constructor! We could redefine Pair using initialization in place of assignment this way:

#include <iostream>
using namespace std;

template<class DataType>
class Pair {
public:
  DataType first, second;
  Pair(DataType a, DataType b) : first(a), second(b)   { }
  void printline() {
    cout << '(' << first << ',' << second << ')' << endl;
  }
}; //end class pair

Now first and second are created with a copy constructor rather than a default constructor. In the case of our class Card, we don't need to explicitly define a copy constructor, because the compiler will create one for us automatically, and the one it creates (member-wise copy) is good enough for us.

Templated functions

We can also use templates to create functions that operate on many different types of arguments. For example, you may notice that maximum(a,b) would be a very usefull operation to have. You might want to find the maximum of two ints, or of two strings, or of two doubles, etc.

int maximum(int a, int b) {
  if (a < b)
    return b;
  else
    return a;
}

string maximum(string a, string b) {
  if (a < b)
    return b;
  else
    return a;
}

double maximum(double a, double b) {
  if (a < b)
    return b;
  else
    return a;
}

At some point, you say enough! These are all just the same, except for the type. Can't I use a template mechanism here? The answer is yes!

template <class DataType>
DataType maximum(DataType a, DataType b) {
  if (a < b)
    return b;
  else
    return a;
}

This one definition of maximum now works for ints, strings, doubles and more. For example, this snippet of code works perfectly well with just our templated definition of maximum:

int a = 5, b = -2;
string s = "hello", t = "heart";
double x = 0.5, y = 0.502;

cout << maximum(a,b) << endl;
cout << maximum(s,t) << endl;
cout << maximum(x,y) << endl;

The actual type that's used in place of the parameter DataType is determined by the compiler by the arguments given in the function call. In the first call to maximum, a and b have type int, and therefore int is used in place of DataType. In the second call to maximum, s and t have typestring, and therefore string is used in place of DataType. And so on.

Now, the definition of a templated function places constraints on the types you use for the template parameter just like the definition of a templated class placed constraints on the types you use for the template parameter. What constraints does our definition of maximum place on the types we use for DataType? Well, since the function uses pass-by-value, the types we use must have copy constructors. Also, since we compare two objects with a <, operator< must be defined for the types we pass maximum. Thus, to use maximum with the Card type we defined in the previous section, we'd need to define bool operator<(Card c1, Card c2).