- Next chapter
- Previous chapter
- Table of contents

# Chapter 16: 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. Mail to Frank Brokken or use an e-mail form. Please state the concerned document version, found in the title.

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 de chapter on abstract containers.

These general functions or classes become concrete code once their definitions are applied to real entities. The general definitions of functions or classes are called templates, the concrete implementations instantiations.

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

## 16.1: Template functions

Template functions are used in cases where a single implementation of a function is not practical due to the different types that are distinguished in C++. If a function is defined as
`fun(int *array)`
then this function will likely run into problems if it is passed the address of an array of `double` values. The function will normally have to be duplicated for parameters of different types. For example, a function computing the sum of the elements of an array for an array of `ints` is:

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

The function must be overloaded for arrays of doubles:

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

In a local program development situation this hardly ever happens, since only one or two `sumVector()` implementations will be required. But the strongly typed nature of C++ stands in the way of creating a truly general function, that can be used for any type of array.

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 general array. In the coming 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, which is given in section 16.1.3.

### 16.1.1: Template function definitions

The definition of a template function is very similar to the definition of a normal function, except for the fact that the parameters, the types that are used in the function, and the function's return value may be specified in a completely general way. The function `sumVector()` in the previous section can as follows be rewritten as a template function:

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

Note the correspondence with the formerly defined `sumVector()` functions. In fact, if a `typedef int T` had been specified, the template function, except for the initial `template` line, would be the first `sumVector()` function of the previous section. So, the essence of the template function is found in the first line. From the above example:
`template <class T>`
This line starts out the definition or declaration of a template function. 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 template function `sumVector()` the only template parameter is `T`, which is a template type parameter. ttT) 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:

            template <class T, unsigned size>
            T sumVector(const T (&array)[size])
            {
                T
                    sum(0);
                for (int idx = 0; idx < size; ++idx)
                    sum += array[idx];
                return (sum);
            }

Template function definitions may have multiple type and non-type parameters. Each parameter name must be unique. For example, the following template declaration declares a template function for a function `outerProduct()`, returning a pointer to vectors of `size2 T2` elements, and expecting two vectors of, respectively, `size1` and `size2` elements:

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

Note that the return type `T1` of the returned vectors is intentionally specified different from `T2`. This allows us to specify, e.g., return type `double` for the returned outer product, while the vectors passed to `outerProduct` are of type `int`. Instead of using the keyword `class`, the keyword `typename` can be used in template type parameter lists. However, 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 <class T>
            void function()
            {
                unsigned
                    p;
                ...
                {
                    T::member
                        *p;
                    ...
                }
            }

