Chapter 18: Template functions

Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.

Please state the document version you're referring to, as found in the title (in this document: 6.5.0) and please state chapter and paragraph name or number you're referring to.

All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.

C++ supports syntactical constructs allowing programmers to define and use completely general (or abstract) functions or classes, based on generic types and/or (possibly inferred) constant values. In the chapters on abstract containers (chapter 12) and the STL (chapter 17) we've already used these constructs, commonly known as the template mechanism.

The template mechanism allows us to specify classes and algorithms, fairly independently of the actual types for which the templates will eventually be used. Whenever the template is used, the compiler will generate code, tailored to the particular data type(s) used with the template. This code is generated compile-time from the template's definition. The piece of generated code is called an instantiation of the template.

In this chapter the syntactical peculiarities of templates will be covered. The notions of template type parameter, template non-type parameter, and template function will be introduced, and several examples of templates will be offered, both in this chapter and in chapter 20, providing concrete examples of C++. Template classes are covered in chapter 19.

Templates offered standard by the language already cover containers allowing us to construct both highly complex and standard data structures commonly used in computer science. Furthermore, the string (chapter 4) and stream (chapter 5) classes are commonly implemented using templates. So, templates play a central role in present-day C++, and should absolutely not be considered an esoteric feature of the language.

Templates should be approached somewhat similarly as generic algorithms: they're a way of life; a C++ software engineer should actively look for opportunities to use them. Initially, templates appear to be rather complex, and you might be tempted to turn your back on them. However, in time their strengths and benefits will be more and more appreciated. Eventually you'll be able to recognize opportunities for using templates. That's the time where your efforts should no longer focus on constructing concrete (i.e., non-template) functions or classes, but on constructing templates.

This chapter starts by introducing template functions. The emphasis is on the required syntax when defining such functions. This chapter lays the foundation upon which the next chapter, introducing template classes and offering several real-life examples, is built.

18.1: Defining template functions

A template function's definition is very similar to the definition of a normal function. A template function has a function head, a function body, a return type, possibly overloaded definitions, etc.. However, different from concrete functions, template functions always use one or more formal types: types for which almost any exising (class or primitive) type could be used. Let's start with a simple example. The following function add() expects two arguments, and returns their sum:
    Type add(Type const &lvalue, Type const &rvalue)
    {
        return lvalue + rvalue;
    }
Note how closely the above function's definition follows its description: it gets two arguments, and returns its sum. Now consider what would happen if we would have to define this function for, e.g., int values. We would have to define:
    int add(int const &lvalue, int const &rvalue)
    {
        return lvalue + rvalue;
    }
So far, so good. However, were we to add to doubles, we would have to overload this function so that its overloaded version accepts doubles:
    double add(double const &lvalue, double const &rvalue)
    {
        return lvalue + rvalue;
    }
There is no end to the number of overloaded versions we might be forced to construct: an overloaded version for std::string, for size_t, for .... In general, we would need an overloaded version for every type supporting operator+() and a copy constructor. All these overloaded versions of basically the same function are required because of the strongly typed nature of C++. Because of this, a truly generic function cannot be constructed without resorting to the template mechanism.

Fortunately, we've already seen the meat and bones of a template function. Our initial function add() actually is an implementation of such a function. However, it isn't a full template definition yet. If we would give the first add() function to the compiler, it would produce an error message like:

    error: `Type' was not declared in this scope
    error: parse error before `const'
And rightly so, as we failed to define Type. The error is prevented when we change add() into a full template definition. To do this, we look at the function's implementation and decide that Type is actually a formal typename. Comparing it to the alternate implementations, it will be clear that we could have changed Type into int to get the first implementation, and into double to get the second.

The full template definition allows for this formal character of the Type typename. Using the keyword template, we prefix one line to our initial definition, obtaining the following template function definition:

    template <typename Type>
    Type add(Type const &lvalue, Type const &rvalue)
    {
        return lvalue + rvalue;
    }
In this definition we distinguish: Normal scope rules and identifier visibility rules apply to template definitions. Formal typenames overrule, within the template definition's scope, any identifiers having identical names having wider scopes.

