• Next chapter
• Previous chapter
• Table of contents

Chapter 18: Templates

We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Send your email to Frank Brokken.

Please state the document version you're referring to, as found in the title (in this document: 5.2.0a) and please state the paragraph you're referring to.

All mail received is seriously considered, and new (sub)releases of the Annotations will normally reflect your suggestions for improvements. Except for the incidental case I will not otherwise acknowledge the receipt of suggestions for improvements. Please don't misinterpret this for lack of appreciation.

The C++ language support a mechanism which allows programmers to define completely general functions or classes, based on hypothetical arguments or other entities. Code in which this mechanism has been used is found in, e.g., de chapter on abstract containers.

These general functions or classes are used to generate concrete code once their definitions are applied to real entities. Such a general definition of a function or a class is called a template, the concrete code that is generated based on a template is called an instantiation.

In this chapter we will examine template functions and template classes.

18.1: Template functions

    fun(int *array)l

    int sumVector(int *array, unsigned n)
    {
        int 
            sum(0);        
        for (int idx = 0; idx < n; ++idx)
            sum += array[idx];
        return (sum);
    }        

    double sumVector(double *array, unsigned n)
    {
        double 
            sum(0);        
        for (int idx = 0; idx < n; ++idx)
            sum += array[idx];
        return (sum);
    }        

In cases like these, template functions are used to create the truly general function. The template function can be considered a general recipe for constructing a function that can be used with the generic array. In the upcoming sections we'll discuss the construction of template functions. First, the construction of a template function is discussed. Then the instantiation is covered. With template functions the argument deduction deserves special attention. See section 18.1.3 for this topic.

18.1.1: Template function definitions

    #include <numeric>

    template <typename T>
    T sumVector(T *array, unsigned n)
    {
        return std::accumulate(array, array + n, T());
    }        

Definitions or declarations of templates always start with the template <...> line. It is followed by the template parameter list, which is a comma-separated non-empty list of so-called template type or template non-type parameters, surrounded by angular brackets < and >. In the Annotations template type parameters always start with the keyword typename. In other texts on C++ the keyword class can also be encountered. So, in other texts template definitions might start with a line like:

Using class instead of typename is now, however, considered an anachronism, and is deprecated: a template type parameter is, after all, a type name and not a class.

In the template function sumVector() the only template parameter is T, which is a template type parameter. T is the formal type that is used in the template function definition to represent the actual type that will be specified when the template function is instantiated. This type is used in the parameter list of the function, it is used to define the type of a local variable of the function, and it is used to define the return type of the function.

Normal scope rules and identifier rules apply to template definitions and declarations: the type T is a formal name, it could have been named Type. The formal typename that is used overrules, within the scope of the template definition or declaration, any previously defined identifiers by that name.

A template non-type parameter represents a constant expression, which must be known by the time the template is instantiated, and which is specified in terms of existing types, such as an unsigned. An alternative definition for the above template function, using a template non-type parameter is (note that there are two versions: one for arrays having const elements, one for arrays having elements that can be modified):

    #include <numeric>

    template <typename T, unsigned size>       // non-const arrays
    T sumVector(T (&array)[size])
    {
        return std::accumulate(array, array + size, T());
    }        

    template <typename T, unsigned size>       // const arrays
    T sumVector(const T (&array)[size])
    {
        return std::accumulate(array, array + size, T());
    }        

    template 
    <
        class T1, 
        class T2, 
        unsigned size1, 
        unsigned size2
    >
        T1
        (
            *outerProduct
            (
                T2 const (&v1)[size1], 
                T2 const (&v2)[size2]
            )
        )[size2];

The keyword typename is required in certain situations that may occur when the template function is defined. For example, assume we define the following template function:

    template <typename T>
    void function()
    {
        T::member
            *p;
    }        

The compiler does so, because it cannot know from the template definition whether member is a typename, defined in the class T, or a member of the class T. It takes the latter and, consequently, interprets the * as a multiplication operator.

What if this interpretation was not intended? In that case the typename keyword must be used. In the following template definition the * indicates a pointer definition to a T::member type.

    template <typename T>
    void function()
    {
        typename T::member
            *p;
    }        

18.1.2: Instantiations of template functions

For example, in the following code it is assumed that the function sumVector has been defined in the header file sumvector.h. In the function main() the function sumVector() is called once for the int array x, once for the double array y, and once the address is taken of a sumVector() function. By taking the address of a sumVector function the type of the argument is defined by the type of the pointer variable, in this case a pointer to a function processing a array of unsigned long values. Since such a function wasn't available yet (we had functions for ints and doubles), it is constructed once its address is required. Here is the function main():

    #include <iostream>
    #include "sumvector.h"

    using namespace std;
    
    int main()
    {
        int
            x[] = {1, 2};
        double
            y[] = {1.1, 2.2};
    
        cout << sumVector(x, 2) << endl     // first instantiation
            << sumVector(y, 2) << endl;     // second instantiation
    
        unsigned long                       // third instantiation
            (*pf)(unsigned long *, unsigned) = sumVector;
    }
    /*
        Generated output:

        3
        3.3
    */

    #include <iostream>
    #include "sumvector.h"

    unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
    double fun(double (*f)(double *p, unsigned n));
    
    int main()
    {
        std::cout << fun(sumVector) << std::endl;
    }

    In function `int main()':
    call of overloaded `fun ({unknown type})' is ambiguous
    candidates are: fun(unsigned int (*)(unsigned int *, unsigned int))
                    fun(double (*)(double *, unsigned int))

    #include <iostream>
    #include "sumvector.h"

    unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
    double fun(double (*f)(double *p, unsigned n));
    
    int main()
    {
        std::cout 
            << fun(static_cast<double (*)(double *, unsigned)>(sumVector)) 
            << std::endl;

        return 0;
    }