Although the layout of the above function suggests that `p` is defined as a pointer to the type `member`, that must have been declared in the class that is specified when the function is instantiated, it actually is interpreted by the compiler as a multiplication of `T::member` and `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 <class T>
            void function()
            {
                unsigned
                    p;
                ...
                {
                    typename T::member
                        *p;
                    ...
                }
            }

16.1.1.1: The keyword 'typename'

As illustrated in section 16.1.1 The keyword `typename` can be used to disambiguate members and typenames in cases where the template type parameter represents a class type. It can also be used instead of the `class` keyword indicating a template type. So, instead of

        template <class T>
        void function(T type)
        {
            ...
        }

the function can be defined as:

        template <typename T>
        void function(T type)
        {
            ...
        }

### 16.1.2: Instantiations of template functions

Consider the first template function definition in section 16.1.1. This definition is a mere recipe for constructing a particular function. The function is actually constructed once it is used, or its address is taken. Its type is implicitly defined by the nature of its parameters.

For example, in the following code assumes 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 "sumvector.h"

        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;

            return (0);
        }

While in the above example the functions `sumVector()` could be instantiated, this is not always possible. Consider the following code:

        #include "template.h"

        unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
        double fun(double (*f)(double *p, unsigned n));

        int main()
        {
            cout << fun(sumVector) << endl;
            return (0);
        }

In the above example the function `fun()` is called in the function `main()`. Although it appears that the address of the function `sumVector()` is passed over to the function `fun()`, there is a slight problem: there are two overloaded versions of the function `fun()`, and both can be given the address of a function `sumVector()`. The first function `fun()` expects an `unsigned *`, the second one a `double *`. Which instantiation must be used for `sumVector()` in the `fun(sumVector)` expression? This is an ambiguity, which balks the compiler. The compiler complains with a message like

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

Situations like this should of course be avoided. Template functions can only be instantiated if this can be done unambiguously. It is, however, possible to disambiguate the situation using a cast. In the following code fragment the (proper) `double *` implementation is forced by means of a `static_cast`:

        #include "template.h"

        unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
        double fun(double (*f)(double *p, unsigned n));

        int main()
        {
            cout << fun(static_cast<double (*)(double *, unsigned)>(sumVector))
                << endl;
            return (0);
        }

But casts should be avoided, where possible. Fortunately the cast can be avoided in this kind of situation, as described in section 16.1.4.

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:

        // This is source file 1: fun.cc
        #include "template.h"
        void fun()
        {
            cout << static_cast<void *>
                    (
                        static_cast<int (*)(int *, unsigned)>
                        (sumVector)
                    )
                << endl;
        }

        // This is source file 2: main.cc
        #include "template.h"

        void fun();

        int main()
        {
            fun();

            cout << static_cast<void *>
                    (
                        static_cast<int (*)(int *, unsigned)>
                        (sumVector)
                    )
                << endl;

            return (0);
        }

After compiling and linking the above two source files, the resulting program produces output like:

        0x8048760
        0x8048760

the addresses of the two functions are the same, so each function eventually uses the same implementation of the template function.

Knowing this, it is also understandable that it is possible to declare a template function, if it is known that the required instantiation is available in another sourcefile. E.g., the function `fun()` in the above example could be defined as follows:

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

        void fun()
        {
            cout << static_cast<void *>
                    (
                        static_cast<int (*)(int *, unsigned)>
                        (sumVector)
                    )
                << endl;
        }

To make this work, one must of course be certain that the instantiation is available elsewhere. The advantage of this approach is that the compiler doesn't have to instantiate a template function, which speeds up the compilation of the function `fun()`, the disadvantage is that we have to do the bookkeeping ourselves: is the template function used somewhere else or not?

A third approach, is to declare template functions in header files, keeping the definition in a template source file. In the template source file the functions are instantiated by pointers to the appropriate functions. For example, define `sumvector.cc` as follows:

        template<class T>
        T sumVector(T *tp, unsigned n)
        {
            return (*tp);
        }

        static void
            *p1 = static_cast<int (*)(int *, unsigned)>(sumVector);

and declare the `sumVector` template function in all sourcefiles using `sumVector`. This way the compiler keeps track of which `sumVector()` functions are required, linking them from the `sumvector.o` object when necessary. Of course, they must be available there. But if they aren't then they can be defined simply by providing another pointer defnition, followed by a recompilation of `sumvector.cc`. The advantage here is gain in compilation time (and maybe a clear overview of what template functions are actually instantiated), as well as data hiding: the implementation of the template function is not required by the users of the implementation, and can therefore be hidden from them. The disadvantage is the definition of a bunch of `static void *` variables: they are used as `rvalues` for the addresses of instantiated template functions. Another disadvantage is that the template definition is not available for other situations. If some program would benefit from a `sumVector()` instantiation for a type that is not available in `sumvector.cc`, the template itself or the `sumvector.cc` sourcefile would be required (since we strongly agree with the principles of the free software foundation, the latter disadvantage is actually more of an advantage in our opinion :-).

Finally, as the structure of the `void *` definitions is always the same, a `macro` definition might come in handy here. E.g., the `sumvector.cc` source file in which three `sumVector()` functions are instantiated could be written as follows:

        template<class T>
        T sumVector(T *tp, unsigned n)
        {
            return (*tp);
        }
                            // NOTE: the next line ends at the backslash
        #define instantiate(type)   \
            static_cast<type (*)(type *, unsigned)>(sumVector)

        static void
            *p[] =
            {
                instantiate(int),
                instantiate(double),
                instantiate(unsigned)
            };

        #undef instantiate

This model can be used over and over again: the `instantiate()` macro is never defined outside of the sourcefile itself, while instantiations can be generated on the fly by new `instantiate()` macro calls.

### 16.1.3: Argument deduction

The compiler determines what type of template function is needed by examining the types and values of the arguments of template functions. This process is called template argument deduction. With template argument deduction, the type of the return value of the template function is not considered.

For example, consider once again the function

T sumVector(const T (&array)[size])
given in section 16.1.1:

            template <class T, unsigned size>
            T sumVector(const T (&array)[size])
            {
                T
                    sum(0);
                for (int idx = 0; idx < size; ++idx)
                    sum += array[idx];
                return (sum);
            }

In this function the template non-type parameter `size` is determined from the size of the array that is used with the call. Since the size of an array is known to the compiler, the compiler can determine the `size` parameter by looking up the size of the array that is used as argument to the function `sumVector()`. If the size is not known, e.g., when a pointer to an array element is passed to the function, the compilation will not succeed. Therefore, in the following example, the first call of the function `sumVector()` will succeed, as `iArray` is an array; the second one will fail, as `iPtr` is a pointer, pointing to an array of (in principle) unknown size:

        #include "sumvector.t"  // define the template function

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

It is not necessary for a template function's argument to match exactly the type of the template function's corresponding parameter. Three kinds of conversions are allowed here:

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

These three conversions are now discussed and illustrated.

16.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. Simply stated, an lvalue is an expression that may be used to the left of an assignment operator. It is an object whose address may be determined, and which contains a value. In contrast, an rvalue is an expression that may be used to the right of an assignment operator: it represents a value that does not have an address and that cannot be modified.
  In a statement like
  `x = y;`
  (in which `x` and `y` are variables of comparable types), the value of `y` is determined. Then this value is assigned to `x`. Determining the value of `y` is called an lvalue-to-rvalue conversion. 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 pointervariable. This if 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.

In the first sumVector() function (section 16.1.1) the first parameter is defined as a `T *`. Here an array-to-pointer conversion is allowed, as it is an lvalue transformation, which is one of the three allowed conversions. Therefore, the name of an array may be passed to this function as its first argument.

16.1.3.2: Qualification conversions

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

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

In the above definition, a plain array or pointer to some type can be used in combination with this function `sumVector()`. E.g., an argument `iArray` could be defined as `int iArray[5]`. However, no damage is inflicted on the elements of `iArray` by the function `sumVector()`: it explicitly states so, by defining `array` as a `T const *`. Qualification conversions are therefore allowed in the process of template argument deduction.

16.1.3.3: Conversion to a base class

In section 16.2 template classes are formally introduced. However, they were already used earlier: abstract containers (covered in chapter 7) are actually defined as template classes. Like `normal' classes, template classes can participate in the construction of class hierarchies. In section 16.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 <class T>
        T sumVector(queue<T> &queue)
        {
            T
                sum(0);

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

All kinds of `queue` objects can be passed to the above function. However, it is also possible to pass `Pipe` objects to the function `sumVector()`: By instantiating the `Pipe` object, its base class, which is the template class `queue`, is also instantiated. Now:

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

Consequently, the definition ``Pipe<int> pi;`' implies the instantiation of the base class `queue<int>`, which is an allowed type for the first parameter of `sumVector()`. Therefore, `pi` may be passed as argument to `sumVector()`.

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

16.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 16.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(vector<Type> &v1, vector<Type> &v2)`
  the arguments used with `twoVectors()` must have equal types. E.g.,

          vector<int>
              v1,
              v2;
          ...
          twoVectors(v1, v2);

### 16.1.4: Explicit arguments

Consider once again the function main() is section 16.1.2. Here the function `sumVector()` was called as follows:

        #include "sumvector.h"

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

            cout << sumVector(x, 2) << endl
                << sumVector(y, 2) << endl;
            ...
        }

In both cases the final argument of the function is of type `int`, but in the template's definition, the second parameter is an unsigned. The conversion `unsigned -> int` is not one of the allowed conversions lvalue transformations, qualification conversions or `conversion to a base class`. Why doesn't the compiler complain in this case? In cases where the type of the argument is fixed, standard type conversions are allowed, and they are applied automatically by the compiler. The types of arguments may also be made explicit by providing casts. In those cases there is no need for the compiler to deduce the types of the arguments.

In section 16.1.2, a 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 16.1.2 using explicit template argument types:

        #include "template.h"

        unsigned fun(unsigned (*f)(unsigned *p, unsigned n));
        double fun(double (*f)(double *p, unsigned n));

        int main()
        {
            cout << fun(sumVector<double, unsigned>)
                << endl;
            return (0);
        }

