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: 7.0.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 function template will be introduced, and several examples of templates will be offered, both in this chapter and in chapter 21, 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 ordinary (i.e., functions or classes that are not templates), but on constructing templates.
This chapter starts by introducing function templates. The emphasis is on the required syntax when defining such functions. This chapter lays the foundation upon which the next chapter, introducing class templates and offering several real-life examples, is built.
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 function template
definition:
template <typename Type> Type add(Type const &lvalue, Type const &rvalue) { return lvalue + rvalue; }In this definition we distinguish:
template
, starting a template definition or
declaration.
template
: it is a list,
containing one or more comma-separated elements. This angle bracket enclosed
list is called the
template parameter list. When multiple elements are used, it could
look like, e.g.,
typename Type1, typename Type2
Type
. It is a formal type name, comparable to a formal parameter name in a
function's definition. Up to now we've only encountered formal variable names
with functions. The types of the parameters were always known by the time
the function was defined. Templates escalate the notion of formal names one
step further up the ladder, allowing type names to be formalized, rather than
just the formal parameter variable names themselves. The fact that Type
is
a formal type name is indicated by the keyword typename
, prefixed to
Type
in the template parameter list. A formal type name like Type
is
also called a
template type parameter. Template non-type parameters also
exist, and are introduced below.
Other texts on C++ sometimes use the keyword
class
where we use
typename
. So, in other texts
template definitions might start with a line like:
template <class Type>Using
class
instead of typename
is now, however, considered an
anachronism, and is
deprecated: a template type parameter is, after all,
a type name.
add()
template's definition.
Type const &
parameters. This has the usual meaning: the parameters are references to
Type
objects or values that will not be modified by the function.
add()
's body, it is clear that operator+()
is
used, as well as a copy constructor, as the function returns a value. This
allows us to formulate the following restrictions for the formal type
Type
:
Type
should support operator+()
Type
should support a copy constructor
Type
could be a std::string
, it could never be
an ostream
, as neither operator+()
nor the copy constructor are
available for streams.
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 support. For example, consider the
following main()
function (here and in the following simple examples it is
assumed that the template and the 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?
Type const
&
parameters to prevent unnecessary copying.
Type const &
:
argument type | Type == |
size_t const | size_t |
size_t | size_t |
size_t * | size_t * |
size_t const * | size_t const * |
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:
size_t
. Template parameters of specific (i.e., non-formal)
types used in template parameter lists are called
template non-type parameters.
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 size_t
.
Type const (&array)[Size]This parameter defines
array
as a reference parameter to an
array having Size
elements of type Type
, that may not be modified.
Type
and Size
are
used. Type
is of course the template's type parameter Type
, but
Size
is also a template parameter. It is an size_t
, whose value must
be inferable by the compiler when it compiles an actual call of the sum()
function template. Consequently, Size
must be a const
value. Such a
constant expression is called a
template non-type parameter, and it is
named in the template's parameter list.
Type
's concrete value, but also Size
's value. Since
the function sum()
only has one parameter, the compiler is only able to
infer Size
's value from the function's actual argument. It can do so if
the provided argument is an array (of known and fixed size), rather
than a pointer to Type
elements. So, in the following main()
function
the first statement will compile correctly, whereas the second statement
won't:
int main() { int values[5]; int *ip = values; cout << sum(values) << endl; // compiles ok cout << sum(ip) << endl; // won't compile }
Type t = Type()
is used to
initialize t
to a default value. Note here that no fixed value (like 0) is
used. Any type's default value may be obtained using its default constructor,
rather than using a fixed numerical value. Of course, not every class
accepts a numerical value as an argument to one of its constructors. But all
types, even the primitive types, support default constructors (actually, some
classes do not implement a default constructor, or make it inaccessible; but
most do). The default constructor of primitive types will initialize their
variables to 0 (or false
). Furthermore, the statement Type t = Type()
is a true initialization: t
is initialized by Type
's default
constructor, rather than using Type
's copy constructor to assign
Type()
's copy to t
.
It's interesting to note here (although unrelated to the current topic)
that the syntactical construction Type t(Type())
cannot be used, even
though it also looks like a proper initialization. Usually an initializing
argument can be provided to an object's definition, like string
s("hello")
. Why, then is Type t = Type()
accepted, whereas Type
t(Type())
isn't? When Type t(Type())
is used, it won't even be clear at
the site of the definition that it's not a Type
object's default
initialization. Instead, the compiler will only start generating error
messages once t
is used. This is caused by the fact that in C++ (and
in C alike) the compiler will try to see a function or
function pointer whenever possible: the
function prevalence rule.
According to this rule Type()
will be interpreted as a pointer to a
function expecting no arguments and returning a Type
, unless the compiler
clearly is unable to do so. In the initialization Type t = Type()
it can't
see a pointer to a function, as a Type
object cannot be given the value of
a function pointer (remember: Type()
is interpreted as Type (*)()
whenever possible). But in Type t(Type())
it can very well use the
pointer interpretation: t
is now declared as a function expecting
a pointer to a function returning a Type
, with t
itself also returning
a Type
. E.g., t
could have been defined as:
Type t(Type (*tp)()) { return (*tp)(); }
sum()
also assumes the
existence of certain public members in Type
's class. This time
operator+=()
and Type
's copy constructor.
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.
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
function template'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 as `fun()' { return Type(); }Although the compiler won't be able to handle a call to `
fun()
', it
is possible to call fun()
using an exmplicit type specification. E.g.,
fun<int>()
will call fun()
, instantiated for int
. This, of course
is not the same as compiler argument deduction.
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
function template 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 function non-template parameter type)). If it cannot deduce the actual types using these transformations, the template function will not be considered. These transformations are:
const
modifier to
a non-constant argument type;
int
to size_t
, int
to double
, etc.).
An lvalue-to-rvalue transformation is applied when anrvalue
is required, and anlvalue
is provided. This happens when a variable is used as argument to a function specifying a value parameter. For example,template<typename Type> Type negate(Type value) { return -value; } int main() { int x = 5; x = negate(x); // lvalue (x) to rvalue (copies x) }
An array-to-pointer transformation is applied when the name of an array is assigned to a pointer variable. This is frequently seen with functions defining pointer parameters. When calling such functions, arrays are often specified as their arguments. The array's address is then assigned to the pointer-parameter, and its type is used to deduce the corresponding template parameter's type. For example:template<typename Type> Type sum(Type *tp, size_t n) { return accumulate(tp, tp + n, Type()); } int main() { int x[10]; sum(x, 10); }In this example, the location of the arrayx
is passed tosum()
, expecting a pointer to some type. Using the array-to-pointer transformation,x
's address is considered a pointer value which is assigned totp
, deducing thatType
isint
in the process.
This transformation is most often seen with function templates defining a parameter which is a pointer to a function. When calling such a function the name of a function may be specified as its argument. The address of the function is then assigned to the pointer-parameter, deducing the template type parameter in the process. This is called a function-to-pointer transformation. For example:#include <cmath> template<typename Type> void call(Type (*fp)(Type), Type const &value) { (*fp)(value); } int main() { call(&sqrt, 2.0); }In this example, the address of thesqrt()
function is passed tocall()
, expecting a pointer to a function returning aType
and expecting aType
for its argument. Using the function-to-pointer transformation,sqrt
's address is considered a pointer value which is assigned tofp
, deducing thatType
isdouble
in the process. Note that the argument2.0
could not have been specified as2
, as there is noint sqrt(int)
prototype. Also note that the function's first parameter specifiesType (*fp)(Type)
, rather thanType (*fp)(Type const &)
as might have been expected from our previous discussion about how to specify the types of function template's parameters, preferring references over values. However,fp
's argumentType
is not a function template parameter, but a parameter of the functionfp
points to. Sincesqrt()
has prototypedouble sqrt(double)
, rather thandouble sqrt(double const &)
,call()
's parameterfp
must be specified asType (*fp)(Type)
. It's that strict.
const
or
volatile
qualifications
to pointers. This transformation is applied when the function template'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 function template'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
.
As class template derivation remains to be covered, the following discussion is necessarily somewhat abstract. Optionally, the reader may of course skip briefly to section 19.9, and return back to this section thereafter.
In this section it should be assumed, for the sake of argument, that a
class template Vector
has somehow been derived from a std::vector
.
Furthermore, assume that the following function template 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 function template
sortVectors()
may now also be used to sort Vector
objects. For example:
int main() { Vector<string> vs; // `Vector' instead of `std::vector' Vector<int> vi; sortVector(vs, CaseLess()); sortVector(vi, less<int>()); }In this example,
Vector
s 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.
Type
is int
if the argument is int x
, and the
function's parameter is Type &value
).
int
and a double
argument:
template <typename Type> Type add(Type const &lvalue, Type const &rvalue) { return lvalue + rvalue; }When calling this function template, two identical types must be used (albeit that the three standard transformations are of course allowed). If the template deduction mechanism does not come up with identical actual types for identical template types, then the function template will not be instantiated.
algorithm
on my old laptop takes about four times the amount of time it
takes to compile a plain header file like cmath
. The header file
iostream
is even harder to process, requiring almost 15 times the amount
of time it takes to process cmath
. Clearly, processing templates is
serious business for the compiler. On the other hand: don't overweigh this
drawback: compilers are getting better and better in their template processing
capacity and computers keep on getting faster and faster. What was a nuisance
a few years ago is hardly noticeable today.
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 then be available elsewhere (of course, this holds true for declarations in general). Unlike the situation we encounter with ordinary functions, which are usually stored in libraries, it is currently not possible to store templates in libraries (although the compiler may construct precompiled header files). 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 function template declaration is simply created: the function's body is
replaced by a semicolon. Note that this is exactly identical to the way
ordinary function declarations are constructed. So, the previously defined
function template 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.
For this a variant of a declaration is available, a so-called explicit instantiation declaration. An explicit instantiation declaration contains the following elements:
template
, omitting the template
parameter list.
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.
So, when is a function template actually instantiated? There are two situations in which the compiler will decide to instantiate templates:
add()
is called with a pair of size_t
values);
#include "add.h" char (*addptr)(char const &, char const &) = add;
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 little 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. Function templates 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:
source1.cc
defines a function fun()
, instantiating
add()
for int
-type arguments, including add()
's template
definition. It displays add()
's address. Here is source1.cc
:
union PointerUnion { int (*fp)(int const &, int const &); void *vp; };
#include <iostream> #include "add.h" #include "pointerunion.h" void fun() { PointerUnion pu = { add }; std::cout << pu.vp << std::endl; }
source2.cc
defines the same function, but only declares the
proper add()
template, using a template declaration (not an
instantiation declaration). Here is source2.cc
:
#include <iostream> #include "pointerunion.h" template<typename Type> Type add(Type const &, Type const &); void fun() { PointerUnion pu = { add }; std::cout << pu.vp << std::endl; }
main.cc
again includes add()
's template definition,
declares the function fun()
and defines main()
, defining add()
for int
-type arguments as well and displaying add()
's function
address. It also calls the function fun()
. Here is main.cc
:
#include <iostream> #include "add.h" #include "pointerunion.h" void fun(); int main() { PointerUnion pu = { add }; fun(); std::cout << pu.vp << std::endl; }
source1.o
(2104 bytes, using g++
version 4.1.2. All sizes reported
here may differ somewhat for different compilers and/or run-time libraries)
and source2.o
(1928 bytes). Since source1.o
contains the instantiation
of add()
, it is somewhat larger than source2.o
, containing only the
template's declaration. Now we're ready to start our little experiment.
main.o
and source1.o
, we obviously link together two
object modules, each containing its own instantiation of the same template
function. The resulting program produces the following output:
0x80486d8 0x80486d8Furthermore, the size of the resulting program is 8701 bytes.
main.o
and source2.o
, we now link together an object
module containing the instantiation of the add()
template, and another
object module containing the mere declaration of the same template
function. So, the resulting program cannot but contain a single instantiation
of the required function template. This program has exactly the same size, and
produces exactly the same output as the first program.
fun()
existed, expecting different types of arguments, both of which could
have been provided by an instantiation of a function template. The intuitive
way to solve such an ambiguity is to use a static_cast
, but as noted: if
possible, casts should be avoided.
When function templates 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; }
Explicit template argument types can be used in situations where the
compiler has no way to detect which types should actually be used. E.g., in
section 18.2 the function template Type fun()
was defined. To
instantiate this function for the double
type, we can use
fun<double>()
.
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:
function templates 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 boil down to, e.g.:
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
function template 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); }One may wonder whether the
init
parameter could not be left out of the
parameter list as init
will often have a default initialization value. The
answer is a somewhat complex `yes', It is possible to define the add()
function as follows:
template <typename Type, typename Container> Type add(Container const &cont) { Type init = Type(); return std::accumulate(cont.begin(), cont.end(), init); }But note that the template's type parameters were reordered, which is necessary because the compiler won't be able to determine
Type
in a call
like:
int x = add(vectorOfInts);However, it is also possible to use a third kind of template parameter, a template template parameter, which does allow the compiler to determine
Type
directly from the actual container argument used when
calling add()
. Template template parameters are discussed in section
20.3.
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 }
int
. It will therefore instantiate add<int>()
, our very
first definition of the add()
template.
add()
requiring but one
argument. It finds the version expecting a std::vector
, deducing that the
template's type parameter must be int
. It instantiates
add<int>(std::vector<int> const &)
add()
template's first definition. But it can use
the last definition, expecting entities having different types. As a
std::vector
supports begin()
and end()
, the compiler is now able
to instantiate the function template
add<std::vector<int>, int>(std::vector<int> const &, int const &)
Having defined add()
using two different template type parameters, and
a function template 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
function template add()
as a function template 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
int
s, three double
s or
three string
s. 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 function template
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:
add()
accepting containers
of a certain type:
template <typename Container, typename Type> Type add(Container const &container, Type const &init);
template int add<std::vector<int>, int> (std::vector<int> const &vect, int const &init);
std::vector<int> vi; int sum = add<std::vector<int>, int>(vi, 0);
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 function template
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 pointless or produces errors.
To solve this problem a template explicit specialization may be defined. A template explicit specialization defines the function template 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()
function template 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 function template 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 our approach doesn't scale. Like ordinary 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()
function template. Template explicit specializations are constructed as
follows:
template
.
error: template-id `add<char*>' for `char* add(char* const&, char* const&)' does not match any template declaration
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 char
s 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 function template'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-function templates may overload each other. Ordinary
functions are not as restrictive as function templates with respect to allowed
type conversions. This could be a reason to overload a template with an
ordinary function every once in a while.
A function template explicit specialization is not just another overloaded version of the the function template. Whereas an overloadeded version may define a completely different set of template parameters, a specialiation must use the same set of template parameters as its non-specialized variant, but the compiler will use the specialization in situations where the actual template arguments match the types defined by the specialization. Subject to this restriction, many specializations can be defined.
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 6The compiler, having read
main()
's statement, must now decide which
function must actually be called. It proceeds as follows:
template <typename T1, typename T2> T1 add(T1 const &a, T2 const &b);The function is called as
add(x, 12.5)
. As x
is a double
both
T &x
and T const &x
would be acceptable, albeit that T const &x
will require a qualification transformation. Since the function's prototype
uses T const &
a qualification transformation is needed. The function is
charged 1 point, and tf(T1) is now determined as double
.
Next, 12.5 is recognized as a double
as well (note that float
constants are recognized by their `F' suffix, e.g., 12.5F), and it is also a
constant value. So, without transformations, we find 12.5 == T2 const &
and at no charge T2
is recognized as double
as well.
double add(float lvalue, double rvalue);Although it is called as
add(x, 12.5)
with x
being of type
double
; but a standard conversion exists from type double
to type
float
. Furthermore, 12.5 is a double
, which can be used to initialize
rvalue
.
add(double const &, double const &b);and
add(float, double);This does not involve `function template 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 function
template has the same prototype as the ordinary function, and so the ordinary
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 an ordinary function.
Now it's time to go back to function template 1.
template <typename T> T add(T const &t1, T const &t2);Once again we call
add(x, 12.5)
and will deduce template types. In
this case there's only one template type parameter T. Let's start with the
first parameter:
x
is of type double
, so both T &x
and
T const &x
are acceptable. According to the function's parameter list T
const &x
must be used, which requires a qualification transformation. So
we'll charge the function 1 point and T is determined as double
. This
results in the instantiation of
add(double const &t1, double const &t2)allowing us to call, at the expense of 1 point,
add(x, 12.5)
.
double
value we see that 12.5 == T
const &
. So we conclude (free of charge) that T is double
. Our function
becomes
add(double const &t1, double const &t2)allowing us to call
add(x, 12.5)
.
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.
add()
function template:
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()
.
Realize that 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.
template <typename Type1, typename Type2> void function(Type1 const &t1, Type2 const &t2);
template
):
template void function<int, double>(int const &t1, double const &t2);
void (*fp)(double, double) = function<double, double>; void (*fp)(int, int) = function<int, int>;
template <> void function<char *, char *>(char *const &t1, char *const &t2);
friend void function<Type1, Type2>(parameters);