If the same template function definition was included in different source files, which are then compiled to different object files which are thereupon linked together, there will, per type of template function, be only one instantiation of the template function in the final program.

This is illustrated by the following example, in which the address of a function sumVector() for int arrays is written to cout. The first part defines a function fun() in which the address of a sumVector() function is written to cout. The second part defines a function main(), defined in a different sourcefile, in which the address of a similar sumVector() function is written to cout, and in which fun() is called. Both sources use the union PointerUnion to convert a pointer to a function to a void *. Here is the used union:

    union PointerUnion
    {
        int (*fp)(int *, unsigned);
        void *vp;
    };

    #include <iostream>
    #include "sumvector.h"
    #include "pointerunion.h"

    void fun()
    {
        PointerUnion
            pu = { sumVector };

        std::cout << pu.vp << std::endl;
    }

    #include <iostream>
    #include "sumvector.h"
    #include "pointerunion.h"

    void fun();

    int main()
    {
        fun();

        PointerUnion
            pu = { sumVector };
        
        std::cout << pu.vp << std::endl;

        return 0;
    }
    /*
        Generated output (actual pointer values may be different):
    
        0x8048710
        0x8048710
    */

18.1.2.1: Declaring template functions

Template functions can be declared as well. If it is known that the required instantiation is available from another source file, as the sumVector that was used in the function fun() in the previous section, then there is actually no need to instantiate the function sumVector() again.

A template function declaration is constructed like any other function declaration: by replacing its code with a semicolon. For example:

    #include <iostream>
    #include "sumvector.h"
    #include "pointerunion.h"

    template<typename T>
    T sumVector(T *tp, unsigned n);

    void fun()
    {
        PointerUnion
            pu = { sumVector };

        std::cout << pu.vp << std::endl;
    }