The explicit argument type list should follow the types mentioned in the `template<...>` line preceding the template's function definition. The type `class T` in the template line of the function `sumVector()` is made explicit as type `double`, and not as, e.g., a type `double *`, which was used in the `static_cast` in the example of section 16.1.2.

Explicit template arguments may be partially specified. Like the specification of arguments of functions for which default arguments are defined, trailing template arguments may be omitted from the list of explicit template argument types. When they are omitted, the types mentioned in the `template<>` line preceding the template's function definition are used. So, in the above example the explicit argument type `unsigned` may be omitted safely, as the type of the second template's argument is already known from the argument type list. The function `main()` can therefore also be written as:

        int main()
        {
            cout << fun(sumVector<double>)
                << endl;
            return (0);
        }

Explicit template arguments can also be used to simplify the definition of the instantiate macro in section 16.1.2. Using an explicit template argument, the code gets so simple that the macro itself can be completely avoided. Here is the revised code of the example:

        template<class T>
        T sumVector(T *tp, unsigned n)
        {
            return (*tp);
        }
        static void
            *p[] =
            {
                &sumVector<int>,
                &sumVector<double>,
                &sumVector<unsigned>
            };

Note that the initial `&`-tokens indicating the addresses of the `sumVector()` functions are required when the addresses of the functions are assigned to pointer variables.

16.1.4.1: Template explicit instantiation declarations

The explicit instantiations that were defined in the previous section were all embedded in the array of void pointers `p[]`, which array was used to have a target for the addresses of the instantiated function.

This is, admittedly not too elegant, but it works well. However, it is also possible to declare a template providing explicit types of the template's arguments with the purpose of instantiating the corresponding template functions. An explicit instantiation declaration starts with the keyword `template`, to be followed by an explicit template function declaration. Although this is a declaration, it is considered by the compiler as a request to instantiate that particular variant of the function.

Using explicit instantiation declarations the final example of the previous section can be rewritten as follows:

        template<class T>
        T sumVector(T *tp, unsigned n)
        {
            return (*tp);
        }

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

As can be seen from this example, explicit instantiation declarations are mere function declarations, e.g.,
`int sumVector(int *, unsigned);`
embellished with the `template` keyword and an explicit template argument list, e.g., `<int>`.

### 16.1.5: Template explicit specialization

Although the function `sumVector()` we've seen in the previous sections is well suited for arrays of elements of the basic types (like `int, double`, etc.), the template implementation is of course not appropriate in cases where the `+=` operator is not defined or the `sum(0)` initialization makes no sense. In these cases an `template explicit specialization` may be provided,

The template's implementation of the `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 <string>
        #include <numeric>

        template <> char *sumVector<char *>(char **argv, unsigned argc)
        {
            string
                s = accumulate(argv, argv + argc, string());

            return (strcpy (new char[s.size() + 1], s.c_str()));
        }

A template explicit specialization starts with the keyword `template`, followed by an empty set of pointed brackets. This is followed by the head of the function, which follows the same syntax as a template explicit instantiation declaration, albeit that the trailing `;` of the declaration is replaced by the actual function body of the specialization implementation.

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

`template <> char *sumVector<char *>(char **, unsigned);`
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.

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:

`template <> char *sumVector(char **, unsigned);`

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. On the other hand, a template explicit specialization must obey the form of the general template function of which it is a specialization. If the template function head is

`T sumVector(T *tp, unsigned n)`
then the template explicit specialization cannot be
`template<> char *sumVector<char const *>(char const **, unsigned)`
as this results in different interpretations of the formal type `T` of the template: `char *` or `char const *`.

### 16.1.6: Overloading template functions

Template functions may be overloaded. The function `sumVector()` defined earlier (e.g. in section 16.1.1) may be overloaded to accept, e.g., variables of type `vector`:

        #include <vector>
        #include <numeric>

        template <class T>
        T sumVector(vector<T> &array)
        {
            return (accumulate(array.begin(), array.end(), T(0)));
        }

Such a template function can be used by passing it an argument of type `vector`, as in:

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

Apart from defining overloaded versions, the overloaded versions can of course also be declared. E.g.,

        template <class T>
        T sumVector(vector<T> &array);

Using templates may result in ambiguities which overloading can't solve. Consider the following template function definition:

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

Passing `differentSigns()` an `int` and an `unsigned` is an error, as the two types are different, whereas the template definition calls for identical types. Overloading doesn't really help here: defining a template having the following prototype is ok with the `int` and `unsigned`, but now two instantiations are possible with identical types.

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

This situation can be disambiguated by using template explicit arguments, e.g., `differentSigns<int, int>(12, 30)`. But template explicit arguments could be used anyway with the second overloaded version of the function: the first definition is superfluous and can be omitted.

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, however, 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 <class T>
        T sumVector(T, unsigned);

        extern int
            iArray[];

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

The above example doesn't produce an ambiguity, even though the original sumVector() given in section 16.1.1 and the version declared here could both be used for the call. Why is there no ambiguity here?

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.,

`sumVector<int *>(iArray, 12);`

### 16.1.7: Selecting an overloaded (template) function

The following steps determine the actual function that is called, given a set of (template or non-template) overloaded functions:

- 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 16.1.3. For example, assuming all of the following declarations were provided, an instantiation of

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

  and the functions

          bool differentSigns(double i, double j);
          bool differentSigns(bool i, bool j);
          bool differentSigns(int (&i)[2]);

  will all be elements of the set of possible functions in the following code fragment, as all of the four functions have the same name of the function that is called:

          void fun(int arg1, double arg2)
          {
              differentSigns(arg1, arg2);
          }

- 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 abouve 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.

If the template would have been declared as

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

