## Chapter 22 - Templates

## Chapter Goals

- 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

## Chapter 22 - Templates

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

## 22.1 Template Functions

- 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 << "]";
  >     }

## 22.1 Template Functions

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

## 22.1 Template Functions (cont.)

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

## 22.1 Template Functions (cont.)

>     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 << "]";
>     }

## 22.1 Template Functions (cont.)

Syntax 22.1: Template Function Definition
    template<typename type_var1, ..., typename type_varn>
    return_type function_name(parameters)
    {
       statements
    }
Purpose: | Define a function that can be reused for different types of arguments

## 22.1 Template Functions (cont.)

Syntax 22.1: Template Function Definition (cont.)
Example: |
    template<typename T>
    void print(ostream& out, T data[], int count)
    {
       out << "[";
       for (int i = 0; i < count; i++)
       {
          out << data[i];
          if (i + 1 < count)
             out << ",";
       }
       out << "]";
    }

## 22.1 Template Functions (cont.)

- `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

## Common Error 22.1

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;
  >     }

## Common Error 22.1 (cont.)

- 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

## Common Error 22.1 (cont.)

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`

## 22.2 Compile-Time Polymorphism

- 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

## 22.3 Template Classes

- 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);
  >     }

## 22.3 Template Classes (cont.)

- 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;
>     };

## 22.3 Template Classes (cont.)

>     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;
>     }

## 22.3 Template Classes (cont.)

- `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>`

## 22.3 Template Classes (cont.)

- 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;
  >     };

## 22.3 Template Classes (cont.)

- 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;
>     }

## 22.3 Template Classes (cont.)

>     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;
>     }

## 22.3 Template Classes (cont.)

- `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

## 22.3 Template Classes (cont.)

Syntax 22.2 Template Class Definition
    template<typename type_var1, ..., typename type_varn>
    class ClassName
    {
       features
    };
Purpose: | Define a class template with a type parameter.

## 22.3 Template Classes (cont.)

Syntax 22.2 Template Class Definition (cont.)
Example: |
    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;
    };

## 22.3 Template Classes (cont.)

Syntax 22.3: Template Member Function Definition
    template<typename type_variable>
    {
       statements
    }
Example: |
    template<typename T>
    inline T Pair<T>::get_first() const
    {
       return first;
    }
Purpose: | Supply the implementation of a member function for a class template.

## 22.4 Template Linked List

- 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;
  >     };

## 22.4 Template Linked List (cont.)

- 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;
  >     };

## 22.4 Template Linked List (cont.)

- 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;
  >     }

## Quality Tip 22.2

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>`

## Quality Tip 22.2 (cont.)

Syntax `typedef` Statement
    typedef declaration;
Example: |
    typedef pair<int, string> ElementType;
Purpose: | Create an alias for a complicated type name.

## 22.5 Nontype Template Arguments

- 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

## 22.5 Nontype Template Arguments (cont.)

- 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

## 22.5 Nontype Template Arguments (cont.)

- 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

## 22.5 Nontype Template Arguments (cont.)

- 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

## 22.6 Setting Behavior Using Template Arguments

- 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;
  >     }

## 22.6 Setting Behavior Using Template Arguments

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

## 22.6 Setting Behavior Using Template Arguments (cont.)

- E.g., use function objects to compare `Employee`s 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();
  >     }

## 22.6 Setting Behavior Using Template Arguments (cont.)

>     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();
>     }

## 22.6 Setting Behavior Using Template Arguments (cont.)

- `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());`

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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;
  >     };

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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);
>     }

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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`

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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;
>     }

## 22.6 Setting Behavior Using Template Arguments (cont.)

- 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`

## 22.7 Case Study: Matrices, Cont.

- 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

## 22.7 Case Study: Matrices (`matrix5.h`)

## 22.7 Case Study: Matrices (`matrix5.cpp`)

## 22.7 Case Study: Matrices (`matrixtest5.cpp`)

## Chapter Summary

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