Regarding namespaces: template function definitions should not use using directives or declarations: the template might be used in a situation where such a directive overrides the programmer's intentions: ambiguities or other conflicts may result from the template's author and the programmer using different using directives (E.g, a cout variable defined in the std namespace and in the programmer's own namespace).

18.1.3: Argument deduction

For example, consider once again the function

    #include <numeric>

    template <typename T, unsigned size>       // non-const arrays
    T sumVector(T (&array)[size])
    {
        return std::accumulate(array, array + size, T());
    }        

    template <typename T, unsigned size>       // const arrays
    T sumVector(const T (&array)[size])
    {
        return std::accumulate(array, array + size, T());
    }        

    #include "sumvectorsize.h"

    int main()
    {
        int
            iArray[] = {1, 2, 3},
            *iPtr = iArray;

        sumVector(iArray);  // succeeds: size of iArray is known
        sumVector(iPtr);    // fails: size of array pointed to by 
                            // iPtr is unknown 
    }

• lvalue transformations
• qualification conversions
• conversion to a base class instantiated from a class template

18.1.3.1: Lvalue transformations

There are three types of lvalue transformations:

• lvalue-to-rvalue conversions
• array-to-pointer conversions
• function-to-pointer conversions

lvalue-to-rvalue conversions.

An lvalue-to-rvalue conversion takes place in situations where the value of an lvalue expression is required. This also happens when a variable is used as argument to a function having a value parameter.

array-to-pointer conversions.

An array-to-pointer conversion occurs when the name of an array is assign to a pointer variable. This is frequently seen with functions using parameters that are pointer variables. When calling such functions, an array is often specified as argument to the function. The address of the array is then assigned to the pointer-parameter. This is called an array-to-pointer conversion.

function-to-pointer conversions.

This conversion is most often seen with functions defining a parameter which is a pointer to a function. When calling such a function the name of a function may be specified for the parameter which is a pointer to a function. The address of the function is then assigned to the pointer-parameter. This is called a function-to-pointer conversion.

18.1.3.2: Qualification conversions

A qualification conversion adds const or volatile qualifications to pointers. Assume the function sumVector() in section 18.1.1 was defined as follows:

    #include <numeric>

    template <typename T>
    T sumVector(T const *array, unsigned n)
    {
        return std::accumulate(array, array + n, T());
    }        

18.1.3.3: Conversion to a base class

In section 18.2 template classes are formally introduced. However, they were already used earlier: abstract containers (covered in chapter 12) are actually defined as template classes. Like `normal' classes, template classes can participate in the construction of class hierarchies. In section 18.2.7 it is shown how a template class can be derived from another template class.

Assume that the template class Pipe is derived from the class queue. Furthermore, assume our function sumVector() was written to return the sum of the elements of a queue:

    template <typename T>
    T sumVector(std::queue<T> &queue)
    {
        T sum();        

        while (!queue.empty())
        {
            sum += queue.front();
            queue.pop();
        }
        return sum;
    }        

• Pipe<xxx> has queue<xxx> as its base class, and
• queue<xxx> is a possible first argument of the above template function sumVector(), and
• a function argument which is of a derived class type may be used with a base class parameter of a template function.

This conversion is called a conversion to a base class instantiated from a class template. In the above example, the class template is Pipe, the base class is queue.

18.1.3.4: Summary: the template argument deduction algorithm

The following algorithm is used with template argument deduction when a template function is called with one or more arguments:

• In turn, the template parameters are identified in the parameters of the called function.
• For each template parameter, the template's type is deduced from the template function's argument (e.g., int if the argument is a Pipe<int> object).
• The three allowed conversions (see section 18.1.3) for template arguments are applied where necessary.
• If the same template parameter is used with multiple function parameters, the template types of the arguments must be the same. E.g., with template function

      twoVectors(std::vector<Type> &v1, std::vector<Type> &v2)
  

  the arguments used with twoVectors() must have equal types. E.g.,

      extern std::vector<int> v1;
      extern std::vector<int> v2;
  
      twoVectors(v1, v2);
  

18.1.4: Explicit arguments

    #include <iostream>
    #include "sumvector.h"

    using namespace std;

    int main()
    {
        int     x[] = {1, 2};
        double  y[] = {1.1, 2.2};
    
        cout << sumVector(x, 2) << endl
            << sumVector(y, 2) << endl;

        return 0;
    }

In section 18.1.2, a type cast was used to disambiguate. Rather than using a static_cast, the type of the required function can be made explicit using another syntax: the function name may be followed by the types of the arguments, surrounded by pointed brackets. Here is the example of section 18.1.2 using an explicit template argument type:

    #include <iostream>
    #include "sumvector.h"

    unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
    double fun(double (*f)(double *p, unsigned n));
    
    int main(int argc, char **argv)
    {
        std::cout << fun(sumVector<double>) << std::endl;
    }

18.1.4.1: Template explicit instantiation declarations

Templates can be declared, explicitly providing the types of the template's arguments with the purpose of instantiating these templates. Such an explicit instantiation declaration starts with the keyword template, to be followed by an explicit template instantiation declaration. Although this is a declaration (see also section 18.1.2.1), it is also understood by the compiler as a request to instantiate that particular variant of the function.

By using explicit instantiation declarations it is possible to collect all required instantiations of a template functions in one file, so that sources using these template functions can use plain, non-instantiating template function declarations, in order to redure their compilation time. For example, several sumVector() functions can be nstantiated as follows:

    #include "sumvector.h"

    template      int sumVector<int>(int *, unsigned);
    template   double sumVector<double>(double *, unsigned);
    template unsigned sumVector<unsigned>(unsigned *, unsigned);

embellished with the template keyword and an explicit template argument list, e.g., <int>.

18.1.5: Template explicit specialization

For example, the template's implementation of sumVector() is not suited for variables of type char *, like the argv parameter of main(). If we want to be able to use sumVector() with variables of type char * as well, we can define the following special form of sumVector():

    #include <iostream>
    #include "specialization.h"

    int main(int argc, char **argv)
    {
        std::cout << sumVector(argv, argc);
    }

The template explicit specialization is normally included in the same file as the standard implementation of the template function. If the template explicit specialization is to be used in a different file than the file in which it is defined, it must be declared. Of course, being a template function, the definition of the template explicit specialization can also be included in every file in which it is used, but that will also slow down the compilation of those other files.

The declaration of a template explicit specialization obeys the standard syntax of a function declaration: the definition is replaced by a semicolon. Therefore, the declaration of the above template explicit specialization is

Note the pair of pointed brackets following the template keyword. Were they omitted, the function would reduce to a template instantiation declaration: you would not notice it, except for the longer compilation time, as using a template instantiation declaration implies an extra instantiation (i.e., compilation) of the function. Furthermore, only one location of the non-template function would be allowed in the sources of a program, so a header file would not exactly be a good location for the code of a non-template function.

In the declaration of the template explicit specialization the explicit specification of the template arguments (in the < ... > list following the name of the function) can be omitted if the types of the arguments can be deduced from the types of the arguments. With the above declaration this is the case. Therefore, the declaration can be simplified to:

Comparably, the template <> part of the template explicit specialization may be omitted. The result is an ordinary function or ordinary function declaration. This is not an error: template functions and non-template functions may overload each other. Ordinary functions are less restrictive in the type conversions that are allowed for their arguments than template functions, which might be a reason for using an ordinary function.

18.1.6: Overloading template functions

    #include <vector>
    #include <numeric>

    template <typename T>
    T sumVector(std::vector<T> &array)
    {
        return std::accumulate(array.begin(), array.end(), T());
    }        

    void fun(std::vector<int> &vi)
    {
        std::cout << sumVector(vi) << std::endl;
    }

    template <typename T>
    T sumVector(std::vector<T> &array);

    template<typename T>
    bool differentSigns(T v1, T v2)
    {
        return
        (
            v1 < 0 && v2 >= 0
            ||
            v1 >= 0 && v2 < 0
        );
    }

    template<typename T1, typename T2>
    bool differentSigns(T1 v1, T2 v2);

On the other hand, if one overloaded version can be interpreted as a more specialized variant of another version of a template function, then in principle the two variants of the template function could be used if the arguments are of the more specialized types. In this case, there is no ambiguity, as the compiler will use the more specialized variant if the arguments so suggest.

So, assume an overloaded version of sumVector() is defined having the following prototype and a snippet of code requiring the instantiation of sumVector:

    template <typename T>
    T sumVector(T, unsigned);

    extern int iArray[];

    void fun()
    {
        sumVector(iArray, 12);
    }

In situations like this there is no ambiguity if both declarations are identical but for the fact that one version is able to accept a superset of the possible arguments that are acceptable for the other version. The original sumVector() template can accept only a pointer type as its first argument. The version declared here can accept a pointer type as well as any non-pointer type. A pointer type iArray is passed, so both template functions are candidates for instantiation. However, the original sumVector() template function can only accept a pointer type as its first argument. It is therefore more specialized than the one given here, and it is therefore selected by the compiler. If, for some reason, this is not appropriate, then an explicit template argument can be used to overrule the selection made by the compiler. E.g.,

18.1.7: Selecting an overloaded (template) function

• First, a set of candidate functions is constructed. This set contains all functions that are visible at the point of the call, having the same name as the function that is called. For a template function to be considered here, depends on the actual arguments that are used. These arguments must be acceptable given the standard template argument deduction process described in section 18.1.3. For example, assume all of the following declarations were provided:

      template <typename T, typename U>
      bool differentSigns(T t, U u);
  
      bool differentSigns(double i, double j);
      bool differentSigns(bool i, bool j);
      bool differentSigns(int (&i)[2]);
  

  Each of these functions will be included in the set of candidate functions in the following code fragment, as all of the four functions have the same name of the function that is called:

      #include "candidates.h"
  
      int main()
      {
          differentSigns(int(), double());
      }
  

• Second, the set of viable functions is constructed. Viable functions are functions for which type conversions exist that can be applied to match the types of the parameters of the functions and the types of the actual arguments. This removes the last two function declarations from the initial set: the third function is removed as there is no standard conversion from double to int, and the fourth function is removed as there is a mismatch in the number of arguments between the called function and the declared function.
• Third, the remaining functions are ranked in order of preference, and the first one is going to be used. Let's see what this boils down to:
  • For the template function, the function differentSign<int, double> is instantiated. For this function the types of the two parameters and arguments for a pairwise exact match: score two points for the template function.
  • For the function bool differentSigns(double i, double j) the type of the second parameter is exactly matches the type of the second argument, but a (standard) conversion int -> double is required for the first argument: score one point for this function.
  Consequently, the template function is selected as the one to be used. As an exercise, feed the above four declarations and the function fun() to the compiler and wait for the linker errors: ignoring the undefined reference to main(), the linker will complain that the (template) function bool differentSigns<int, double>(int, double)

  is an undefined reference.

    template <typename T>
    bool differentSigns(T t, T u);

As we've seen, a template function in which all type parameters exactly match the types of the arguments prevails over an ordinary function in which a (standard) type conversion is required. Correspondingly, a template explicitly specialized function will prevail over an instantiation of the general template if both instantiations show an exact match between the types of the parameters and the arguments. For example, if the following template declarations are available:

    template <typename T, typename U>
    bool differentSigns(T t, U u);

    template <> bool differentSigns<double, int>(double, int);

Another situation in which an apparent ambiguity arises is when both an ordinary function is available and a proper instantiation of a template can be generated, both exactly matching the types of the arguments of the called function. In this case the compiler does not flag an ambiguity as the oridinary function is considered the more specialized function, which is therefore selected.

As a rule of thumb consider that when there are multiple viable functions sharing the top ranks of the set of viable functions, then the function template instantiations are removed from the set. If only one function remains, it is selected. Otherwise, the call is ambiguous.

18.1.8: Name resolution within template functions

    template <typename T>
    T sumVector(T *array, unsigned n)
    {
        T
            sum = accumulate(array, array + n, T());        

        cout << "The array has " << n << " elements." << endl;
        cout << "The sum is " << sum << endl;

        return sum;
    }        

    std::ostream &std::ostream::operator<<(unsigned)

    std::ostream &std::ostream::operator<<(char const *)

    std::cout << ... << sum << std::endl

Names (variables) whose type depend on a template parameter are resolved when the template is instantiated: at that point the relevant declarations must be available. The location where this happens is called the template's point of instantiation. As a rule of thumb, make sure that the necessary declarations (usually: header files) are available at every point of instantiation of the template.

18.2: Template classes

In the upcoming sections the construction of template classes is discussed. In a sense, template classes compete with object oriented programming (cf. chapter 14), where a similar mechanism is seen. Polymorphism allows the programmer to separate algorithms from data, by deriving classes from the base class in which the algorithm is implemented, while implementing the data in the derived class, together with member functions that were defined as pure virtual functions in the base class to handle the data.

Generally, template classes are easier to use. It is certainly easier to write stack<int> istack to create a stack of ints than it is to derive a new class Istack: public stack and to implement all necessary member functions to be able to create a similar stack of ints using object oriented programming. On the other hand, for each different type that is used with a template class the complete class is reinstantiated, whereas in the context of object oriented programming the derived classes use, rather than copy, the functions that are already available in the base class.

Below a simple version of the template class Vector is constructed: the essential characteristics of a template class are illustrated, without attempting to redo the existing vector class completely.

18.2.1: Template class definitions

The construction of a template class can normally begin with the construction of a normal class interface around a hypothetical type Type. If more hypothetical types are required, then hypothetical types U, V, W, etc. can be used as well. Assume we want to construct a class Vector, that can be used to store values of type Type. We want to provide the class with the following members:

• Constructors to create an object of the class Vector, possibly of a given size, as well as a copy constructor, since memory will be allocated by the object to store values of type Type.
• A destructor.
• An overloaded operator=().
• An operator[]() to retrieve and reassign the elements given their indices.
• Forward and backward iterators to be able to visit all elements sequentially, either from the first to the last or from the last to the first.
• A member push_back() to add a new element at the end of the vector.

Now that we have decided which members we want, the class interface can be constructed. Like template functions, a template class definition begins with the keyword template, which is followed by a non-empty list of template type and/or non-type parameters, surrounded by angular brackets. This template announcement is followed by the class interface, in which the template parameters may be used to represent types and constants. Here is the first form of the class interface of the Vector template class, already containing the private member function construct , which is used in the implementation of the copy constructor, the destructor, and the overloaded assignment operator. The class also already contains an iterator type: it's simply defined as a pointer to an element of the vector. The reverse_iterator will be added later. Note that the Vector template class contains only one template type parameter, and no non-type parameter.

    template <typename Type>
    class Vector
    {
        void construct(Vector<Type> const &other);
        Type 
            *d_start,
            *d_finish,
            *d_end_of_storage;
        public:
            typedef reverse_iter<Type> reverse_iterator;

            Vector();
            Vector(unsigned n);
            Vector(Vector<Type> const &other);
            ~Vector();
            Vector<Type> const &operator=(Vector<Type> const &other);
            Type &operator[](int index);
            Vector<Type> &sort();
            void push_back(Type const &value);
            Type *begin();
            Type *end();
            reverse_iterator rbegin();
            reverse_iterator rend();
            unsigned size();
    };

Different from template functions, template class parameters can have default arguments. This holds true both for template type- and template non-type parameters. If a template class is instantiated without specifying arguments for the template parameters, and if default template parameters were defined, then the defaults are used. Such defaults should be suitable for a majority of instantiations of the class. E.g., for the template class Vector the template announcement could have been altered to specify int as the default type:

The class contains three data members: pointers to the begin and end of the allocated storage area (respectively data and end_of_storage) and a pointer pointing just beyond the element that was last allocated. The allocation scheme will add extra elements beyond the ones that are actually required to reduce the number of times the vector must be reallocated to accomodate new elements.

Template classes may be declared by removing the template interface definition (the part between the curly braces), replacing the definition by a semicolon:

    template <typename Type>
    class Vector;

18.2.2: Template class instantiations

    Vector<int>
        vInt;

    Vector<std::string>
        vString;

In combination with the keyword extern template class objects can be declared rather than defined. E.g.,

    extern Vector<int>
        vInt;

    template <typename T>
    Vector<T> cloneVector(Vector<T> &vector)
    {
        return Vector<T>(vector);
    }

    #include "vector.h"

    void add(Vector<int> &vector, int value)
    {
        vector.push_back(value);
    }

18.2.3: Non-type parameters

    template <typename Type, unsigned size>
    class Buffer
    {
        public:
            Type
                buffer[size];
    };

    Buffer<int, 20>
        buffer;

• Global variables have constant addresses, that can be used as arguments for non-type parameters
• Local and dynamically allocated variables have addresses that are not known by the compiler when the source file is compiled. These addresses can therefore not be used as arguments for non-type parameters.
• Lvalue transformations are allowed: if a pointer is defined as a non-type parameter, an array name may be specified.
• Qualification conversions are allowed: a pointer to a non-const object may be used with a non-type parameter defined as a const pointer.
• Promotions are allowed: a constant of a `narrower' data type may be used for the specification of a non-type parameter of a `wider' type (e.g., a short can be used when an int is called for, a long when a double is called for).
• Integral conversions are allowed: if an unsigned parameter is specified, an int may be used too.

18.2.4: Template class member functions

Template member functions must be known to the compiler when the template is instantiated. The current Gnu g++ compiler does not support precompiled template classes, therefore the member functions of templates are inline functions. They can be defined inside the template interface or outside the template interface. Inline template member functions are defined in the same way as inline member functions of non-templates classes. However, for the member functions that are defined outside of the template's interface

• No inline keyword is required in the interface,
• A template <template parameter list> definition is required.

could be declared. When defined outside of the template's interface, its implementation would be:

    template <typename T>
    T &Vector<T>::operator[](unsigned index) throw(char const *)
    {
        if (index >= (beyond - data))
            throw "Vector array index out of bounds";
        return data[index];
    }

18.2.5: Template classes and friend declarations

• A nontemplate friend function or class. This is a well-known friend declaration, such as the insertion operator for ostream objects.
• A bound friend template class or function. Here the template parameters of the current template are used to bind the types of another template class or function, so that a one-to-one correspondence between the template's parameters and the template parameters of the friend template class or function is obtained.
• A unbound friend template class or function. Here the template parameters of the friend template class or function remain to be specified, and are not related in some predefined way to the current template's parameters.

18.2.5.1: Non-template friends

A template class may declare another function or class or class member function as its friend. Such a friend may access the private members of the template class. Classes and ordinary functions can be declared as friend, but a class interface must have been seen by the compiler before one of its members can be declared a friend of a template class (in order to verify the name of the friend function against the interface).

For example, here are some friend declarations:

    class Friend
    {
        public:
            void member();
    };

    template <typename T>
    class Vector
    {
        friend class AnotherFriend;     // declaration only is ok here
        friend void anotherMember();    // declaration is ok here
        friend Friend::member();        // Friend interface class required.
    };

18.2.5.2: Bound friends

With bound friend template classes or functions there is a one-to-one mapping between the types that are used with the instantiations of the friends and the template class declaring them as friends. Here the friends are themselves templates. For example:

    template <typename T>
    class Friend;                   // declare a template class        

    template <typename T>
    void function(Friend<T> &t);    // declare a template function

    template <typename T>
    class AnotherFriend
    {
        public:
            void member();          // a member function within a class
    }

    template <typename T>
    class Vector
    {
        friend class Friend<T>;                     // 1 (see the text)
        friend void function<T>(Friend<T> t);       // 2
        friend void AnotherFriend<T>::member();     // 3
    };

• At 1, the class Friend is declared a friend of Vector if it is instantiated for the same type T as Vector itself.
• At 2, the function function is declared a friend of Vector if it is instantiated for the same type T as Vector itself. Note that the template type parameter T appears immediately following the function name in the friend declaration. Here the correspondence between the function's template parameter and Vector's template parameter is defined. After all, function() could have been a parameterless function. Without the <T> affixed to the function name, it is an ordinary function, expecting an (unrestricted) instantiation of the class Vector for its argument.
• At 3, a specific member function of the class AnotherFriend, instantiated for type T is declared as a friend of the class Vector.

    #include <algorithm>
    #include <iostream>

    template<typename T>
    class Vector
    {
        friend std::ostream &operator<< <T> (std::ostream &str, 
                                            Vector<T> const &vector);
        T *d_data;
        T *d_beyond;
    };        

    template <typename T>
    std::ostream &operator<<(std::ostream &str, Vector<T> const &vector)
    {
        std::copy(vector.d_data, vector.d_beyond, 
                            std::ostream_iterator<T *>(str, " "));
        return str;
    }

18.2.5.3: Unbound friends

By prepending the friend keyword to the template<typelist> phrase, friends received their own template parameter list. The template types of these friends are completely independent from the type of the template class declaring the friends. Such friends are called unbound friends. Every instantiation of an unbound friend has unrestricted access to the private members of every instantiation of the template class declaring the friends.

Here is the syntactic convention for declaring an unbound friend function, an unbound friend class and an unbound friend member function of a class:

    template <typename Type>
    class Vector
    {
        template <typename T>
        friend void function(); // unbound friend function

        template <typename T>
        friend class Friend;    // unbound friend class

        template <typename T>      // unbound friend member function
        friend void AnotherFriend<T>::member();
    };

18.2.6: Template classes and static data

    template <typename Type>
    class TheClass
    {
        static int s_objectCounter;        
    };

    TheClass<int> theClassOne;
    TheClass<int> theClassTwo;

    template <typename Type>
    class TheClass
    {
        static int s_objectCounter;         // declaration
                
    };

    template <typename Type>                // definition
    int TheClass<Type>::s_objectCounter = 0;

    template <typename Type>
    class TheClass
    {
        static TheClass *s_objectPtr;
    };

    template <typename Type>
    TheClass<Type> *TheClass<Type>::s_objectPtr = 0;

18.2.7: Derived Template Classes

    template<typename T>
    class Base
    {
        T const &t;

        public:
            Base(T const &t)
            :
                t(t)
            {}
    };

    template<typename T>
    class Derived: public Base<T>
    {
        public:
            Derived(T const &t)
            :
                Base(t)
            {}
    };

    class Ordinary: public Base<int>
    {
        public:
            Ordinary(int x)
            :
                Base(x)
            {}
    };

    // With the following object definition:
    Ordinary
        o(5);

18.2.8: Nesting and template classes

Also, the surrounding class is allowing access to its private members by the class reverse_iterator, so once the definition of the class reverse_iterator has been seen by the compiler, we're ready to declare reverse_iterator a friend of Vector<Type>.

Once the classes are set up, a main program constructs a Vector<int>, which is used to construct a Vector<int>::reverse_iterator, using its rbegin() member. This member, however, returns an anonymous (and thus: constant) reverse_iterator object. So the public copy constructor is used to make a non-constant reverse_iterator object available in main(), as the rbegin object. Here is the skeleton program, omitting all data members and extra member functions:

    #include <iostream>

    template <typename Type>
    class Vector
    {
        class reverse_iterator
        {
            friend class Vector<Type>;

            reverse_iterator(Vector<Type> *vector);

            public:
                reverse_iterator(reverse_iterator const &other);
                Type &operator*() const;
        };

        friend class reverse_iterator;

        public:
            Vector();
            reverse_iterator rbegin()
            {
                return reverse_iterator(this);
            }
    };
            
    int main()
    {
        Vector<int>
            vi;

        Vector<int>::reverse_iterator
            rbegin = vi.rbegin();

        std::cout << *rbegin;
    }

Nested enumerations and typedefs can be defined in template classes as well. For example, with arrays the distinction between the last index that can be used and the number of elements frequently causes confusion in people who are exposed to C-array types for the first time. The following construction automatically provides valid last and nElements definition:

    template<typename Type, int size>
    class Buffer
    {
        Type    *b;

        public:
            enum Limits
            {
                last = size - 1,
                nElements
            };
            typedef Type elementType;

            Buffer()
            :
                b(new Type [size])
            {}
    };

Of course, the above represents the template form of these values and declarations. They must be instantiated before they can be used. E.g,

is a synonym of int.

Note that a construction like Buffer::elementType is illegal, as the type of the Buffer class remains unknown.

18.2.9: Member templates

    template <typename Type1>
    class Outer
    {
        public:
            template <typename Type2>              // template class
            class Inner
            {
                public:
                    Type1
                        variable1;
                    Type2
                        variable2;
            };
                        
            template <typename Type3>              // template function
            Type3 process(Type3 const &p1, Type3 const &p2)
            {
                Type3
                    result;

                return result;
            }
    };

• Normal access rules apply: the function process() can be used by the general program, given an instantiated Outer object. Of course, this implies that a large number of possible instantiations of process() are possible. Actually, an instantiation is only then constructed when a process() function is in fact used. In the following code the member function int process(int const &p1, int const &p2) is instantiated, even though the object is of the class Outer<double>:

      Outer<double>
          outer;
  
      outer.process(10, -3);
  

  The process() template member function allows the processing of any other type by an object of the class Outer.
• Any function can be defined as a template function, not just an ordinary member function. A constructor can be defined as a template member as well:

      template <typename Type1>
      class Outer
      {
          public:
              template <typename Type2>     // template class
              Outer(Type2 const &initialValue)
              {}
      };
  

  Here, an Outer object can be constructed for a particular type given another type that's given to the constructor. E.g.

      Outer<int>
          t(12.5);    // instantiates Outer(double const &initialvalue)
  

• Template members can be defined inline or outside of their containing class. When a member is defined outside of its surrounding class, the template parameter list must precede the template parameter list of the template member. E.g.,

      template <typename Type1>
      class Outer
      {
          public:
              template <typename Type2>                  // template class
              class Inner;
  
              template <typename Type>                   // template function
              Type process(Type const &p1, Type const &p2);
      };
  
                                                      // template class member
      template <typename Type1> template <typename Type2>   
  
      class Outer<Type1>::Inner                       // no Type2 with `Inner'
      {
          public: 
              Type1
                  variable1;
              Type2
                  variable2;
      };  
                                                      // template function member
      template <typename Type1> template <typename Type>    
      Type Outer<Type1>::process(Type const &p1, Type const &p2)
      {
          Type
              result;
          return result;
      }
  

  Note the way the class Inner starts its implementation: with the Outer class template parameters are used, with the Inner class definition the template parameters must be omitted.
• When template member classes are not defined inline, the formal template parameter names in the declaration and implementation must be identical.

18.2.10: Template class specializations

Assume we have a template class which supports the insertion of its type parameter into an ostream. E.g.,

    template <typename Type>
    class Inserter
    {
        public:
            Inserter(Type const &t)
            :
                object(t)
            {}
            ostream &insert(ostream &os) const
            {
                return os << object;
            }
        private:
            Type 
                object;
    };

    int main()
    {
        Inserter<int>
            ins(5);
    
        ins.insert(cout) << endl;
    }

    class Person
    {
        public:
            std::ostream &insert(std::ostream &ostr) const;
    };

    int main()
    {
        Person 
            person;
        Inserter<Person>
            p2(person);
    
        p2.insert(std::cout) << endl;
    }

For this situation multiple solutions exist. One would be to define an operator<<(Person const &p) function which calls the Person::insert() function. But in the context of the Inserter class, this might not what we want. Instead, we might want to look for a solution that is closer to the class Inserter.

Such a solution exists in the form of a template class specialization. Such an explicit specialization definition starts with the word template, then two angular brackets (<>), which is then followed by the function definition for the nstantiation of the template class for the specific template parameters. So, with the above function this yields the following function definition:

    template<>
    std::ostream  &Inserter<Person>::insert(std::ostream &os) const
    {
        return object.insert(os);
    }

Note that the explicit specialization definition is a true definition: it should not be given in the header file of the Inserter template class, but it should have its own source file. However, in order to inform the compiler that an explicit specialization is available, it can be declared in the template's header file. The declaration is straightforward: the code-block is replaced by the semicolon:

    template<>
    std::ostream  &Inserter<Person>::insert(std::ostream &os) const;

    template <>
    class Inserter
    {
        public:
            Inserter<double>(double const &t);
            std::ostream &insert(std::ostream &os) const;
        private:
            double
                object;
    };

    Inserter<double>(double const &t)   // NO template<> prefix !
    :
        object(t)
    {}

18.2.11: Template class partial specializations

Let's assume we are working on a image processing program. A class defining an image receives two int template parameters, e.g.,

    template <int columns, int rows>
    class Image        
    {
        public:
            Image()
            {
                // uses 'columns' and 'rows'
            }
    };

    template <int rows>
    class Image<320, rows>
    {
        public:
            Image()
            {
                // use 320 columns and 'rows' rows.
            }
    };

    Image<320, 240>
        image;

Every template parameter can be used for the specialization. In the last example the columns were specialized, but the rows could have been specialized as well. The following partial specialization of the template class Image specializes the rows parameter and leaves the columns open for later specification:

    template <int columns>
    class Image<columns, 200>
    {
        public:
            Image()
            {
                // use 'columns' columns and 200 rows.
            }
    };

    Image<1024, 768>
        generic;
    Image<320, 240>
        columnSpecialization;
    Image<480, 200>
        rowSpecialization;

One might wonder what happens if we want to construct the following image:

    Image<320, 200>
        superSpecialized;

    template <>
    class Image<320, 200>
    {
        public:
            Image()
            {
                // use 320 columns and 200 rows.
            }
    };

18.2.12: Name resolution within template classes

On the other hand, if a template defines a <typename Type> template parameter, which is the returntype of some template function, e.g.,

    Type returnValue();

    template <typename Type>
    class Resolver
    {
        Type        d_datum;
        static int  d_value;

        public:
            Resolver();
            Type result();
    };

    // ----------------------- example 1: define the static variable
    int Resolver<std::string>::d_value = 12;   

    // ----------------------- example 2: define a Resolver object
    int main()
    {
        Resolver<std::string>   resolver;
    }

    // ----------------------- example 3: declare a Resolver object
    extern Resolver<string>
        resolver;

18.3: Constructing iterators

Also, in section 17.2 the characterstics of iterators were introduced: basically it should be possible to increment iterators, to dereference iterators and to compare iterators for equality.

However, in order to use iterators in the context of the generic algorithms iterators often must meet extra requirements. This is caused by the fact that generic algorithms check the types of the iterators they receive. Simple pointers are usually accepted, but if a class is used as an iterator, the iterator-class must be able to specify the kind of iterator it represents.

To make sure that an object of a class is interpreted as a particular type of iterator, the class must be derived from the classes input_iterator, output_iterator, forward_iterator, bidirectional_iterator, or random_access_iterator. These classes mainly define tags which are used by generic algorithms to check the correct types of the provided iterators, and have nothing to do with the actual implementation of the iterators. In order to derive classes from the iterator-classes, sources must

    #include <iterator>

To construct a class Iterator that can be used as an iterator (which could be an ordinary iterator, a const_iterator, a reverse_iterator or a const_reverse_iterator) for type `Type' (which may be a template type parameter or a specific type like an int or a string), one must be prepared to implement several members. Also, these iterator-classes must be derived from appropriate iterator-tag classes. With the exception of the output_iterator base class, these iterator classes are template classes themselves, using Type and ptrdiff_t as their template class parameters. The following iterator classes can thus be constructed:

• An InputIterator:
  • Base class: std::input_iterator<Type, ptrdiff_t>
  • Type const &operator*() const: the dereference operator.
  • Iterator &operator++(): the prefix increment operator.
  • bool operator==(Iterator const &other): the operator to compare two iterators for equality.
• An OutputIterator:
  • Base class: std::output_iterator (Note: no template class)
  • Type &operator*() const: the dereference operator.
  • Iterator &operator++(): the prefix increment operator.
• A ForwardIterator:
  • Base class: std::forward_iterator<Type, ptrdiff_t>
  • Type &operator*() const: the dereference operator.
  • Iterator &operator++(): the prefix increment operator.
• A BidirectionalIterator:
  • Base class: std::bidirectional_iterator<Type, ptrdiff_t>
  • The same members as required for the ForwardIterator
  • : the postfix increment operator.
  • Iterator &operator--(): the prefix decrement operator.
  • Iterator &operator--(int): the postfix decrement operator.
• A RandomAccessIterator:
  • Base class: std::random_access_iterator<Type, ptrdiff_t>
  • The same members as required for the BidirectionalIterator
  • Iterator operator+(int step): the random step forward operator.
  • Iterator operator-(int step): the random step backward operator.
  • : the pointer arithmetic operator.
  • : the comparison operator applied to the Iterators themselves. Note that this is not a comparison applied to two Type values: with the RandomAccessIterator it must be possible to order the iterators themselves, so they can be compared with respect to their relative magnitudes.

• Next chapter
• Previous chapter
• Table of contents