then no template function would have been instantiated here. This is ok, as the ordinary function `differentSigns(double, double)` will now be used. An error occurs only if no instantiation of the template function can be generated and if no acceptable ordinary function is available. If such a case, the compiler will generate an error like
`no matching function for call to `differentSigns (int &, double &)`

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 <class T, class U>
        bool differentSigns(T t, U u);

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

then the template explicitly specialized function will be selected without generating an extra instantiation from the general template definition.

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.

### 16.1.8: Name resolution within template functions

Consider once more our function `sumVector()` of section 16.1.1, but now it's given a somewhat different implementation:

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

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

            return (sum);
        }

In this template definition, `cout`'s `operator<<` is called to display a `char const *` string, an `unsigned`, and a `T`-value. The first `cout` statement displays the string and the `unsigned` value, no matter what happens in the template. These types do not depend on a template parameter. If a type does not depend on a template parameter, the necesary declarations for compiling the statement must be available when the definition of the template is given. In the above template definition this implies that
`ostream &ostream::operator<<(unsigned)`
and
`ostream &ostream::operator<<(char const *)`
must be known to the compiler when the definition of the template is given. On the other hand,
`cout << ... << sum << endl`
cannot be compiled by the time the template's definition is given, as the type of the variable `sum` depends on a template parameter. The statement can therefore be checked for semantical correctness (i.e., the question whether `sum` can be inserted into `cout`) can only be answered at the point where the template function is instantiated.

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 instantiation of the template.

## 16.2: Template classes

Like templates for functions, templates can be constructed for complete classes. A template class can be considered when the class should be available for different types of data. Template classes are frequently used in C++: chapter 7 covers general data structures like `vector, stack` and `queue`, which are available as template classes. The algorithms and the data on which the algorithms operate are completely separated from each other. To use a particular data structure on a particular data type, only the data type needs to be specified at the definition or declaration of the template class object, e.g., `stack<int> istack`.

In the upcoming sections the construction of such a template class is discussed. In a sense, template classes compete with object oriented programming (cf. chapter 15), 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 memberfunctions 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.

### 16.2.1: Template class definitions

The construction and use of template classes will be covered in the coming sections, where a basic template class `bvector` (basic vector will be constructed.

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 `bvector`, 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 `bvector`, possibly of a given size, as well as a copy constructor, since memory will be allocated by the object to store the values of type `Type`.
- A destructor.
- An overloaded `operator=` operator.
- A `operator[]` to retrieve and reassign the elements giving 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 `sort()` member to sort the elements of type `Type`.
- A member `push_back()` to add a new element at the end of the vector.

Should the set of members include members that can be used with `const` objects? In practical situations it probably should, but for now these members are not included in the interface: I've left them for the reader to implement.

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`, to be followed by a non-empty list of template type and/or non-type parameters, surrounded by angular brackets. This template announcement is then followed by the class interface, in which the template parameters may be used to represent types and constants. Here is initial class interface of the `bvector` template class, already showing member functions `construct` and `destroy` which are 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 defined simply as a pointer to an element of the vector. The reverse-iterator will be added later. Note that the `bvector` template class contains only a template type parameter, and no non-type parameter.

        template <class Type>
        class bvector
        {
            public:
                typedef reverse_iter<Type> reverse_iterator;

                bvector();
                bvector(unsigned n);
                bvector(bvector<Type> const &other);
                ~bvector();
                bvector<Type> const &operator=(bvector<Type> const &other);
                Type &operator[](int index);
                bvector<Type> &sort();
                void push_back(Type const &value);
                Type *begin();
                Type *end();
                reverse_iterator rbegin();
                reverse_iterator rend();
                unsigned size();
            private:
                void construct(bvector<Type> const &other);
                Type
                    *start,
                    *finish,
                    *end_of_storage;
        };

Within the class interface definition the abstract type `Type` can be used as a normal typename. However, note the `bvector<Type>` constructions appearing in the interface: there is no plain `bvector`, as the `bvector` will be bound to a type `Type`, to be specified later on in the program using a `bvector`.

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 `bvector` the template announcement could have been altered to specify `int` as the default type:

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

Template class declarations are constructed by removing the template interface definition (the part between the curly braces), replacing the definition by a semicolon:

        template <class Type>
        class bvector;

here too, default types may be specified.

In section 16.3 the full implementation of the `bvector` template class is given.

### 16.2.2: Template class instantiations

template classes are instantiated when an object of the template class is defined. When a template class object is defined (or declared) the template parameters must be explicitly specified (note that the parameters having default arguments are also specified, albeit as defaults). The template arguments are never deducted, as with template functions. To define a `bvector` to store `ints`, the construction

        bvector<int>
            bvInt;

is used. For a `bvector` for `strings`

        bvector<string>
            bvString;

is used.

In combination with the keyword `extern` these variables are declared rather than defined. E.g.,

        extern bvector<int>
            bvInt;

A template (type) parameter can be used to designate a type within another template. In the following function the template function `manipulateVector()` is defined, using type parameter `T`. It receives, defines, and returns `bvector` references and objects:

        template <class T>
        bvector<T> &manipulateVector(bvector<T> &vector)
        {
            bvector<T>
                extra(vector);
            ...
            return (vector);
        }

A template class is not instantiated if a reference or pointer to the class template is used. In the above example, the `bvector<int> extra(...)` results in a template instantiation, but the parameter and the return value of the function `manipulateVector()`, being references, don't result in template instantiations. However, if a memberfunction of a template class is used with a pointer or reference to a template class object, then the class is instantiated. E.g., in the following code

        template <class T>
        void add(bvector<T> &vector, int value)
        {
            vector.push_back(value);
        }

the class `bvector<int>` will be instantiated.

### 16.2.3: Nontype parameters

Template nontype parameters must be constant expressions. I.e., the compiler must be able to evaluate their values. For example, the following class uses a template type parameter to define the type of the elements of a buffer, and a template nontype parameter to define the size of the buffer:

        template <class Type, unsigned size>
        class Buffer
        {
            ...
            Type
                buffer[size];
        };

The `size` parameter must be a constant value when a `Buffer` object is defined or declared. E.g.,

        Buffer<int, 20>
            buffer;

Note that

- Global variables have constant addresses, that can be used as arguments for nontype 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 nontype parameters.
- Lvalue transformations are allowed: if a pointer is defined as a nontype parameter, an arrayname 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 datatype may be used for a nontype parameter of a wider type (e.g., `short` when an `int` is called for, `long` when a `double` is called for).
- Integral conversions are allowed: if an `unsigned` parameter is specified, an `int` may be used.

### 16.2.4: Template class member functions

Normal design considerations should be followed when constructing template class member functions or template class constructors: template class type parameters should preferably be defined as `T const &`, rather than `T`, to prevent unnecessary copying of large `T` types. Template class constructors should use member initializers rather than member assignment within the body of the constructors, again to prevent double assignment of composed objects: once by the default constructor of the object, once by the assignment itself.

Template memberfunctions must be known to the compiler when the template is instantiated. The current egcs compiler does not allow precompiled template classes, therefore the memberfunctions of templates are inline functions. They can be defined inside the template interface or outside the template interface. Template memberfunctions are defined as the inline memberfunctions of any other class. However, for the memberfunctions 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.

