• To be able to use and define template functions
• To learn how to use and define template classes
• To understand the relationship between template functions and classes and ordinary functions and classes
• To learn how to use typedef statements to create alias names for long type names
• To understand the interactions between template classes, inheritance, and static data fields
• To learn how policy can be established by the selection of template arguments

• Provides another level of abstraction
• A template class or function can work with many different types
• Handled at compile time (efficient)

• E.g., a function to print an array of int:

  void print(ostream& out, int data[], int count)
  {
     out << "[";
     for (int i = 0; i < count; i++)
     {
        if (i > 0)
           out << ",";
        out << data[i];
     }
     out << "]";
  }

• Your next project requires the same for an array of doubles:
  • Cut and paste?
  • Search and replace?
• Template function is a better solution

• Function parameterized by type
• Abstract away the differences (argument types)
• Use the template prefix, template followed by a list of type parameters:

template<typename T>
void print(ostream& out, T data[], int count)
{
   out << "[";
   for (int i = 0; i < count; i++)
   {
      if (i > 0)
         out << ",";
      out << data[i];
   }
   out << "]";
}

• T is arbitrary; any legal C identifier
• typename (or class) indicates that the value of T will be a type
• T could represent any type
• Its type is inferred from the arguments of the call:

  int a[] = {2, 4, 5};
  print(cout, a, 3); // Will use int print
  double b[] = {3.14159, 2.7};
  print(cout, b, 2); // Will use double print
  string c[] = {"Fred", "Sally", "Alice"};
  print(cout, c, 3); // Will use string print

• Within the function body T can be used wherever that type would be appropriate

A type argument is characterized implicitly, by its use in the function.

• The typical max function:

  template<typename T>
  T max(const T& left, const T& right)
  {
     if (left < right)
        return right;
     return left;
  }

• The < operator must be defined for T
• This won't work:

  Employee mary("Mary Smith", 25000);
  Employee fred("Fred Jones", 37500);
  Employee big = max(mary, fred); // Error - invalid types

• Compiler must see the entire definition of a function template

Coercion doesn't happen. You can't mix types.

• Consider:

  double e = max( 2, 3.13 ); // Error - cannot infer type argument

• Type argument(s) may be supplied explicitly:

  double e = max<double>( 2, 3.13 ); // OK - integer will be converted to a double

• Templates instantiated in many different ways
• Does its work at compile time
  • Compiler creates template functions from the function template, as needed
  • Few run-time costs
  • A function template prototype is meaningless
• Templates are commonly stored in included files
• Not compiled separately (sect. 22.6)
• Compiler looks for non-templates first

• The most common examples are container classes
• Consider a function that finds the max and min values of a vector
• make a Pair class to return both values

  Pair minmax(vector<int> v)
  {
     int min = v[0];
     int max = v[0];
     for (int i = 1; i < v.size(); i++)
     {
        if (v[i] < min) min = v[i];
        if (v[i] > max) max = v[i];
     }
     return Pair(min, max);
  }

• To use:

  Pair p = minmax(data);
  cout << p.get_first() << " " << p.get_second() << "\n";

Example: non-template class:

class Pair
{
   public:
      Pair(int a, int b);
      int get_first() const;
      int get_second() const;
   private:
      int first;
      int second;
};

inline Pair::Pair(int a, int b)
{
   first = a;
   second = b;
}

inline int Pair::get_first() const
{
   return first;
}

inline int Pair::get_second() const
{
   return second;
}

• Pair is not very flexible
• We'd like a generic pair
• One that can hold disparate types
• Type arguments can not be inferred
• They are explicitly named at declaration:

  Pair<int, int>
  Pair<string, int>

• Replace types with F and S

  template<typename F, typename S>
  class Pair
  {
  public:
     Pair(const F& a, const S& b);
     F get_first() const;
     S get_second() const;
  private:
     F first;
     S second;
  };

• Turn each member function into a template:

template<typename F, typename S>
inline Pair<F, S>::Pair(const F& a, const S& b)
{
   first = a;
   second = b;
}

template<typename F, typename S>
inline F Pair<F, S>::get_first() const
{
   return first;
}

template<typename F, typename S>
inline S Pair<F, S>::get_second() const
{
   return second;
}

• Pair is a template, not a class
• Pair<F,S> precedes each declaration
• Compare to the STL pair class
• These are templates, not functions
• Must be included in each compilation module

• Recall the linked list from chptr. 16
• List stored strings
• Used the Node and Iterator classes
• Let's make them into templates
• Node:

  template<typename T>
  class Node
  {
  public:
     Node(T s);
  private:
     T data;
     Node<T>* previous;
     Node<T>* next;
  };

• List:

  template<typename T>
  class List
  {
  public:
     List();
     void push_back(T s);
     void insert(Iterator<T> pos, T s);
     Iterator<T> erase(Iterator<T> pos);
     Iterator<T> begin();
     Iterator<T> end();
  private:
     Node<T>* first;
     Node<T>* last;
  };

• Turn each member function definition into a template:

  template<typename T>
  Iterator<T> List<T>::begin()
  {
     Iterator<T> iter;
     iter.position = first;
     iter.last = last;
     return iter;
  }

Use typedef to Form an Alias for a Long Name

