Templates

Introduction

Generic programming involves writing code in a way that is independent of any particular type. Examples of generic programming are library containers and iterator. Templates are the foundation of generic programming.
A template is a blueprint or formula for creating a class or a function.
C++ templates constitute a compile-time, Turing-complete sublanguage of C++.

Template Definitions

Defining a Function Template

A function template is a type-independent function that is used as a formula for generating a type-specific version of the function.

Example 1
Function to compare two values and indicate whether the first is less than, equal to, or greater than the second.
First attempt might be to define several overloaded functions:

// returns 0 if the values are equal, -1 if v1 is smaller, 1 if v2 is smaller
     int compare(const string &v1, const string &v2)
     {
         if (v1 < v2) return -1;
         if (v2 < v1) return 1;
         return 0;
     }
     int compare(const double &v1, const double &v2)
     {
         if (v1 < v2) return -1;
         if (v2 < v1) return 1;
         return 0;
     }

Having to repeat the body of the function for each type that we compare is tedious and error-prone. More importantly, we need to know in advance all the types that we might ever want to compare.

Example 2

// implement strcmp-like generic compare function
     // returns 0 if the values are equal, 1 if v1 is larger, -1 if v1 is smaller
     // one type parameter, T.
     // Which actual type T represents is determined by the compiler based on how the function is used. 
     template <typename T>
     int compare(const T &v1, const T &v2)
     {
         if (v1 < v2) return -1;
         if (v2 < v1) return 1;
         return 0;
     }

Template parameters represent types or values we can use in the definition of a class or function.

Example 3

int main ()
     {
         // T is int;
         // compiler instantiates int compare(const int&, const int&)
         cout << compare(1, 0) << endl;
         // T is string;
         // compiler instantiates int compare(const string&, const string&)
         string s1 = "hi", s2 = "world";
         cout << compare(s1, s2) << endl;
         return 0;
     }

Defining a Function Template

Rather than defining a new function for each type, we can define a single function template. A function template is a type-independent function that is used as a formula for generating a type-specific version of the function.
A template definition starts with the keyword template followed by a template parameter list, which is a comma-separated list of one or more template parameters bracketed by the less-than (<) and greater-than (>) tokens.
When we use a function template, the compiler infers what template argument(s) to bind to the template parameter(s). Once the compiler determines the actual template argument(s), it instantiates an instance of the function template for us.

Inline Function Templates

A function template can be declared inline function |inline in the same way as a nontemplate function.
Example 4

// ok: inline specifier follows template parameter list
     template <typename T> inline T min(const T&, const T&);
     // error: incorrect placement of inline specifier
     inline template <typename T> T min(const T&, const T&);}}

Defining a Class Template

Example
Implementation of a Queue class. Our Queue template takes a single template type parameter named Type.

template <class Type> class Queue 
{
     public:
         Queue ();                // default constructor
         Type &front ();          // return element from head of Queue
         const Type &front () const;
         void push (const Type &); // add element to back of Queue
         void pop();              // remove element from head of Queue
         bool empty() const;      // true if no elements in the Queue
     private:
         // ...
 };

Template Type Parameters

Type parameters consist of the keyword class or the keyword typename followed by an identifier. In a template parameter list, these keywords have the same meaning: They indicate that the name that follows represents a type.
The keyword typename was added to C++ as part of Standard C++, so older programs are more likely to use the keyword class exclusively.

Nontype Template Parameters

A template parameter need not be a type.
Nontype parameters are replaced by values when the function is called. The type of that value is specified in the template parameter list.

Example
The following function template declares array_init as a function template with one type and one nontype template parameter. The function itself takes a single parameter, which is a reference to an array.

// initialize elements of an array to zero
template <class T, size_t N> void array_init(T (&parm)[N])
{
         for (size_t i = 0; i != N; ++i) 
    {
             parm[i] = 0;
    }
}

Writing Generic Programs

The operations performed inside a function template constrains the types that can be used to instantiate the function. It is up to the programmer to guarantee that the types used as the function arguments actually support any operations that are used, and that those operations behave correctly in the context in which the template uses them.

Instantiation

The compiler uses the template to generate type-specific versions of the specified class or function. The process of generating a type-specific instance of a template is known as instantiation.
A template is instantiated when we use it. A class template is instantiated when we refer to the an actual template class type, and a function template is instantiated when we call it or use it to initialize or assign to a pointer to function.

Example

Queue<int> qi; // the compiler automatically creates a class named Queue<int>
Queue<string> qs; // each occurrence of Type would be replaced by string.
Queue qs; // error: which template instantiation?

Template Argument Deduction

To determine which functions to instantiate, the compiler looks at each argument. If the corresponding parameter was declared with a type that is a type parameter, then the compiler infers the type of the parameter from the type of the argument. The process of determining the types and values of the template arguments from the type of the function arguments is called template argument deduction.

Function-Template Explicit Arguments

In some situations, it is not possible to deduce the types of the template arguments. This problem arises most often when a function return type must be a type that differs from any used in the parameter list. In such situations, it is necessary to override the template argument deduction mechanism and explicitly specify the types or values to be used for the template parameters.

Template Compilation Models

When the compiler sees a template definition, it does not generate code immediately. The compiler produces type-specific instances of the template only when it sees a use of the template, such as when a function template is called or an object of a class template is defined.

Class Template Members

Queue Implementation Strategy

Two classes:

  1. Class QueueItem will represent a node in Queue's linked list. This class has two data members: item and next
  2. Class Queue will provide the interface functions

The QueueItem Class

Class QueueItem is a private class—it has no public interface. We intend this class to be used to implement Queue and have not built it for general use. Hence, it has no public members. We'll need to make class Queue a [[friends|friend]]] of QueueItem so that its members can access the members of QueueItem.

 template <class Type> class QueueItem 
{
     // private class: no public section
         QueueItem(const Type &t): item(t), next(0) { }
         Type item;           // value stored in this element
         QueueItem *next;     // pointer to next element in the Queue
};

The Queue Class

template <class Type> class Queue 
{
     public:
         // empty Queue
         Queue(): head(0), tail(0) { }
         // copy control to manage pointers to QueueItems in the Queue
         Queue(const Queue &Q): head(0), tail(0)
                                       { copy_elems(Q); }
         Queue& operator=(const Queue&);
         ~Queue() { destroy(); }
              // return element from head of Queue
         // unchecked operation: front on an empty Queue is undefined
         Type& front()             { return head->item; }
         const Type &front() const { return head->item; }
         void push(const Type &);       // add element to back of Queue
         void pop ();                    // remove element from head of Queue
         bool empty () const 
    {    
        // true if no elements in the Queue
                 return head == 0;
         }
     private:
         QueueItem<Type> *head;         // pointer to first element in Queue
         QueueItem<Type> *tail;         // pointer to last element in Queue
         // utility functions used by copy constructor, assignment, and destructor
         void destroy();                // delete all the elements
         void copy_elems(const Queue&); // copy elements from parameter
     };
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.