In the bvector template class a memberfunction

`void push_back(T const &value);`
is declared. Its definition, outside of the template's interface, could be:

        template <class T>
        void bvector<T>::push_back(T const &t)
        {
            if (finish == end_of_storage)
            {
                end_of_storage <<= 1;
                T
                    *tmp = copy(start, finish, new T[max]);
                delete [] start;
                finish = tmp + (finish - start);
                finish = tmp;
            }
            *finish++ = t;
        }

Note the fact that the class type of `push_back` is the generic `bvector<T>` type. The abstract type `T` is also used to define the type of the variable `tmp`.

### 16.2.5: Template classes and friend declarations

Template classes may define other functions and classes as friends. There are three types of friend declarations that can appear within a template class:

- A nontemplate friend function or class. This is a well-known friend declaration.
- 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.

The following sections will discuss the three types of friend declarations in further detail.

16.2.5.1: Nontemplate 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. Friend classes and ordinary friend functions can be declared as friends, 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 <class T>
        class bvector
        {
            friend class AnotherFriend;     // declaration only is ok here
            friend void anotherMember();    // declaration is ok here
            friend Friend::member();        // Friend interface class required.
            ...
        };

Such ordinary friends can be used, e.g., to access the static private members of the `bvector` class or they can themselves define `bvector` objects and access all members of these objects.

16.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 <class T>
        class Friend;                   // declare a template class

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

        template <class T>
        class AnotherFriend
        {
            public:
                void member();
        }

        template <class T>
        class bvector
        {
            friend class Friend<T>;                     // 1
            friend void function<T>(Friend<T> t);       // 2
            friend void AnotherFriend<T>::member();     // 3
        };

Above, three friend declarations are defined:

- At `1`, the class `Friend` is declared a friend of `bvector` if it is instantiated for the same type `T` as `bvector` itself.
- At `2`, the function `funciont` is declared a friend of `bvector` if it is instantiated for the same type `T` as `bvector` 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 `bvector`'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 `bvector` for its argument.
- At `3`, a specific memberfunction of the class `AnotherFriend`, instantiated for type `T` is declared as a friend of the class `bvector`.

Assume we would like to be able to insert the elements of a `bvector` into an `ostream` object, using the insertion operator `<<`. For such a situation the `copy()` generic algorithm in combination with the `ostream_iterator` comes in handy. However, the latter iterator is a template function, depending on type `T`. If we can assume that `start` and `finish` are iterators of `bvector`, then the implementation is quickly realized by defining `operator<<` as a template function, and by declaring this operator as a friend of the class `bvector()`:

        #include <iterator>
        #include <algorithm>
        #include <iostream>

        template<class T>
        class bvector
        {
            friend ostream &operator<< <T> (ostream &str,
                                                bvector<T> const &vector);
            private:
                Iterator
                    *start,
                    *finish;
        };

        template <class T>
        ostream &operator<<(ostream &str, bvector<T> const &vector)
        {
            ostream_iterator<T *>
                out(str, " ");
            return (copy(bvector.start, bvector.finish, out));
        }

16.2.5.3: Unbound friends

By prepending the `friend` declarations by the `template<typelist>` phrase, the 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 <class Type>
        class bvector
        {
            template <class T>
            friend void function(); // unbound friend function

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

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

            ...
        };

Unbound friends may not yet be supported by your compiler, though. E.g., earlier versions of the `egcs` compiler )) used to complain with a message like
`invalid member template declaration`
However, current versions of the `egcs` compiler do accept unbound friends.

### 16.2.6: Template classes and static data

When static members are defined in a template class, these static members are instantiated for every different instantiation of the template class. As they are static members, there will be only one member when multiple objects of the same template type(s) are defined. For example, in a class like:

        template <class Type>
        class TheClass
        {
            ...
            private:
                static int
                    objectCounter;
        };

There will be one `TheClass<Type>::objectCounter` for each different `Type`. However, the following will result in just one static variable, which is shared among the different objects:

        TheClass<int>
            theClassOne,
            theClassTwo;

Remeber that static members are only declared in their classes. They must be defined separately. With static members of template classes this is not different. But, comparable to the implementations of static functions, the definitions of static members are usually provided in the same file as the template class interface itself. The definition of the static member `objectCounter` is therefore:

        template <class Type>
        class TheClass
        {
            ...
            private:
                static int
                    objectCounter;
        };

        template <class Type>
        int
            TheClass<Type>::objectCounter = 0;

In the above case `objectCounter` is an `int`, and thus independent of the template type parameter `Type`. In a list-like construction, where a pointer to objects of the class itself is required, the template type parameter `Type` does enter the definition of the static variable, as is shown in the following example:

        template <class Type>
        class TheClass
        {
            ...
            private:
                static TheClass
                    *objectPtr;
        };

        template <class Type>
        TheClass<Type>
            *TheClass<Type>::objectPtr = 0;

Note here that the definition can be read, as usual, from the variable name back to the beginning of the definition: `objectPtr` of the class `TheClass<Type>` is a pointer to an object of `TheClass<Type>`.

### 16.2.7: Derived Template Classes

Template classes can be used in class derivation as well. Consider the following base class:

        template<class T>
        class Base
        {
            public:
                Base(T const &t)
                :
                    t(t)
                {}
                // and other members
            private:
                T const &t;
        };

The above class is a template class, which can be used as a base class for the following template class `Derived`:

        template<class T>
        class Derived: public Base<T>
        {
            public:
                Derived(T const &t)
                :
                    Base(t)
                {}
                // and other members
        };

Other combinations are possible too: By specifying the template type parameters of the base class at the point where the base class is introduced as the base class of a derived class, the derived class becomes an ordinary (non-template) class:

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

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

### 16.2.8: Nesting and template classes

When a class is nested within a template class, it automatically becomes a template class itself. The nested class may use the template parameters of the surrounding class, as shown in the following small program:

        #include <vector>

        template<class Type>
        class TheVector
        {
            public:
                class Enumeration
                {
                    public:
                        Enumeration(vector<Type> const &vector)
                        :
                            vp(&vector),
                            idx(0)
                        {
                        }
                        Type const &nextElement()   // uses 'Type'
                        {
                            if (idx == vp->size())
                                throw NoSuchElementException(index);
                            return ((*vp)[idx++]);
                        }
                        bool hasMoreElements()
                        {
                            return (idx < vp->size());
                        }
                    private:
                        vector<Type>
                            const *vp;
                        unsigned
                            idx;
                };

                TheVector<Type>::Enumeration getEnumeration()
                {
                    return (Enumeration(vector));
                }
            private:
                vector<Type>
                    vector;
        };

        int main()
        {
            TheVector<int>
                theVector;

            TheVector<int>::Enumeration
                en = theVector.getEnumeration();

            cout << (en.hasMoreElements() ? "has more elements" :
                                            "no more elements") << endl;

            return (0);
        }