• typedef long types:

  typedef pair<int, double> ElementType;
  typedef vector< pair<string, string> > StringMap;

• Space inside the > >
• Associates a new name with the given type
• Use as any other type:

  ElementType new_value; // new_value is type pair<int, string>

• May be other things (integer constants)
• Consider our matrix case study
  • 3x3, at first
  • Then managed heap memory to remove this restriction
  • Template arguments provide a third alternative

• Size could be specified by integer template arguments:

  template<typename T, int ROWS, int COLUMNS>
  class Matrix
  {
     . . .
  private:
     T data[ROWS][COLUMNS];
  };

• Note, the integer values must be known at compile time

• Supply the type and the size:

  Matrix<double, 3, 4> a; // A 3 x 4 matrix of double values
  Matrix<string, 2, 2> b;

• The bounds become part of the type

• Compatibility checked at compile time

  Matrix<int, 3, 4> a;
  Matrix<double, 3, 4> b;
  Matrix<int, 5, 7> c;
  Matrix<int, 3, 4> d;
  b = a; // Error, element types don't match.
  c = a; // Error, sizes dont match, so types differ.
  d = a; // OK. Element types and sizes match.

• The requirements for matrix multiplication are much more difficult to specify

• Specify behavior (set policy)
• Generalize the max function to support types that:
  • Don't define operator<
  • Have more than one way of ordering
• Make comparison a template argument:

  template<typename T, typename CMP>
  T max(const T& left, const T& right, CMP cmp)
  {
     if (cmp(left, right))
        return right;
     return left;
  }

• < has been replaced by a function call
• cmp may be either
  1. An actual function
  2. A function object (chptr. 17)

• E.g., use function objects to compare Employees by salary or name
• Develop these two classes:

  class CompareBySalary
  {
  public:
     bool operator()(const Employee& a,
        const Employee& b) const;
  };
  
  bool CompareBySalary::operator()(const Employee& a,
     const Employee& b) const
  {
     return a.get_salary() < b.get_salary();
  }

class CompareByName
{
public:
   bool operator()(const Employee& a,
      const Employee& b) const;
};

bool CompareByName::operator()(const Employee& a,
   const Employee& b) const
{
   return a.get_name() < b.get_name();
}

• CompareByName and CompareBySalary are types
• Represent two different orderings
• We can use the max function in either sense:

  Employee alice("Alice Smith", 45000);
  Employee fred("Fred Jones", 38500);
  
  Employee one = max(alice, fred, CompareBySalary());
  Employee two = max(alice, fred, CompareByName());

• Same idea applies to template class arguments
• Maintaining a collection in sorted order
  • Specify the rules for comparing two elements
  • Do not specify criteria in the container itself

• Use template arguments:

  template<typename T, typename CMP>
  class OrderedCollection
  {
  public:
     typedef Iterator<T> iterator;
     void add(T value);
     iterator begin();
     iterator end();
  private:
     List<T> data;
     CMP comparator;
  };

• The comparator is an attribute

template<typename T, typename CMP>
void OrderedCollection<T, CMP>::insert(T value)
{
   iterator ptr = begin();
   while (ptr != end())
   {
      if (comparator(value, *ptr))
      {
         // Found place to insert
         data.insert(ptr, value);
         return;
      }
      ++ptr;
   }
   // Insert at end
   data.insert(ptr, value);
}

• The collection is defined by the type it stores, and by the type of its comparator

  void f(OrderedCollection<Employee, CompareByName>& c)
  {
     . . .
  }
  
  OrderedCollection<Employee, CompareBySalary> a;
  a.add(. . .);
  OrderedCollection<Employee, CompareByName> b;
  b.add(. . .);
  f(a); // Errortypes don't match
  f(b); // OK - type is OK

• Identify a default policy
• Associated with a template parameter
• STL algorithms use the less<T>, in the <functional> header file

template<typename T>
class less
{
   bool operator()(const T& x, const T& y) const;
}

template<typename T>
bool less<T>::operator()(const T& x, const T& y) const
{
   return x < y;
}

• The less defines a function object
• Invokes operator<
• Specify trait as the default template argument

  template<typename T, typename CMP = less<T> >
  class OrderedCollection
  {
     . . .
  }

• To use the default:

  OrderedCollection<int> data; // Will use the less than operator

• Create a template version of the Matrix class
• Start with the class in chptr. 19
  • Avoids explaining interactions between templates and nested classes
  • No reason to make the exception classes into templates
• Parameterize the element type only
• Not the row and column bounds; simplifies overloading the arithmetic operators
• Zero is no longer an appropriate value for all types; remove the initializer loop in the c'tor
• Move member function definitions into the header file

1. A template allows a function or class to be parameterized by type
2. The template abstracts the actions to be performed
3. Template arguments are inferred from the values in a function invocation
4. Template functions can have the same name as nontemplate functions. The nontemplates are searched first for a match
5. Template classes allow the creation of containers that work with many different types of values
6. Template classes must be explicitly instantiated in order to declare new variables
7. Template arguments can be type names or they can be constants
8. A typedef statement can be used to form an alias for a type name
9. Template arguments can be used to set behavior, for example, setting the comparison algorithm for sorted containers