Lecture 12: Templates
----------------------

Consider the function swap:

void swap(int& a, int& b) {
  int temp = a;
  a = b;
  b = temp;
}

As we've seen in previous lectures this implementation works for ints.
Or for floats, if we could replace "int" with "float" everywhere.
In fact, there are a lot of types, primitive (non-class) types at least,
for which this is the perfect implementation of swap.
We could even imagine wanting to use it for objects of an
arbitary user-defined class as well.
So, do we have to repeat that definition over and over ?

No.

Function templates
------------------

A function template for swapping two items of some type is

template <class T>
void swap(T& a, T& b) {
  T temp = a;
  a = b;
  b = temp;
}

This does not, by itself, translate into code for your machine to
carry out.  Rather, when you use the swap function on a type such as:

int a,b;
swap(a,b);

the compiler uses the template, with "int" replacing "T" everywhere,
to produce a function, and then generates the machine code for that
function.

If you swap 8 pairs of ints in 8 different places, then the template
is applied once to produce "void swap(int&,int&)", and that function
is invoked 8 times.

Let's consider another common function template:

template <class T>
T max(T a, T b) {
  return (a > b) ? a : b; 
}

This template function works.  It generates a function to
return the larger of two items of any type, provided that the ">"
operator is defined for that type, and that ">" does the right thing
for that type.

More important than function templates are class templates.  For a
simple example, consider a point class:

Class templates
---------------

class point {
public:
  float x;
  float y;
};

Do we always want these to be floats ?  Maybe there will be a few
remarkable points specified with int coordinates (such as the corners of
our drawing space).
We can get that by defining point as a class template:

template <class T>
class point {
  T x;
  T y;
};

If we want a few integer points, and many of the float kind, we might declare
these:

point<int> few[4];
point<float> many[1000];

General Syntax:
The arguments to the class template appear in <angle brackets> after
the template keyword like this:

template <class T1, class T2, class T3>
The use of the class keyword in this context indicates that the identifier
that follows represents a type parameter.

As with function templates, class templates and function members of
class templates are only turned into code for the classes and members
we actually use.

Another class template example is Array. We may want to use
Arrays of ints, doubles, Strings, studentrecords ...
Templates save us from having to define all these different
classes which essentially are very similar.

template <class T>
class Array {

private:
  T A[size];
  int size;
public:
  T& operator[](int index) {
    return A[index]; // could add out of range check too
  }
};

int main() {
  Array<int> ia;
  Array<float> fa;
  for(int i = 0; i < 20; i++) {
    ia[i] = i;
    fa[i] = i * 1.4;
  }

  for(int j = 0; j < 20; j++)
    cout << j << ": " << ia[j]
         << ", " << fa[j] << endl;
}

You can see that it looks like a normal class except for the line
template <class T>
which says that T is the substitution parameter, and that it represents
a type name. Also, you see T used everywhere in the class where you would
normally see a specific type.

As we have seen for class String in our previous lectures,
the overloaded operator[] returns a reference, so it
can be used on both sides of an equal sign (that is, as both an lvalue
and an rvalue).

In main(), you can see how easy it is to create Arrays that hold different
types of objects. When you say

Array<int> ia;
Array<float> fa;
the compiler expands the Array template (this is called instantiation) twice,
to create two new generated classes, which you can think of as
Array_int and Array_float.

These are classes just like the ones you would have produced if you had
performed the substitution by hand, except that the compiler creates them
for you as you define the objects ia and fa. In this way, duplicate class
definitions are avoided.

What if you want to write a non-inline member function definitions
for operator[] ? In this case, the compiler needs
to see the template declaration before the member function definition.
Here is the example above, modified to show the non-inline function
member definition:

template<class T>
class Array {
private:
  int size;
  T A[size];
public:
  T& operator[](int index);
};

template<class T>
T& Array<T>::operator[](int index) {
  return A[index];
}

int main() {
  Array<float> fa;
  fa[0] = 1.4;
}

Any reference to a template class name must be accompanied by its
template argument list, as in Array<T> in the above definition
of operator[].

Header files
------------

Templates pose a problem for linking because the actual code for the 
classes/functions we have defined templates for is not generated 
until an instantiation (use of these classes with a real type argument).
So if we include a .h file for the ListTemplate in the driver, the linker will
not know where the actual classes (e.g., List of ints) are defined.

There are two solutions:
 
1. We can keep the template class declaration in .h
and the class method implementations in .cc as before. 
We need to add instantiations for all types we'll use 
the templated class/function for at the end of the .cc file.
We use Makefiles with dependencies specified in the same
way as before (please see the Vector and Stack template
classes as examples).

2. An alternative is to include the .cc file in the .h file
at the end (you can try modifying the ListTemplate code sample 
to see how it works).
In this case we do not need to use a Makefile with dependencies
since everything will be included directly or indirectly in the driver.cc file 
(e.g., the driver.cc file includes the List.h which includes the List.cc ...).

However, I prefer/would recommend the first method (above).