C++ lets you declare and use a special kind of variable whose value is a type name or expression

The syntax for declaring such a variable is:

	template <typename T>
      

This declares T to be a variable whose value can be a type name or expression.

An alternate syntax is often used:

	template <class T>	
      

but the value of T can be type expressions like int or Point or int *

That is, the value of T does not have to a type that is the name of a class.

Write a simple function to sort an array of elements of type T:

Pseudo code (since type variable T is not declared)

void simplesort(T a[], int n)
{
  int maxpos;
  for(int i = n; i > 1; i--) {
    maxpos = 0;
    for(int j = 1; j < i; j++) {
      if ( a[maxpos] < a[j] ) {
	maxpos = j;
      }
    }
    T tmp = a[maxpos];
    a[maxpos] = a[i-1];
    a[i-1] = tmp;
  }
}

#ifndef SIMPLESORT_H
#define SIMPLESORT_H

template <class T>
void simplesort(T a[], int n)
{
  int maxpos;
  for(int i = n; i > 1; i--) {
    maxpos = 0;
    for(int j = 1; j < i; j++) {
      if ( a[maxpos] < a[j] ) {
	maxpos = j;
      }
    }
    T tmp = a[maxpos];
    a[maxpos] = a[i-1];
    a[i-1] = tmp;
  }
}
#endif

a. The code above is in simplesort.h (there is no simplesort.cpp!)

b. If we tried to compile this code by itself, it is incomplete. What
type will be subtituted for the parameter T?

c. We can use almost any type for T. ALMOST.

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include "simplesort.h"

using namespace std;

int main()
{
  int a[] = {5,2,3,10,7,1,4,8,9,6};
  int n = sizeof(a)/sizeof(int);

  simplesort(a, n); // compiler replaces T by int
  printArray(a, n);

  double b[] = {0.5,0.2,0.3,0.7,0.1,0.4,0.8,0.9,0.6};
  int nd = sizeof(b)/sizeof(double);

  simplesort(b, nd); // Compiler replaces T by double
  printArray(b, nd);

  string c[] = {"bb", "aa", "cb", "ca", "ba", "cd", "ab", "ac"};
  int ns = sizeof(c)/sizeof(string);

  simplesort(c, ns); // Compiler replaces T by string
  printArray(c, ns);

  return 0;
}

sizeof(a) is 40  (10 int's, each of size 4)
sizeof(int) is 4

sizeof(a)/sizeof(int) is 10  (the number of int's in a)

In Pair.h

template <class T>
class Pair
{
public:
 Pair();
 Pair(const T& xval, const T& yval);
 T getFirst();
 T getSecond();
 
private:
 T x;
 T y;
};

Also in Array.h after the class
template <class T>
T Pair<T>::getFirst()
{
  return x;
}

T Pair&T>::getSecond()
{
  return y;
}

The intArray class. intArray's grow automatically unlike ordinary arrays.

#ifndef INTARRAY_H
#define INTARRAY_H

#include <iostream>

using namespace std;


class intArray
{
  int *arr;
  int arr_size;
  int arr_capacity;
  void grow(int new_capacity);
public:
  intArray();
  intArray(int sz);
  intArray(const intArray& other); // 1. copy constructor

  int& at(int i);
  const int& at(int i) const;
  void add(int x);

  void operator=(const intArray& other); // 2. assignment

  int size() const;
  ~intArray();  // 3. destructor
};

#endif

int main()
{
  // declare an empty intArray (of integers)
  intArray a;
  
  // Insert numbers at the end
  for(int i = 0; i < 10000; i++) {
    a.add(i);
  }

  // Print the items in the Array a

  for(int i = 0; i < a.size(); i++) {
     cout << a.at(i) << endl;
  }

  return 0;
}
 

Our intArray class has int as the type of array elements.

If we wanted a intArray with a different type, we would have to change the int type to the new different type, but otherwise there would be no change to the code.

For example we might want a array of LineItem's. So the substitute for the int data type would be: LineItem.

If we created the new intArray for LineItem data, we would have a naming problem. We would have to create a name like

• LineItemArray

Instead of doing that, we can write the code once for a class named Array, but add a type "parameter".

When the Array is created, we provide a type name or expression for this parameter. For example:

 Array<int>  arr1;      // Array of integers
 Array<LineItem> arr2;   // Array of LineItem's

#ifndef ARRAY_H
#define ARRAY_H

#include <iostream>

using namespace std;

template <class T>
class Array
{
  T *arr;
  int arr_size;
  int arr_capacity;
  void grow(int new_capacity);
public:
  Array();
  Array(int sz);
  Array(const Array& other); // 1. copy constructor

  T& at(int i);
  const T& at(int i) const;
  void add(const T& x);

  void operator=(const Array& other); // 2. assignment

  int size() const;
  ~Array();  // 3. destructor
};
    

The member functions, constructors, destructors of a template class should be implemented in the .h file rather than a .cpp file.

The Array.h file!

#ifndef ARRAY_H
#define ARRAY_H

#include <iostream>

using namespace std;

template <class T>
class Array
{
  ...
};

// Add all the member function implementations here!
// after the class declaration.

template <class T>
Array<T>::Array()
{
  arr_size = 0;
  arr_capacity = 10;
  arr = new T[arr_capacity];
}
...

template <class T>
void Array<T>::add(const T& x)
{
  if ( arr_size == arr_capacity ) {
     grow(2*arr_capacity);
  }
  arr[arr_size] = x;
  arr_size++;
}

#endif

int main()
{
  // declare an empty Array (of integers)
  Array<int> a;
  
  // Insert numbers at the end
  for(int i = 0; i < 10000; i++) {
    a.add(i);
  }

  // Print the items in the Array a

  for(int i = 0; i < a.size(); i++) {
     cout << a.at(i) << endl;
  }

  return 0;
}
 

int main()
{
  // declare an empty Array (of Point's)
  Array<Point> a;
  int x, y;

  srand((unsigned int) time(0)); // Initialize random number generator

  // Insert random Point's at the end
  for(int i = 0; i < 10000; i++) {
    x = rand();
    y = rand();
    a.add( Point(x,y) );
  }

  // Print the Points in the Array a
  // Assumes operator<< has been overloaded for Poitn

  for(int i = 0; i < a.size(); i++) {
     cout << a.at(i) << endl;
  }

  return 0;
}
 

• A template function should be declared and implemented in a header file, not in a .cpp file.

• A template class should be declared and implemented in a header file, not in a .cpp file. That is, member functions and constructors for a template class should be implemented after the class declaration, but in the header file!

• Outside the class declaration, the name of a template class includes the <T>; e.g., Array<T>

• A declaration of a template function should be preceded by the declaration of the template parameter name; e.g.,

  	  template <class T>
  	

• A declaration of a template class should be preceded by the declaration of the template parameter name; e.g.,

  	  template <class T>
  	

• A template function implementation should be preceded by the declaration of the template parameter name; e.g:

  	  template <class T>
  	

  Note this also applies to implementations of member functions of template classes as well as implementations of non-member template functions.

  So the implementation of a member function outside the class declaration should use the class scope operator :: with this class name; e.g., the implementation of add in Array<T> should begin:

            template <class T>
  	  void Array<T>::add(const T& x)
            {
               ...
            }