Look again at the function's parameters, as defined in its parameter list. By specifying Type const & rather than Type superfluous copying is prevented, at the same time allowing values of primitive types to be passed as arguments to the function. So, when add(3, 4) is called, int(4) will be assigned to Type const &rvalue. In general, function parameters should be defined as Type const & to prevent unnecessary copying. The compiler is smart enough to handle `references to references' in this case, which is something the language normally does not supports. For example, consider the following main() function (here and in the following simple examples assuming the template and required headers and namespace declarations have been provided):

    int main()
    {
        size_t const &uc = size_t(4);
        cout << add(uc, uc) << endl;
    }
Here uc is a reference to a constant size_t. It is passed as argument to add(), thereby initializing lvalue and rvalue as Type const & to size_t const & values, with the compiler interpreting Type as size_t. Alternatively, the parameters might have been specified using Type &, rather than Type const &. The disadvantage of this (non-const) specification being that temporary values cannot be passed to the function anymore. The following will fail to compile:
    int main()
    {
        cout << add(string("a"), string("b")) << endl;
    }
Here, a string const & cannot be used to initialize a string &. On the other hand, the following will compile, with the compiler deciding that Type should be considered a string const:
    int main()
    {
        string const &s = string("a");
        cout << add(s, s) << endl;
    }
What can we deduce from these examples? As a second example of a template function, consider the following function definition:
    template <typename Type, size_t Size>
    Type sum(Type const (&array)[Size])
    {
        Type t = Type();

        for (size_t idx = 0; idx < Size; idx++)
            t += array[idx];

        return t;
    }
This template definition introduces the following new concepts and features:

Like class definitions, template definitions should not contain using directives or declarations: the template might be used in a situation where such a directive overrides the programmer's intentions: ambiguities or other conflicts may result from the template's author and the programmer using different using directives (E.g, a cout variable defined in the std namespace and in the programmer's own namespace). Instead, within template definitions only fully qualified names, including all required namespace specifications should be used.

18.2: Argument deduction

In this section we'll concentrate on the process by which the compiler deduces the actual types of the template type parameters when a template function is called, a process called template parameter deduction. As we've already seen, the compiler is able to substitute a wide range of actual types for a single formal template type parameter. Even so, not every thinkable conversion is possible. In particular when a function has multiple parameters of the same template type parameter, the compiler is very restrictive in what argument types it will actually accept.

When the compiler deduces the actual types for template type parameters, it will only consider the types of the arguments. Neither local variables nor the function's return value is considered in this process. This is understandable: when a function is called, the compiler will only see the template function's arguments with certainty. At the point of the call it will definitely not see the types of the function's local variables, and the function's return value might not actually be used, or may be assigned to a variable of a subrange (or super-range) type of a deduced template type parameter. So, in the following example, the compiler won't ever be able to call fun(), as it has no way to deduce the actual type for the Type template type parameter.

    template <typename Type>
    Type fun()              // can never be called
    {
        return Type();
    }
In general, when a function has multiple parameters of identical template type parameters, the actual types must be exactly the same. So, whereas
        void binarg(double x, double y);
may be called using an int and a double, with the int argument implicitly being converted to a double, the corresponding template function cannot be called using an int and double argument: the compiler won't itself promote int to double and to decide next that Type should be double:
    template <typename Type>
    void binarg(Type const &p1, Type const &p2)
    {}

    int main()
    {
        binarg(4, 4.5); // ?? won't compile: different actual types
    }

What, then, are the transformations the compiler will apply when deducing the actual types of template type parameters? It will perform only three types of parameter type transformations (and a fourth one to function parameters of any fixed type (i.e., of a non-template function parameter type)). If it cannot deduce the actual types using these transformations, the template function will not be considered. These transformations are:

The first three types of transformations will now be discussed and illustrated.

18.2.1: Lvalue transformations

There are three types of lvalue transformations:

18.2.2: Qualification transformations

A qualification transformation adds const or volatile qualifications to pointers. This transformation is applied when the template function's parameter is explicitly defined using a const (or volatile) modifier, and the function's argument isn't a const or volatile entity. In that case, the transformation adds const or volatile, and subsequently deduces the template's type parameter. For example:
    template<typename Type>
    Type negate(Type const &value)
    {
        return -value;
    }
    int main()
    {
        int x = 5;
        x = negate(x);
    }
Here we see the template function's Type const &value parameter: a reference to a const Type. However, the argument isn't a const int, but an int that can be modified. Applying a qualification transformation, the compiler adds const to x's type, and so it matches int const x with Type const &value, deducing that Type must be int.

18.2.3: Transformation to a base class

Although the construction of template classes will only be constructed in chapter 19, template classes have already extensively been used earlier. For example, abstract containers (covered in chapter 12) are actually defined as template classes. Like concrete classes (i.e., non-template classes), template classes can participate in the construction of class hierarchies. In section 19.9 it is shown how a template class can be derived from another template class.

As template class derivation remains to be covered, the following discussion is necessarily somewhat abstract. Optionally, the reader may of course skip briefly to section 19.9, to read this section thereafter.

In this section it should now be assumed, for the sake of argument, that a template class Vector has somehow been derived from a std::vector. Furthermore, assume that the following template function has been constructed to sort a vector using some function object obj:

    template <typename Type, typename Object>
    void sortVector(std::vector<Type> vect, Object const &obj)
    {
        sort(vect.begin(), vect.end(), obj);
    }
To sort std::vector<string> objects case-insensitively, the class Caseless could be constructed as follows:
    class CaseLess
    {
        public:
            bool operator()(std::string const &before,
                            std::string const &after) const
            {
                return strcasecmp(before.c_str(), after.c_str()) < 0;
            }
    };
Now various vectors may be sorted, using sortVector():
    int main()
    {
        std::vector<string> vs;
        std::vector<int> vi;

        sortVector(vs, CaseLess());
        sortVector(vi, less<int>());
    }
Applying the transformation transformation to a base class instantiated from a class template, the template function sortVectors() may now also be used to sort Vector objects. For example:
    int main()
    {
        Vector<string> vs;      // note: not `std::vector'
        Vector<int> vi;

        sortVector(vs, CaseLess());
        sortVector(vi, less<int>());
    }
In this example, Vectors were passed as argument to sortVector(). Applying the transformation to a base class instantiated from a class template, the compiler will consider Vector to be a std::vector, and is thus able to deduce the template's type parameter. A std::string for the Vector vs, an int for Vector vi.

Please realize the purpose of the various template parameter type deduction transformations. They do not aim at matching function arguments to function parameters, but having matched arguments to parameters, the transformations may be applied to determine the actual types of the various template type parameters.

18.2.4: The template parameter deduction algorithm

The compiler uses the following algorithm to deduce the actual types of its template type parameters:

18.3: Declaring template functions

Up to now, we've only defined template functions. There are various consequences of including template function definitions in multiple source files, none of them serious, but worth knowing. Instead of including template definitions again and again in various source files, templates may also be declared. When templates are declared, the compiler will not have to process the template's definitions again and again, and no instantiations will be created on the basis of template declarations alone. Any actually required instantiation must, as holding true for declarations in general, be available elsewhere. Unlike the situation we encounter with concrete functions, which are usually stored in libraries, it is currently not possible to store templates in libraries (although precompiled header files may be implemented in various compilers). Consequently, using template declarations puts a burden on the shoulders of the software engineer, who has to make sure that the required instantiations exist. Below a simple way to accomplish that is introduced.

A template function declaration is simply created: the function's body is replaced by a semicolon. Note that this is exactly identical to the way concrete function declarations are constructed. So, the previously defined template function add() can simply be declared as

    template <typename Type>
    Type add(Type const &lvalue, Type const &rvalue);

Actually, we've already encountered template declarations. The header file iosfwd may be included in sources not requiring instantiations of elements from the class ios and its derived classes. For example, in order to compile the declaration

        std::string getCsvline(std::istream &in, char const *delim);
it is not necessary to include the string and istream header files. Rather, a single
        #include <iosfwd>
is sufficient, requiring about one-ninth the amount of time it takes to compile the declaration when string and istream are included.

18.3.1: Instantiation declarations

So, if declaring template functions speeds up the compilation and the linking phases of a program, how can we make sure that the required instantiations of the template functions will be available when the program is eventually linked together?

For this a variant of a declaration is available, a so-called explicit instantiation declaration. An explicit instantiation declaration contains the following elements:

Although this is a declaration, it is actually understood by the compiler as a request to instantiate that particular variant of the function.

Using explicit instantiation declarations all instantiations of template functions required by a program can be collected in one file. This file, which should be a normal source file, should include the template definition header file, and should next specify the required instantiation declarations. Since it's a source file, it will not be included by other sources. So namespace using directives and declarations may safely be used once the required headers have been included. Here is an example showing the required instantiations for our earlier add() template, instantiated for double, int, and std::string types:

    #include "add.h"
    #include <string>
    using namespace std;

    template int add<int>(int const &lvalue, int const &rvalue);
    template double add<double>(double const &lvalue, double const &rvalue);
    template string add<string>(string const &lvalue, string const &rvalue);
If we're sloppy and forget to mention an instantiation required by our program, then the repair can easily be made: just add the missing instantiation declaration to the above list. After recompiling the file and relinking the program we're done.

18.4: Instantiating template functions

A template is not instantiated when its definition is read by the compiler. A template is merely a recipe telling the compiler how to create particular code once it's time to do so. It's very much like a recipe in a cooking book: you reading a cake's recipe doesn't mean you have actually cooked that cake by the time you've read the recipe.

So, when is a template function actually instantiated? There are two situations in which the compiler will decide to instantiate templates:

The location of statements causing the compiler to instantiate a template is called the template's point of instantiation. The point of instantiation has serious implications for the template function's code. These implications are discussed in section 18.9.

The compiler is not always able to deduce the template's type parameters unambiguously. In that case the compiler reports an ambiguity which must be solved by the software engineer. Consider the following code:

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

    size_t fun(int (*f)(int *p, size_t n));
    double fun(double (*f)(double *p, size_t n));

    int main()
    {
        std::cout << fun(add) << std::endl;
    }
When this small program is compiled, the compiler reports an ambiguity it cannot resolve. It has two candidate functions, as for each overloaded version of fun() a proper instantiation of add() can be constructed:
    error: call of overloaded 'fun(<unknown type>)' is ambiguous
    note: candidates are: int fun(size_t (*)(int*, size_t))
    note:                 double fun(double (*)(double*, size_t))
Situations like these should of course be avoided. Template functions can only be instantiated if there's no ambiguity. Ambiguities arise when multiple functions emerge from the compiler's function selection mechanism (see section 18.8). It is up to us to resolve these ambiguities. Ambiguities like the above can be resolved using a blunt static_cast (as we select among alternatives, all of them possible and available):
    #include <iostream>
    #include "add.h"

    int fun(int (*f)(int const &lvalue, int const &rvalue));
    double fun(double (*f)(double const &lvalue, double const &rvalue));

    int main()
    {
        std::cout << fun(
                        static_cast<int (*)(int const &, int const &)>(add)
                    ) << std::endl;
        return 0;
    }
But if possible, type casts should be avoided. How to avoid casts in situations like these is explained in the next section (18.5).

As mentioned in section 18.3, the linker will remove identical instantiations of a template from the final program, leaving only one instantiation for each unique set of actual template type parameters. Let's have a look at an example showing this behavior of the linker. To illustrate the linker's behavior, we will do as follows:

So, from our little experiment we can conclude that the linker will indeed remove identical template instantiations from a final program, and that using mere template declarations will not result in template instantiations.

18.5: Using explicit template types

In the previous section (section 18.4) we've seen that the compiler may encounter ambiguities when attempting to instantiate a template. We've seen an example in which overloaded versions of a function fun() existed, expecting different types of arguments, both of which could have been provided by an instantiation of a template function. The intuitive way to solve such an ambiguity is to use a static_cast type cast, but as noted: if possible, casts should be avoided.

When template functions are involved, such a static_cast may indeed neatly be avoided, using explicit template type arguments. When explicit template type arguments are used the compiler is explicitly informed about the actual template type parameters it should use when instantiating a template. Here, the function's name is followed by an actual template parameter type list which may again be followed by the function's argument list, if required. The actual types mentioned in the actual template parameter list are used by the compiler to `deduce' the actual types of the corresponding template types of the function's template parameter type list. Here is the same example as given in the previous section, now using explicit template type arguments:

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

    int fun(int (*f)(int const &lvalue, int const &rvalue));
    double fun(double (*f)(double const &lvalue, double const &rvalue));

    int main()
    {
        std::cout << fun(add<int>) << std::endl;
        return 0;
    }

18.6: Overloading template functions

Let's once again look at our add() template. That template was designed to return the sum of two entities. If we would want to compute the sum of three entities, we could write:
    int main()
    {
        add(2, add(3, 4));
    }
This is a perfectly acceptable solution for the occasional situation. However, if we would have to add three entities regularly, an overloaded version of the add() function, expecting three arguments, might be a useful thing to have. The solution for this problems is simple: template functions may be overloaded.

To define an overloaded version, merely put multiple definitions of the template in its definition header file. So, with the add() function this would be something like:

    template <typename Type>
    Type add(Type const &lvalue, Type const &rvalue)
    {
        return lvalue + rvalue;
    }

    template <typename Type>
    Type add(Type const &lvalue, Type const &mvalue, Type const &rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
The overloaded function does not have to be defined in terms of simple values. Like all overloaded functions, just a unique set of function parameters is enough to define an overloaded version. For example, here's an overloaded version that can be used to compute the sum of the elements of a vector:
    template <typename Type>
    Type add(std::vector<Type> const &vect)
    {
        return accumulate(vect.begin(), vect.end(), Type());
    }

Overloading templates does not have to restrict itself to the function's parameter list. The template's type parameter list itself may also be overloaded. The last definition of the add() template allows us to specify a std::vector as its first argument, but no deque or map. Overloaded versions for those types of containers could of course be constructed, but where's the end to that? Instead, let's look for common characteristics of these containers, and if found, define an overloaded template function on these common characteristics. One common characteristic of the mentioned containers is that they all support begin() and end() members, returning iterators. Using this, we could define a template type parameter representing containers that must support these members. But mentioning a plain `container type' doesn't tell us for what data type it has been instantiated. So we need a second template type parameter representing the container's data type, thus overloading the template's type parameter list. Here is the resulting overloaded version of the add() template:

    template <typename Container, typename Type>
    Type add(Container const &cont, Type const &init)
    {
        return std::accumulate(cont.begin(), cont.end(), init);
    }
With all these overloaded versions in place, we may now start the compiler to compile the following function:
    using namespace std;

    int main()
    {
        vector<int> v;

        add(3, 4);          // 1 (see text)
        add(v);             // 2
        add(v, 0);          // 3
    }

Having defined add() using two different template type parameters, and a template function having a parameter list containing two parameters of these types, we've exhausted the possibilities to define an add() function template having a function parameter list showing two different types. Even though the parameter types are different, we're still able to define a template function add() as a template function merely returning the sum of two differently typed entities:

    template <typename T1, typename T2>
    T1 add(T1 const &lvalue, T2 const &rvalue)
    {
        return lvalue + rvalue;
    }
However, now we won't be able to instantiate add() using two differently typed arguments anymore: the compiler won't be able resolve the ambiguity. It cannot choose which of the two overloaded versions defining two differently typed function parameters to use:
    int main()
    {
        add(3, 4.5);
    }
    /*
        Compiler reports:

        error: call of overloaded `add(int, double)' is ambiguous
        error: candidates are: Type add(const Container&, const Type&)
                                    [with Container = int, Type = double]
        error:                 T1 add(const T1&, const T2&)
                                    [with T1 = int, T2 = double]
    */
Consider once again the overloaded function accepting three arguments:
    template <typename Type>
    Type add(Type const &lvalue, Type const &mvalue, Type const &rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
It may be considered as a disadvantage that only equally typed arguments are accepted by this function: e.g., three ints, three doubles or three strings. To remedy this, we define yet another overloaded version of the function, this time accepting arguments of any type. Of course, when calling this function we must make sure that operator+() is defined between them, but apart from that there appears to be no problem. Here is the overloaded version accepting arguments of any type:
    template <typename Type1, typename Type2, typename Type3>
    Type1 add(Type1 const &lvalue, Type2 const &mvalue, Type3 const &rvalue)
    {
        return lvalue + mvalue + rvalue;
    }
Now that we've defined these two overloaded versions, let's call add() as follows:
        add(1, 2, 3);
In this case, one might expect the compiler to report an ambiguity. After all, the compiler might select the former function, deducing that Type == int, but it might also select the latter function, deducing that Type1 == int, Type2 == int and Type3 == int. However, the compiler reports no ambiguity. The reason for this is the following: if an overloaded template function is defined using more specialized template type parameters (e.g., all equal types) than another (overloaded) function, for which more general template type parameters (e.g., all different) have been used, then the compiler will select the more specialized function over the more general function wherever possible.

As a rule of thumb: when overloaded versions of a template function are defined, each overloaded version must use a unique combination of template type parameters to avoid ambiguities when the templates are instantiated. Note that the ordering of template type parameters in the function's parameter list is not important. When trying to instantiate the following binarg() template, an ambiguity will occur:

    template <typename T1, typename T2>
    void binarg(T1 const &first, T2 const &second)
    {}
    // and:
    template <typename T1, typename T2>
    void binarg(T2 const &first, T1 const &second)  // exchange T1 and T2
    {}
The ambiguity should come as no surprise. After all, template type parameters are just formal names. Their names (T1, T2 or Whatever) have no concrete meanings whatsoever.

Finally, overloaded functions may be declared, either using plain declarations or instantiation declarations, and explicit template parameter types may also be used. For example:

18.7: Specializing templates for deviating types

The initial add() template, defining two identically typed parameters works fine for all types sensibly supporting operator+() and a copy constructor. However, these assumptions are not always met. For example, when char *s are used, neither the operator+() nor the copy constructor is (sensibly) available. The compiler does not know this, and will try to instantiate the simple template function
    template <typename Type>
    Type add(Type const &t1, Type const &t2);
But it can't do so, since operator+() is not defined for pointers. In situations like these it is clear that a match between the template's type parameter(s) and the actually used type(s) is possible, but the standard implementation is senseless or produces errors.

To solve this problem a template explicit specialization may be defined. A template explicit specialization defines the template function for which a generic definition already exists, using specific actual template type parameters.

In the abovementioned case an explicit specialization is required for a char const *, but probably also for a char * type. Probably, as the compiler still uses the standard type-deducing process mentioned earlier. So, when our add() template function is specialized for char * arguments, then its return type must also be a char *, whereas it must be a char const * if the arguments are char const * values. In these cases the template type parameter Type will be deduced properly. With Type == char *, for example, the head of the instantiated function becomes:

        char *add(char *const &t1, char *const &t2)
If this is considered undesirable, an overloaded version could be designed expecting pointers. The following template function definition expects two (const) pointers, and returns a non-const pointer:
    template <typename T>
    T *add(T const *t1, T const *t2)
    {
        std::cout << "Pointers\n";
        return new T;
    }
But we might still not be where we want to be, as this overloaded version will now only accept pointers to constant T elements. Pointers to non-const T elements will not be accepted. At first sight it may come as a surprise that the compiler will not apply a qualification transformation. But there's no need for the compiler to do so: when non-const pointers are used the compiler will simply use the initial definition of the add() template function expecting any two arguments of equal types.

So do we have to define yet another overloaded version, expecting non-const pointers? It is possible, but at some point it should become clear that we're overshooting our goal. Like concrete functions and classes, templates should have well-described purposes. Trying to add overloaded template definitions to overloaded template definitions quickly turns the template into a kludge. Don't follow this approach. A better approach is probably to construct the template so that it fits its original purpose, make allowances for the occasional specific case, and to describe its purpose clearly in the template's documentation.

Nevertheless, there may be situations where a template explicit specialization may be worth considering. Two specializations for const and non-const pointers to characters might be considered for our add() template function. Template explicit specializations are constructed as follows:

Here are two explicit specializations for the template function add(), expecting char * and char const * arguments (note that the const still appearing in the first template specialization is unrelated to the specialized type (char *), but refers to the const & mentioned in the original template's definition. So, in this case it's a reference to a constant pointer to a char, implying that the chars may be modified):
    template <> char *add<char *>(char * const &p1,
                                        char * const &p2)
    {
        std::string str(p1);
        str += p2;
        return strcpy(new char[str.length() + 1], str.c_str());
    }

    template <> char const *add<char const *>(char const *const &p1,
                                        char const *const &p2)
    {
        static std::string str;
        str = p1;
        str += p2;
        return str.c_str();
    }
Template explicit specializations are normally included in the file containing the other template function's implementations.

A template explicit specialization can be declared in the usual way. I.e., by replacing its body with a semicolon.

Note in particular how important the pair of angle brackets are that follow the template keyword when declaring a template explicit specialization. If the angle brackets were omitted, we would have constructed a template instantiation declaration. The compiler would silently process it, at the expense of a somewhat longer compilation time.

When declaring a template explicit specialization (or when using an instantiation declaration) the explicit specification of the template type parameters can be omitted if the compiler is able to deduce these types from the function's arguments. As this is the case with the char (const) * specializations, they could also be declared as follows:

    template <> char const *add(char const *const &p1,
                                        char const *const &p2);
    template <> char const *add(char const *const &p1,
                                        char const *const &p2);
In addition, template <> could be omitted. However, this would remove the template character from the declaration, as the resulting declaration is now nothing but a plain function declaration. This is not an error: template functions and non-template functions may overload each other. Ordinary functions are not as restrictive as template functions with respect to allowed type conversions. This could be a reason to overload a template with an ordinary function every once in a while.

18.8: The template function selection mechanism

When the compiler encounters a function call, it must decide which function to call when overloaded functions are available. In this section this function selection mechanism is described.

In our discussion, we assume that we ask the compiler to compile the following main() function:

    int main()
    {
        double x = 12.5;
        add(x, 12.5);
    }
Furthermore we assume that the compiler has seen the following six function declarations when it's about to compile main():
    template <typename Type>                                    // function 1
    Type add(Type const &lvalue, Type const &rvalue);

    template <typename Type1, typename Type2>                   // function 2
    Type1 add(Type1 const &lvalue, Type2 const &rvalue);

    template <typename Type1, typename Type2, typename Type3>   // function 3
    Type1 add(Type1 const &lvalue, Type1 const &mvalue, Type2 const &rvalue);

    double add(float lvalue, double rvalue);                    // function 4
    double add(std::vector<double> const &vd);                  // function 5
    double divide(double lvalue, double rvalue);                // function 6
The compiler, having read main()'s statement, must now decide which function must actually be called. It proceeds as follows: Now we'll apply the above procedure to the viable functions 1, 2 and 4. As we will find function 1 to contain a slight complication, we'll start with function 2. Thus, at this point we could ask the compiler to select among:
    add(double const &, double const &b);
and
    add(float, double);
This does not involve `template function selection' since the first one has already been determined. As the first function doesn't require any standard conversion at all, it is selected, since a perfect match is selected over one requiring a standard conversion.

As an intermezzo you are invited to take a closer look at this process by defining float x instead of double x, or by defining add(float x, double x) as add(double x, double x): in these cases the template function has the same prototype as the non-template function, and so the non-template function is selected since it's a more specific function. Earlier we've seen that process in action when redefining ostream::operator>>(ostream &os, string &str) as a non-template function.

Now it's time to go back to template function 1.

Earlier this section, we preferred function 2 over function 4. Function 2 is a template function that required one qualification transformation. Function 1, on the other hand, did not require any transformation at all, so it emerges as the function to be used.

As an exercise, feed the above six declarations and main() to the compiler and wait for the linker errors: the linker will complain that the (template) function

    double add<double>(double const&, double const&)
is an undefined reference.

18.9: Compiling template definitions and instantiations

Consider the following definition of the add() template function:
    template <typename Container, typename Type>
    Type add(Container const &container, Type init)
    {
        return std::accumulate(container.begin(), container.end(), init);
    }
In this template definition, std::accumulate() is called, using container's begin() and end() members.

The calls container.begin() and container.end() are said to depend on template type parameters. The compiler, not having seen container's interface, cannot check whether container will actually have members begin() and end() returning input iterators, as required by std::accumulate.

On the other hand, std::accumulate() itself is a function call which is independent of any template type parameter. Its arguments are dependent of template parameters, but the function call itself isn't. Statements in a template's body that are independent of template type parameters are said not to depend on template type parameters.

When the compiler reads a template definition, it will verify the syntactical correctness of all statements not depending on template type parameters. I.e., it must have seen all class definitions, all type definitions, all function declarations etc., that are used in the statements not depending on the template's type parameters. If this condition isn't met, the compiler will not accept the template's definition. Consequently, when defining the above template, the header file numeric must have been included first, as this header file declares std::accumulate().

On the other hand, with statements depending on template type parameters the compiler cannot perform these extensive checks, as it has, for example, no way to verify the existence of a member begin() for the as yet unspecified type Container. In these cases the compiler will perform superficial checks, assuming that the required members, operators and types will eventually become available.

The location in the program's source where the template is instantiated is called its point of instantiation. At the point of instantiation the compiler will deduce the actual types of the template's type parameters. At that point it will check the syntactical correctness of the template's statements that depend on template type parameters. This implies that only at the point of instantiation the required declarations must have been read by the compiler. As a rule of thumb, make sure that all required declarations (usually: header files) have been read by the compiler at every point of instantiation of the template. For the template's definition itself a more relaxed requirement can be formulated. When the definition is read only the declarations required for statements not depending on the template's type parameters must be known.

18.10: Summary of the template declaration syntax

In this section the basic syntactical constructions when declaring templates are summarized. When defining templates, the terminating semicolon should be replaced by a function body. However, not every template declaration may be converted into a template definition. If a definition may be provided it is explicitly mentioned.