In the above program the class `Enumeration` is a nested class, that uses the template parameter `Type` of its surrounding class. The nested class `Enumeration` defines an object that returns the subsequent elements of the vector of the surrounding class, and allows a simple query about the existence of another element.

(Parts of) the nested class are instantiated once used. E.g., in the above example, the function `nextElent()` is not used. This is why the example can be compiled to a working program, as the `NoSuchElementException()` exception was never defined!

Enumerations and typedefs can be defined nested 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 first exposed to the C-array types. The following construction automatically provides a valid `last` and `nElements` definition:

        template<class Type, int size>
        class Buffer
        {
            public:
                enum Limits
                {
                    last = size - 1,
                    nElements
                };
                typedef Type elementType;

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

This small example defines `Buffer<Type, size>::elementType, Buffer<Type, size>::last` and `Buffer<Type, size>::nElements` (as values), as well as `Buffer<Type, size>::Limits` and `Buffer<Type, size>::elementType>` (as typenames).

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

`Buffer<int, 80>::elementType`
is a synonym of `int`.

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

### 16.2.9: Template members

It is possible to define a template class or a template function within another class (which itself may or may not be a template class). Such a template function or template class is called a member template. It is defined as any other ordinary template class, including the `template <class ...>` header. E.g.,

        template <class T>
        class Outer
        {
            public:
                ...
                template <class T2>     // template class
                class Inner
                {
                    public:
                        T
                            tVariable;
                        T2
                            t2Variable;
                };
                template <class Type>
                Type process(Type const &p1, Type const &p2)
                {
                    Type
                        result;
                    ...
                    return (result);
                }
                ...
        };

The special characteristic of a member template is that it can use its own and its surrounding class' template parameters, as illustrated by the definition of `tVariable` in `Inner`.

Normall 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 function memberfunction `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 template member function allows the processing of any other type by an object of the class `Outer`, which becomes important if the other type can be converted to the type that's used by the outer template class.

Any function can be defined as a template function, not just an ordinary member function. A constructor can be defined as a template as well:

        template <class T>
        class Outer
        {
            public:
                template <class T2>     // template class
                Outer(T2 const &initialValue)
                {
                    ...
                }
                ...
        };

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

        Outer<int>
            t(12.5);    // uses 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 <class T>
        class Outer
        {
            public:
                template <class T2>     // template class
                class Inner;

                template <class Type>
                Type process(Type const &p1, Type const &p2);
        };

        template <class T> template <class Type>    // template class member
        class Outer<T>::Inner<Type>
        {
            public:
                T
                    tVariable;
                T2
                    t2Variable;
        };

        template <class T> template <class Type>    // template function member
        Type Outer<T>::process(Type const &p1, Type const &p2)
        {
            Type
                result;
            ...
            return (result);
        }

Not all compilers fully support member templates yet. E.g., the `egcs` compiler 1.0.3 does not support the member template classes, but it does support the member template functions.

### 16.2.10: Template class specializations

Template class specializations are used in cases where template member functions cannot be used with a (class) type for which the template is instantiated. In those cases the template's member function(s) can be explicitly constructed to suit the needs of the particular type for which the template is instantiated.

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

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

In the example a plain member function is used to insert the current object into an ostream. The implementation of the `insert()` function shows that it uses the `operator<<`, as defined for the type that was used when the template class was instantiated. E.g., the following little program instantiates the class `Inserter<int>`:

        int main()
        {
            Inserter<int>
                ins(5);

            ins.insert(cout) << endl;
            return (0);
        }

Now suppose we have a `class Person` having, among other members, the following memberfunction:

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

This class cannot be used to instantiate `Inserter`, as it does not have a `operator<<()` function, which is used by the function `Inserter<Type>::insert()`. Attempts to instantiate `Inserter<Person>` will result in a compilation error. For example, consider the following `main()` function:

        int main()
        {
            Person
                person;
            Inserter<Person>
                p2(person);

            p2.insert(cout) << endl;
        }

If this function is compiled, the compiler will complain about the missing function `ostream & << const Person &`, which was indeed not available. However, the function `ostream &Person::insert(ostream &ostr)` is available, and it serves the same purpose as the required function `ostream & Inserter<Person>::insert(ostream &)`.

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 wordt `template`, then two angular brackets (`<>`), which is then followed by the function definition for the instantiation of the template class for the particular template parameter(s). So, with the above function this yields the following function definition:

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

Here we explicitly define a function `insert` of the class `Inserter<Person>`, which calls the appropriate function that lives in the `Person` class.

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 sourcefile. 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<>
        ostream  &Inserter<Person>::insert(ostream &os) const;

It is even possible to specialize a complete template class. For the above class `Inserter` which would boil down to the following for the class `double`:

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

The explicit template class specialization is obtained by replacing all references to the template's class name `Inserter` by the class name and the type for which the specialization holds true: `Inserter<double>`, and by replacing occurrences of the template's type parameter by the actual type for which the specialization was constructed. The complete template class specialization interface must be given after the original template class has been defined. The definition of its members are, analogously to the `Inserter<Person>::insert()` function above, given in separate source files. However, in the case of a complete template class specialization, the definitions of its members should not be preceded by the `template<>` prefix. E.g.,

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

### 16.2.11: Template class partial specializations

In cases where a template has more than one parameter, a partial specialization rather than a full specialization might be appropriate. With a `partial` specialization, a subset of the parameters of the original template can be redefined.

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()
                {
                    // use 'columns' and 'rows'
                }
                ...
        };

Now, assume that an image having 320 columns deserves special attention, as those pictures require, e.g., a special smoothing algorithm. From the general template given above we can now construct a partially specialized template, which only has a `columns` parameter. Such a template is like an ordinary template parameter, in which only the `rows` remain as a template parameter. At the definition of the class name the specialization is made explicit by mentioning a specialization parameter list:

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

With the above partially specialized template definition the 320 columns are explicitly mentioned at the class interface, while the `rows` remain variable. Now, if an image is defined as

        Image<320, 240>
            image;

two instantiations could be used: the fully general template is a candidate as well as the partially specialized template. Since the partially specialized template is more specialized than the fully general template, the `Image<320, rows>` template will be used. This is a general rule: a more specialized template instantiation is chosen in favor of a more general one whereever possible.

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

Even when both specializations are provided there will (generally) be no problem. The following three images will result in, respectively, an instantiation of the general template, of the template that has been specialized for 320 columns, and of the template that has been specialized for the 200 rows:

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

With the `generic` image, no specialized template is available, so the general template is used. With the `columnSpecialization` image, 320 columns were specified. For that number of columns a specialized template is available, so it's used. With the `rowSpecialization` image, 200 rows were specified. For that number of rows a specialized template is available, so that specialized template is used with `rowSpecialization`.

One might wonder what happens if we want to construct a

        Image<320, 200>
            superSpecialized;

image. Is this a specialization of the columns or of the rows? The answer is: neither. It's an ambiguity, precisely because both the columns and the rows could be used with a (differently) specialized template. If such an image is required, yet another specialized template is needed, albeit that that one isn't a partially specialized template anymore. Instead, it specializes all its parameters with the class interface:

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

The above super specialization of the `Image` template will be used with the image having 320 columns and 200 rows.

### 16.2.12: Name resolution within template classes

In section 16.1.8 the name resolution process with template functions was discussed. As is the case with template functions, name resolution in template classes also proceeds in two steps. Names that do not depend on template parameters are resolved when the template is defined. E.g., if a member function in a template class uses a `qsort()` function, then `qsort()` does not depend on a template parameter. Consequently, `qsort()` must be known when the compiler sees the template definition, e.g., by including the file `stdlib.h`.

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

        Type returnValue();

then we have a different situation. At the point where template objects are defined or declared, at the point where template member functions are used, and at the point where static data members of template classes are defined or declared, it must be able to resolve the template type parameters. So, if the following template class is defined:

        template <class Type>
        class Resolver
        {
            public:
                Resolver();
                Type result();
            private:
                Type
                    datum;
                static int
                    value;
        };

Then `string` must be known before each of the following examples:

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

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

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

## 16.3: An example: the implementation of the bvector template

In this section the implementation of the basic vector `bvector`, introduced in section 16.2.1, will be completed.

The implementation of the `bvector` is generally straightforward: the basic constructors initialize the data members of the `bvector`, using an auxiliary private function `init()`:

        bvector()
        {
            init(0);
        };
        bvector(unsigned n)
        {
            init(n);
        }
        void init(unsigned n)
        {
            if (n)
            {
                start = new Type[n];
                finish = start + n;
                end_of_storage = start + n;
            }
            else
            {
                start = 0;
                finish = 0;
                end_of_storage = 0;
            }
        }

The copy-constructor, overloaded assignment operator and destructor are also constructed according to a general recipe. The destructor is simple: it only has to call the operator `delete` for `start`, using the `[]` notation to make sure that class objects stored in the `bvector` are deleted too. Therefore, no `destroy()` function was considered necessary in this class. Note that storing pointers in the `bvector` is dangerous, as it is with the official `STL vector` type: the data pointed to by pointer elements of `bvector` is not deleted when the `bvector` itself is destroyed.

Here are the destructor, the copy constructor, the overloaded assignment operator and the private `construct()` function:

        ~bvector()
        {
            delete [] start;
        }

        bvector(bvector<Type> const &other)
        {
            construct(other);
        }

        bvector<Type> const &operator=(bvector<Type> const &other)
        {
            if (this != &other)
            {
                delete [] start;
                construct(other);
            }
            return (*this);
        }

        void construct(bvector<Type> const &other)
        {
            init(other.finish - other.start);
            copy(other.start, other.finish, start);
        }

The `operator[]` first checks the validity of the `index` that's passed to the function. If out of bounds a simple exception is thrown. Otherwise the function is completely standard. Note that the current implementation of `bvector` does not allow for `bvector<Type> const` objects to use the `operator[]`. Here is the implementation of the `operator[]` function:

        Type &operator[](unsigned index) throw(char const *)
        {
            if (index > (finish - start))
                throw "bvector array index out of bounds";
            return (start[index]);
        }

The `sort()` function uses the available `sort()` generic algorithm. The `::sort()` notation is required to prevent confusion: without the scope resolution operator the compiler complains about us having specified the wrong arguments for the function `sort()`. Here is the implementation of `sort()`:

        bvector<Type> &sort()
        {
            ::sort(start, finish);
            return (*this);
        }

The push_back() function either initializes the size of the `bvector` to one element, or doubles the number of elements in the vector when there's no more room to store new elements. When the number of elements must be doubled, an auxiliary `bvector` object is created, into which the elements of the current `bvector` object are copied, using the `copy()` generic algorithm. Next, the memory pointed to by the the current `bvector` object is deleted, and its pointers are reassigned to point to the memory occupied by the auxiliary `bvector` object. The `start` pointer of the auxiliary `bvector` object is then set to 0, to prevent the destruction of its memory, to which the current `bvector` points as well. Finally the new value is stored in the vector. Here is the implementation:

        void push_back(Type const &value)
        {
            if (!finish)
            {
                init(1);
                finish = start;
            }
            else if (finish == end_of_storage)
            {
                bvector<Type>
                    enlarged((end_of_storage - start) << 1);
                copy(start, finish, enlarged.start);
                delete [] start;
                finish = enlarged.start + (finish - start);
                start = enlarged.start;
                end_of_storage = enlarged.end_of_storage;
                enlarged.start = 0;
            }
            *finish++ = value;
        }

Two sets of iterators are available: the `begin()` and `end()` functions return `iterators`, the `rbegin()` and `rend()` functions return `reverse_iterators`. `Iterators` and `reverse_iterators` are defined as `typedefs` within the template class. These typedefs and the functions returning the (reverse) iterators are given below:

        typedef Type *iterator;
        typedef reverse_iter<Type> reverse_iterator;

        iterator begin()
        {
            return (start);
        }
        iterator end()
        {
            return (finish);
        }
        reverse_iterator rbegin()
        {
            return (reverse_iterator(finish));
        }
        reverse_iterator rend()
        {
            return (reverse_iterator(start));
        }

The `iterator` is simply a type definition for a pointer to a `Type`. The `reverse_iterator` is more complex, as its type definition depends on a `reverse_iter<iterator>` type, defining the actual reverse iterator. The `reverse_iter<iterator>` itself is a template class, that is discussed in the next section.

### 16.3.1: The reverse_iter template class

The template class `reverse_iter` uses a template class parameter `Type` representing the data type for which a reverse iterator must be constructed. Since the type of the data to which the reverse iterator points is known, a reference and a pointer to the data type can easily be constructed.

Given the data type `Type` to which a reverse iterator points, the reverse iterator must support the following operations:

- It must be possible to construct a reverse iterator from an iterator.
- A dereference operator `Type &operator*()`, returning the data item to which the reverse iterator points.
- A pointer operator `Type *operator->()` returning the address of the data element, to be used when the data element is an object having members.
- A prefix and postfix increment operator returning a reverse iterator pointing to the previous data element.

As the reverse iterator returns a pointer to the previous element, it is possible to let the `rbegin()` iterator return a pointer to the last element, and to let `rend()` return a pointer to the address before the first data element. But it is also possible to let `rbegin()` return `end()`, and to let `rend()` return `begin()`. That way the pointers are used the same way, both for iterators and reverse iterators. This latter approach, which is used by the standard template library's implementation of the reverse iterators, requires the dereference operator to return the data element before the one to which the reverse iterator actually points. The implementation of the `operator*()` is, therefore:

        Type &operator*() const
        {
            Type
                *tmp = current;
            return (*--tmp);
        }

The increment operators return reverse iterators. The prefix increment operator reduces the `current` pointer, and returns a reference to the current reverse iterator by returning `*this`:

        reverse_iter<Type>& operator++()
        {
            --current;
            return (*this);
        }

The postfix increment operator returns a reverse iterator object which is a copy of the current reverse iterator, whose pointer `current` is reduced by applying the postfix decrement operator on the `current` pointer:

        reverse_iter<Type> operator++(int)
        {
            reverse_iter<Type>
                tmp(current--);
            return (tmp);
        }

Of course, the `operator+(int step)` and the `operator--()` could be defined as well. These definitions are left as an exercise for the reader.

### 16.3.2: The final implementation

Below is the implementation of the template class `bvector` and its auxiliary template class `reverse_iter`:

        #include <algorithm>

        template <class Type>
        class reverse_iter
        {
            public:
                explicit reverse_iter(Type *x)
                :
                    current(x)
                {}
                Type &operator*() const
                {
                    Type
                        *tmp = current;
                    return (*--tmp);
                }
                Type *operator->() const
                {
                    return &(operator*());
                }
                reverse_iter<Type>& operator++()
                {
                    --current;
                    return (*this);
                }
                reverse_iter<Type> operator++(int)
                {
                    reverse_iter<Type>
                        tmp(current--);
                    return (tmp);
                }
                bool operator!=(reverse_iter<Type> const &other)
                {
                    return (current != other.current);
                }
            private:
                Type
                    *current;
        };

        template <class Type>
        class bvector
        {
            typedef Type *iterator;
            typedef reverse_iter<Type> reverse_iterator;

            public:
                bvector()
                {
                    init(0);
                };
                bvector(unsigned n)
                {
                    init(n);
                }
                bvector(bvector<Type> const &other)
                {
                    construct(other);
                }
                ~bvector()
                {
                    delete [] start;
                }
                bvector<Type> const &operator=(bvector<Type> const &other)
                {
                    if (this != &other)
                    {
                        delete [] start;
                        construct(other);
                    }
                    return (*this);
                }
                Type &operator[](unsigned index) throw(char const *)
                {
                    if (index >= (finish - start))
                        throw "bvector array index out of bounds";
                    return (start[index]);
                }
                bvector<Type> &sort()
                {
                    ::sort(start, finish);
                    return (*this);
                }
                void push_back(Type const &value)
                {
                    if (!finish)
                    {
                        init(1);
                        finish = start;
                    }
                    else if (finish == end_of_storage)
                    {
                        bvector<Type>
                            enlarged((end_of_storage - start) << 1);
                        copy(start, finish, enlarged.start);
                        delete [] start;
                        finish = enlarged.start + (finish - start);
                        start = enlarged.start;
                        end_of_storage = enlarged.end_of_storage;
                        enlarged.start = 0;
                    }
                    *finish++ = value;
                }
                iterator begin()
                {
                    return (start);
                }
                iterator end()
                {
                    return (finish);
                }
                reverse_iterator rbegin()
                {
                    return (reverse_iterator(finish));
                }
                reverse_iterator rend()
                {
                    return (reverse_iterator(start));
                }
                unsigned size()
                {
                    return (finish - start);
                }
            private:
                void init(unsigned n)
                {
                    if (n)
                    {
                        start = new Type[n];
                        finish = start + n;
                        end_of_storage = start + n;
                    }
                    else
                    {
                        start = 0;
                        finish = 0;
                        end_of_storage = 0;
                    }
                }
                void construct(bvector<Type> const &other)
                {
                    init(other.finish - other.start);
                    copy(other.start, other.finish, start);
                }

                Type
                    *start,
                    *finish,
                    *end_of_storage;
        };

A small `main()` function using the `bvector` data type is given next:

    #include <iostream>
    #include <string>
    #include "bvector.h"

    int main()
    {
        bvector<int>
            bv(5),
            b2;

        b2 = bv;

        bv[0] = 3;
        bv[1] = 33;
        bv[2] = 13;
        bv[3] = 6;
        bv[4] = 373;

        copy(bv.begin(), bv.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        bvector<int>::reverse_iterator
                rit  = bv.rbegin();

        while (rit != bv.rend())
            cout << *rit++ << ", ";
        cout << endl;

        bv.push_back(12);
        bv.push_back(5);

        copy(bv.begin(), bv.end(), ostream_iterator<int>(cout, " "));
        cout << endl;

        bv.sort();
        copy(bv.begin(), bv.end(), ostream_iterator<int>(cout, " "));
        cout << "bv has " << bv.size() << " elements\n";

        bvector<string>
            bstr;

        bstr.push_back("bravo");
        bstr.push_back("delta");
        bstr.push_back("foxtrot");
        bstr.push_back("echo");
        bstr.push_back("charley");
        bstr.push_back("alpha");

        bstr.sort();
        copy(bstr.begin(), bstr.end(), ostream_iterator<string>(cout, " "));
        cout << endl;
    }

- Next chapter
- Previous chapter
- Table of contents