Базовая терминология шаблонов
"Class Template" или "Template Class"?
В C++,
структуры,классы и юнионы называются классовыми типами
Использование слова "class" может указывать на использование либо ключевого слова class
либо struct.
Чего нельзя сказать о юнионах.
Существуют спорные моменты :
Термин class template указывает на то ,
что класс является шаблоном.
Термин template class
говорит о следующем :
- это синоним для вышеупомянутого class template. -
ссылается на класс , сгенерированный из шаблона
-
ссылается на класс , имя которого - template-id.
В этой книге мы будем избегать термина template class.
Инсталляция и специализация
Процесс создания класса , функции или члена-функции из шаблона называется шаблонной инсталляцией -
template instantiation.
Результат называется специализацией - specialization.
У инсталляции есть альтернатива , которая позволяет программисту явно декларировать
механизм получения параметров шаблона.
Пример специализации template<>:
template <typename T1, typename T2> // primary class template
class MyClass {
…
};
template<> // explicit specialization
class MyClass<std::string,float> {
…
};
Это пример явной специализации.
Специализация с параметрами называется парциальной специализацией :
template <typename T> // partial specialization
class MyClass<T,T> {
…
};
template <typename T> // partial specialization
class MyClass<bool,T> {
…
};
Когда бы говорим о явной или парциальной специализации ,
базовый шаблон называется primary template.
|
Декларации и определения
Термины декларация и определение несут свое значение в стандарте С++.
Декларация - это конструкция С++ , которая определяет или переопределяет имя - например :
class C; // a declaration of C as a class
void f(int p); // a declaration of f() as a function and p as a named parameter
extern int v; // a declaration of v as a variable
Надо заметить , что макросы и метки goto не рассматриваются в С++ как декларации.
Декларация становится определением тогда , когда инициализируются детали ее структуры ,
а в случае переменных - когда под них выделяется память.
Для класса и функции должна быть создана не-пустая реализация.
Примеры деклараций:
class C {}; // definition (and declaration) of class C
void f(int p) { // definition (and declaration) of function f()
std::cout << p << std::endl;
}
extern int v = 1; // an initializer makes this a definition for v
int w; // global variable declarations not preceded by
// extern are also definitions
Декларация класса шаблона :
template <typename T>
void func (T);
и определение :
template <typename T>
class S {};
|
Правило One-Definition
The C++ language definition places some constraints on the redeclaration of various entities. The totality of these constraints is known as the one-definition rule or ODR. The details of this rule are quite complex and span a large variety of situations. Later chapters illustrate the various resulting facets in each applicable context, and you can find a complete description of the ODR in Appendix A. For now, it suffices to remember the following ODR basics:
Noninline functions and member functions, as well as global variables and static data members should be defined only once across the whole program. Class types (including structs and unions) and inline functions should be defined at most once per translation unit, and all these definitions should be identical.
A translation unit is what results from preprocessing a source file; that is, it includes the contents named by #include directives.
In the remainder of this book, linkable entity means one of the following: a noninline function or member function, a global variable or a static data member, including any such things generated from a template.
|
7.5 Template Arguments versus Template Parameters
Compare the following class template
template <typename T, int N>
class ArrayInClass {
public:
T array[N];
};
with a similar plain class:
class DoubleArrayInClass {
public:
double array[10];
};
The latter becomes essentially equivalent to the former if we replace the parameters T and N by double and 10 respectively. In C++, the name of this replacement is denoted as
ArrayInClass<double,10>
Note how the name of the template is followed by so-called template arguments in angle brackets.
Regardless of whether these arguments are themselves dependent on template parameters, the combination of the template name, followed by the arguments in angle brackets, is called a template-id.
This name can be used much like a corresponding nontemplate entity would be used. For example:
int main()
{
ArrayInClass<double,10> ad;
ad.array[0] = 1.0;
}
It is essential to distinguish between template parameters and template arguments. In short, you can say that you "pass arguments to become parameters."
Or more precicely:
Template parameters
are those names that are listed after the keyword template in the template declaration or definition (T and N in our example).
Template arguments
are the items that are substituted for template parameters (double and 10 in our example). Unlike template parameters, template arguments can be more than just "names."
The substitution of template parameters by template arguments is explicit when indicated with a template-id, but there are various situations when the substitution is implicit (for example, if template parameters are substituted by their default arguments).
A fundamental principle is that any template argument must be a quantity or value that can be determined at compile time. As becomes clear later, this requirement translates into dramatic benefits for the run-time costs of template entities. Because template parameters are eventually substituted by compile-time values, they can themselves be used to form compile-time expressions. This was exploited in the ArrayInClass template to size the member array array. The size of an array must be a so-called constant-expression, and the template parameter N qualifies as such.
We can push this reasoning a little further: Because template parameters are compile-time entities, they can also be used to create valid template arguments. Here is an example:
template <typename T>
class Dozen {
public:
ArrayInClass<T,12> contents;
};
Note how in this example the name T is both a template parameter and a template argument. Thus, a mechanism is available to enable the construction of more complex templates from simpler ones. Of course, this is not fundamentally different from the mechanisms that allow us to assemble types and functions.
|
Chapter 8. Fundamentals in Depth
In this chapter we review some of the fundamentals introduced in the first part of this book in depth: the declaration of templates, the restrictions on template parameters, the constraints on template arguments, and so forth.
|
8.1 Parameterized Declarations
C++ currently supports two fundamental kinds of templates: class templates and function templates (see Section 13.6 on page 212 for a possible future change in this area). This classification includes member templates. Such templates are declared much like ordinary classes and functions, except for being introduced by a parameterization clause of the form
template<… parameters here… >
or perhaps
export template<… parameters here… >
(see Section 6.3 on page 68 and Section 10.3.3 on page 149 for a detailed explanation of the keyword export).
We'll come back to the actual template parameter declarations in a later section. An example illustrates the two kinds of templates, both as class members and as ordinary namespace scope declarations:
template <typename T>
class List { // a namespace scope class template
public:
template <typename T2> // a member function template
List (List<T2> const&); // (constructor)
…
};
template <typename T>
template <typename T2>
List<T>::List (List<T2> const& b) // an out-of-class member function
{ // template definition
…
}
template <typename T>
int length (List<T> const&); // a namespace scope function template
class Collection {
template <typename T> // an in-class member class template
class Node { // definition
…
};
template <typename T> // another member class template,
class Handle; // without its definition
template <typename T> // an in-class (and therefore implicitly
T* alloc() { // inline) member function template
… // definition
}
…
};
template <typename T> // an out-of-class member class
class Collection::Node { // template definition
…
};
Note how member templates defined outside their enclosing class can have multiple template<…> parameterization clauses: one for the template itself and one for every enclosing class template. The clauses are listed starting from the outermost class template.
Union templates are possible too (and they are considered a kind of class template):
template <typename T>
union AllocChunk {
T object;
unsigned char bytes[sizeof(T)];
};
Function templates can have default call arguments just like ordinary function declarations:
template <typename T>
void report_top (Stack<T> const&, int number = 10);
template <typename T>
void fill (Array<T>*, T const& = T()); // T() is zero for built-in types
The latter declaration shows that a default call argument could depend on a template parameter. When the fill() function is called, the default argument is not instantiated if a second function call argument is supplied. This ensures that no error is issued if the default call argument cannot be instantiated for a particular T. For example:
class Value {
public:
Value(int); // no default constructor
};
void init (Array<Value>* array)
{
Value zero(0);
fill(array, zero); // OK: = T() is not used
fill(array); // ERROR: = T() is used, but not valid for T = Value
}
In addition to the two fundamental kinds of templates, three other kinds of declarations can be parameterized using a similar notation. All three correspond to definitions of members of class templates
:
Definitions of member functions of class templates Definitions of nested class members of class templates Definitions of static data members of class templates
Although they can be parameterized, such definitions aren't quite first-class templates. Their parameters are entirely determined by the template of which they are members. Here is an example of such definitions:
template <int I>
class CupBoard {
void open();
class Shelf;
static double total_weight;
…
};
template <int I>
void CupBoard<I>::open()
{
…
}
template <int I>
class CupBoard<I>::Shelf {
…
};
template <int I>
double CupBoard<I>::total_weight = 0.0;
Although such parameterized definitions are commonly called templates, there are contexts when the term doesn't quite apply to them.
8.1.1 Virtual Member Functions
Member function templates cannot be declared virtual. This constraint is imposed because the usual implementation of the virtual function call mechanism uses a fixed-size table with one entry per virtual function. However, the number of instantiations of a member function template is not fixed until the entire program has been translated. Hence, supporting virtual member function templates would require support for a whole new kind of mechanism in C++ compilers and linkers.
In contrast, the ordinary members of class templates can be virtual because their number is fixed when a class is instantiated:
template <typename T>
class Dynamic {
public:
virtual ~Dynamic(); // OK: one destructor per instance of Dynamic<T>
template <typename T2>
virtual void copy (T2 const&);
// ERROR: unknown number of instances of copy()
// given an instance of Dynamic<T>
};
8.1.2 Linkage of Templates
Every template must have a name and that name must be unique within its scope, except that function templates can be overloaded (see Chapter 12). Note especially that, unlike class types, class templates cannot share a name with a different kind of entity:
int C;
class C; // OK: class names and nonclass names are in a different ''space''
int X;
template <typename T>
class X; // ERROR: conflict with variable X
struct S;
template <typename T>
class S; // ERROR: conflict with struct S
Template names have linkage, but they cannot have C linkage. Nonstandard linkages may have an implementation-dependent meaning (however, we don't know of an implementation that supports nonstandard name linkages for templates):
extern "C++" template <typename T>
void normal();
// this is the default: the linkage specification could be left out
extern "C" template <typename T>
void invalid();
// invalid: templates cannot have C linkage
extern "Xroma" template <typename T>
void xroma_link();
// nonstandard, but maybe some compiler will some day
// support linkage compatible with the Xroma language
Templates usually have external linkage. The only exceptions are namespace scope function templates with the static specifier:
template <typename T>
void external(); // refers to the same entity as a declaration of
// the same name (and scope) in another file
template <typename T>
static void internal(); // unrelated to a template with the same name in
// another file
Note that templates cannot be declared in a function.
8.1.3 Primary Templates
Normal declarations of templates declare so-called primary templates. Such template declarations are declared without adding template arguments in angle brackets after the template name:
template<typename T> class Box; // OK: primary template
template<typename T> class Box<T>; // ERROR
template<typename T> void translate(T*); // OK: primary template
template<typename T> void translate<T>(T*); // ERROR
Nonprimary class templates occur when declaring so-called partial specializations which are discussed in Chapter 12. Function templates must always be primary templates (but see Section 13.7 on page 213 for a potential future language change).
|
8.2 Template Parameters
There are three kinds of template parameters:
Type parameters (these are by far the most common) Nontype parameters Template template parameters
Template parameters are declared in the introductory parameterization clause of a template declaration. Such declarations do not necessarily need to be named:
template <typename, int>
class X;
A parameter name is, of course, required if the parameter is referred to later in the template. Note also that a template parameter name can be referred to in a subsequent parameter declaration (but not before):
template <typename T, // the first parameter is used in the
T* Root, // declaration of the second one and
template<T*> class Buf> // the third one
class Structure;
8.2.1 Type Parameters
Type parameters are introduced with either the keyword typename or the keyword class: The two are entirely equivalent.
The keyword must be followed by a simple identifier and that identifier must be followed by a comma to denote the start of the next parameter declaration, a closing angle bracket (>) to denote the end of the parameterization clause, or an equal sign (=) to denote the beginning of a default template argument.
Within a template declaration, a type parameter acts much like a typedef name. For example, it is not possible to use an elaborated name of the form class T when T is a template parameter, even if T were to be substituted by a class type:
template <typename Allocator>
class List {
class Allocator* allocator; // ERROR
friend class Allocator; // ERROR
…
};
It is possible that a mechanism to enable such a friend declaration will be added in the future.
8.2.2 Nontype Parameters
Nontype template parameters stand for constant values that can be determined at compile or link time.
The type of such a parameter (in other words, the type of the value for which it stands) must be one of the following:
An integer type or an enumeration type A pointer type (including regular object pointer types, function pointer types, and pointer-to-member types) A reference type (both references to objects and references to functions are acceptable)
All other types are currently excluded (although floating-point types may be added in the future, see Section 13.4 on page 210).
Perhaps surprisingly, the declaration of a nontype template parameter can in some cases also start with the keyword typename:
template<typename T, // a type parameter
typename T::Allocator* Allocator> // a nontype parameter
class List;
The two cases are easily distinguished because the first is followed by a simple identifier, whereas the second is followed by a qualified name (in other words, a name containing a double colon, ::). Section 1.1 on page 43 and Section 9.3.2 on page 130 explain the need for the keyword typename in the nontype parameter.
Function and array types can be specified, but they are implicitly adjusted to the pointer type to which they decay:
template<int buf[5]> class Lexer; // buf is really an int*
template<int* buf> class Lexer; // OK: this is a redeclaration
Nontype template parameters are declared much like variables, but they cannot have nontype specifiers like static, mutable, and so forth. They can have const and volatile qualifiers, but if such a qualifier appears at the outermost level of the parameter type, it is simply ignored:
template<int const length> class Buffer; // const is useless here
template<int length> class Buffer; // same as previous declaration
Finally, nontype parameters are always rvalues: Their address cannot be taken, and they cannot be assigned to.
8.2.3 Template Template Parameters
Template template parameters are placeholders for class templates. They are declared much like class templates, but the keywords struct and union cannot be used:
template <template<typename X> class C> // OK
void f(C<int>* p);
template <template<typename X> struct C> // ERROR: struct not valid here
void f(C<int>* p);
template <template<typename X> union C> // ERROR: union not valid here
void f(C<int>* p);
In the scope of their declaration, template template parameters are used just like other class templates.
The parameters of template template parameters can have default template arguments. These default arguments apply when the corresponding parameters are not specified in uses of the template template parameter:
template <template<typename T,
typename A = MyAllocator> class Container>
class Adaptation {
Container<int> storage; // implicitly equivalent to
// Container<T, MyAllocator>
…
};
The name of a template parameter of a template template parameter can be used only in the declaration of other parameters of that template template parameter. The following contrived template illustrates this concept:
template <template<typename T, T*> class Buf>
class Lexer {
static char storage[5];
Buf<char, &Lexer<Buf>::storage> buf;
…
};
template <template<typename T> class List>
class Node {
static T* storage; // ERROR: a parameter of a template template
// parameter cannot be used here
…
};
Usually however, the names of the template parameters of a template template parameter are not used. As a result, the former parameters are often left unnamed altogether. For example, our earlier Adaptation template could be declared as follows:
template <template <typename,
typename = MyAllocator> class Container>
class Adaptation
{
Container<int> storage; // implicitly equivalent to
// Container<int, MyAllocator>
…
};
8.2.4 Default Template Arguments
Currently, only class template declarations can have default template arguments (see Section 13.3 on page 207 for likely changes in this area). Any kind of template parameter can be equipped with a default argument, although it must match the corresponding parameter. Clearly, a default argument should not depend on its own parameter. However, it may depend on previous parameters:
template <typename T, typename Allocator = allocator<T> >
class List;
Similar to default function call arguments, a template parameter can have a default template argument only if default arguments were also supplied for the subsequent parameters. The subsequent default values are usually provided in the same template declaration, but they could also have been declared in a previous declaration of that template. The following example makes this clear:
template <typename T1, typename T2, typename T3,
typename T4 = char, typename T5 = char>
class Quintuple; // OK
template <typename T1, typename T2, typename T3 = char,
typename T4, typename T5>
class Quintuple; // OK: T4 and T5 already have defaults
template <typename T1 = char, typename T2, typename T3,
typename T4, typename T5>
class Quintuple; // ERROR: T1 cannot have a default argument
// because T2 doesn't have a default
Default template arguments cannot be repeated:
template<typename T = void>
class Value;
template<typename T = void>
class Value; // ERROR: repeated default argument
|
8.3 Template Arguments
Template arguments are the "values" that are substituted for template parameters when instantiating a template. These values can be determined using several different mechanisms:
Explicit template arguments:
A template name can be followed by explicit template argument values enclosed in angle brackets. The resulting name is called a template-id.
Injected class name:
Within the scope of a class template X with template parameters P1, P2, …, the name of that template (X) can be equivalent to the template-id X<P1, P2, …>. See Section 9.2.3 on page 126 for details.
Default template arguments:
Explicit template arguments can be omitted from class template instances if default template arguments are available. However, even if all template parameters have a default value, the (possibly empty) angle brackets must be provided.
Argument deduction:
Function template arguments that are not explicitly specified may be deduced from the types of the function call arguments in a call. This is described in detail in Chapter 11. Deduction is also done in a few other situations. If all the template arguments can be deduced, no angle brackets need to be specified after the name of the function template.
8.3.1 Function Template Arguments
Template arguments for a function template can be specified explicitly or deduced from the way the template is used. For example:
// details/max.cpp
template <typename T>
inline T const& max (T const& a, T const& b)
{
return a<b?b:a;
}
int main()
{
max<double>(1.0, -3.0); // explicitly specify template argument
max(1.0, -3.0); // template argument is implicitly deduced
// to be double
max<int>(1.0, 3.0); // the explicit <int> inhibits the deduction;
// hence the result has type int
}
Some template arguments can never be deduced (see Chapter 11). The corresponding parameters are best placed at the beginning of the list of template parameters so they can be specified explicitly while allowing the other arguments to be deduced. For example:
// details/implicit.cpp
template <typename DstT, typename SrcT>
inline DstT implicit_cast (SrcT const& x) // SrcT can be deduced,
{ // but DstT cannot
return x;
}
int main()
{
double value = implicit_cast<double>(-1);
}
If we had reversed the order of the template parameters in this example (in other words, if we had written template<typename SrcT, typename DstT>), a call of implicit_cast would have to specify both template arguments explicitly.
Because function templates can be overloaded, explicitly providing all the arguments for a function template may not be sufficient to identify a single function: In some cases, it identifies a set of functions. The following example illustrates a consequence of this observation:
template <typename Func, typename T>
void apply (Func func_ptr, T x)
{
func_ptr(x);
}
template <typename T> void single(T);
template <typename T> void multi(T);
template <typename T> void multi(T*);
int main()
{
apply(&single<int>, 3); // OK
apply(&multi<int>, 7); // ERROR: no single multi<int>
}
In this example, the first call to apply() works because the type of the expression &single<int> is unambiguous. As a result, the template argument value for the Func parameter is easily deduced. In the second call, however, &multi<int> could be one of two different types and therefore Func cannot be deduced in this case.
Furthermore, it is possible that explicitly specifying the template arguments for a function template results in an attempt to construct an invalid C++ type. Consider the following overloaded function template (RT1 and RT2 are unspecified types):
template<typename T> RT1 test(typename T::X const*);
template<typename T> RT2 test(...);
The expression test<int> makes no sense for the first of the two function templates because type int has no member type X. However, the second template has no such problem. Therefore, the expression &test<int> identifies the address of a single function. The fact that the substitution of int into the first template fails does not make the expression invalid.
This "substitution-failure-is-not-an-error" (SFINAE) principle is clearly an important ingredient to make the overloading of function templates practical. However, it also enables remarkable compile-time techniques. For example, assuming that types RT1 and RT2 are defined as follows:
typedef char RT1;
typedef struct { char a[2]; } RT2;
We can check at compile time (in other words, as a so-called constant-expression) whether a given type T has a member type X:
#define type_has_member_type_X(T) \
(sizeof(test<T>(0)) == 1)
To understand the expression in this macro, it is convenient to analyze from the outside to the inside. First, the sizeof expression will equal one if the first test template (which returns a char of size one) is selected. The other template returns a structure with a size that is at least two (because it contains an array of size two). In other words, this is a device to determine as a constant-expression whether the first or second template was selected for the call test<T>(0). Clearly, the first template cannot be selected if the given type T has no member type X. However, if the given type has a member type X, then the first template is preferred because overload resolution (see Appendix B) prefers the conversion from zero to a null pointer constant over binding an argument to an ellipsis parameter (ellipsis parameters are the weakest kind of binding from an overload resolution perspective). Similar techniques are explored in Chapter 15.
The SFINAE principle protects only against attempts to create invalid types but not against attempts to evaluate invalid expressions. The following example is therefore invalid C++:
template<int I> void f(int (&)[24/(4-I)]);
template<int I> void f(int (&)[24/(4+I)]);
int main()
{
&f<4>; // ERROR: division by zero (SFINAE doesn't apply)
}
This example is an error even though the second template supports the substitution without leading to a division by zero. This sort of error must occur in the expression itself and not in binding of an expression to a template parameter. Indeed, the following example is valid:
template<int N> int g() { return N; }
template<int* P> int g() { return *P }
int main()
{
return g<1>(); // 1 cannot be bound to int* parameter,
} // but SFINAE principle applies
See Section 15.2.2 on page 266 and Section 19.3 on page 353 for further applications of the SFINAE principle.
8.3.2 Type Arguments
Template type arguments are the "values" specified for template type parameters. Most commonly used types can be used as template arguments, but there are two exceptions:
Local classes and enumerations (in other words, types declared in a function definition) cannot be involved in template type arguments. Types that involve unnamed class types or unnamed enumeration types cannot be template type arguments (unnamed classes or enumerations that are given a name through a typedef declaration are OK).
An example illustrates these two exceptions:
template <typename T> class List {
…
};
typedef struct {
double x, y, z;
} Point;
typedef enum { red, green, blue } *ColorPtr;
int main()
{
struct Association
{
int* p;
int* q;
};
List<Assocation*> error1; // ERROR: local type in template argument
List<ColorPtr> error2; // ERROR: unnamed type in template
// argument
List<Point> ok; // OK: unnamed class type named through
// a typedef
}
Although other types can, in general, be used as template arguments, their substitution for the template parameters must lead to valid constructs:
template <typename T>
void clear (T p)
{
*p = 0; // requires that the unary * be applicable to T
}
int main()
{
int a;
clear(a); // ERROR: int doesn't support the unary *
}
8.3.3 Nontype Arguments
Nontype template arguments are the values substituted for nontype parameters. Such a value must be one of the following things:
Another nontype template parameter that has the right type A compile-time constant value of integer (or enumeration) type. This is acceptable only if the corresponding parameter has a type that matches that of the value, or a type to which the value can be implicitly converted (for example, a char can be provided for an int parameter). The name of an external variable or function preceded by the built-in unary & ("address of") operator. For functions and array variables, & can be left out. Such template arguments match nontype parameters of a pointer type. The previous kind of argument but without a leading & operator is a valid argument for a nontype parameter of reference type. A pointer-to-member constant; in other words, an expression of the form &C::m where C is a class type and m is a nonstatic member (data or function). This matches nontype parameters of pointer-to-member type only.
When matching an argument to a parameter that is a pointer or reference, user-defined conversions (constructors for one argument and conversion operators) and derived-to-base conversions are not considered, even though in other circumstances they would be valid implicit conversions. Implicit conversions that make an argument more const or more volatile are fine.
Here are some valid examples of nontype template arguments:
template <typename T, T nontype_param>
class C;
C<int, 33>* c1; // integer type
int a;
C<int*, &a>* c2; // address of an external variable
void f();
void f(int);
C<void (*)(int), &f>* c3;
// name of a function: overload resolution selects
// f(int) in this case; the & is implied
class X {
int n;
static bool b;
};
C<bool&, X::b>* c4; // static class members are acceptable variable
// and function names
C<int X::*, &X::n>* c5;
// an example of a pointer-to-member constant
template<typename T>
void templ_func();
C<void (), &templ_func<double> >* c6;
// function template instantiations are functions too
A general constraint of template arguments is that a compiler or a linker must be able to express their value when the program is being built. Values that aren't known until a program is run (for example, the address of local variables) aren't compatible with the notion that templates are instantiated when the program is built.
Even so, there are some constant values that are, perhaps surprisingly, not currently valid:
Null pointer constants Floating-point numbers String literals
One of the problems with string literals is that two identical literals can be stored at two distinct addresses. An alternative (but cumbersome) way to express templates instantiated over constant strings involves introducing an additional variable to hold the string:
template <char const* str>
class Message;
extern char const hello[] = "Hello World!";
Message<hello>* hello_msg;
Note the need for the extern keyword because otherwise a const array variable would have internal linkage.
See Section 4.3 on page 40 for another example and Section 13.4 on page 209 for a discussion of possible future changes in this area.
Here are few other (less surprising) invalid examples:
template<typename T, T nontype_param>
class C;
class Base {
int i;
} base;
class Derived : public Base {
} derived_obj;
C<Base*, &derived_obj>* err1; // ERROR: derived-to-base conversions are
// not considered
C<int&, base.i>* err2; // ERROR: fields of variables aren't
// considered to be variables
int a[10];
C<int*, &a[0]>* err3; // ERROR: addresses of individual array
// elements aren't acceptable either
8.3.4 Template Template Arguments
A template template argument must be a class template with parameters that exactly match the parameters of the template template parameter it substitutes. Default template arguments of a template template argument are ignored (but if the template template parameter has default arguments, they are considered during the instantiation of the template).
This makes the following example invalid:
#include <list>
// declares:
// namespace std {
// template <typename T,
// typename Allocator = allocator<T> >
// class list;
// }
template<typename T1,
typename T2,
template<typename> class Container>
// Container expects templates with only
// one parameter
class Relation {
public:
…
private:
Container<T1> dom1;
Container<T2> dom2;
};
int main()
{
Relation<int, double, std::list> rel;
// ERROR: std::list has more than one template parameter
…
}
The problem in this example is that the std::list template of the standard library has more than one parameter. The second parameter (which describes a so-called allocator) has a default value, but this is not considered when matching std::list to the Container parameter.
Sometimes, such situations can be worked around by adding a parameter with a default value to the template template parameter. In the case of the previous example, we may rewrite the Relation template as follows:
#include <memory>
template<typename T1,
typename T2,
template<typename T,
typename = std::allocator<T> > class Container>
// Container now accepts standard container templates
class Relation {
public:
…
private:
Container<T1> dom1;
Container<T2> dom2;
};
Clearly this isn't entirely satisfactory, but it enables the use of standard container templates. Section 13.5 on page 211 discusses possible future changes of this topic.
The fact that syntactically only the keyword class can be used to declare a template template parameter is not to be construed as an indication that only class templates declared with the keyword class are allowed as substituting arguments. Indeed, "struct templates" and "union templates" are valid arguments for a template template parameter. This is similar to the observation that (just about) any type can be used as an argument for a template type parameter declared with the keyword class.
8.3.5 Equivalence
Two sets of template arguments are equivalent when values of the arguments are identical one-for-one. For type arguments, typedef names don't matter: It is the type ultimately underlying the typedef that is compared. For integer nontype arguments, the value of the argument is compared; how that value is expressed doesn't matter. The following example illustrates this concept:
template <typename T, int I>
class Mix;
typedef int Int;
Mix<int, 3*3>* p1;
Mix<Int, 4+5>* p2; // p2 has the same type as p1
A function generated from a function template is never equivalent to an ordinary function even though they may have the same type and the same name. This has two important consequences for class members:
A function generated from a member function template never overrides a virtual function. A constructor generated from a constructor template is never a default copy constructor. (Similarly, an assignment generated from an assignment template is never a copy-assignment operator. However, this is less prone to problems because unlike copy constructors, assignment operators are never called implicitly.)
|
8.4 Friends
The basic idea of friend declarations is a simple one: Identify classes or functions that have a privileged connection with the class in which the friend declaration appears. Matters are somewhat complicated, however, by two facts:
A friend declaration may be the only declaration of an entity. A friend function declaration can be a definition.
Friend class declarations cannot be definitions and therefore are rarely problematic. In the context of templates, the only new facet of friend class declarations is the ability to name a particular instance of a class template as a friend:
template <typename T>
class Node;
template <typename T>
class Tree {
friend class Node<T>;
…
};
Note that the class template must be visible at the point where one of its instances is made a friend of a class or class template. With an ordinary class, there is no such requirement:
template <typename T>
class Tree {
friend class Factory; // OK, even if first declaration of Factory
friend class class Node<T>; // ERROR if Node isn't visible
};
Section 9.2.2 on page 125 has more to say about this.
8.4.1 Friend Functions
An instance of a function template can be made a friend by making sure the name of the friend function is followed by angle brackets. The angle brackets can contain the template arguments, but if the arguments can be deduced, the angle brackets can be left empty:
template <typename T1, typename T2>
void combine(T1, T2);
class Mixer {
friend void combine<>(int&, int&);
// OK: T1 = int&, T2 = int&
friend void combine<int, int>(int, int);
// OK: T1 = int, T2 = int
friend void combine<char>(char, int);
// OK: T1 = char T2 = int
friend void combine<char>(char&, int);
// ERROR: doesn't match combine() template
friend void combine<>(long, long) { … }
// ERROR: definition not allowed!
};
Note that we cannot define a template instance (at most, we can define a specialization), and hence a friend declaration that names an instance cannot be a definition.
If the name is not followed by angle brackets, there are two possibilities:
If the name isn't qualified (in other words, it doesn't contain a double colon), it never refers to a template instance. If no matching nontemplate function is visible at the point of the friend declaration, the friend declaration is the first declaration of that function. The declaration could also be a definition. If the name is qualified (it contains ::), the name must refer to a previously declared function or function template. A matching function is preferred over a matching function template. However, such a friend declaration cannot be a definition.
An example may help clarify the various possibilities:
void multiply (void*); // ordinary function
template <typename T>
void multiply(T); // function template
class Comrades {
friend multiply(int) {}
// defines a new function ::multiply(int)
friend ::multiply(void*);
// refers to the ordinary function above;
// not to the multiply<void*> instance
friend ::multiply(int);
// refers to an instance of the template
friend ::multiply<double*>(double*);
// qualified names can also have angle brackets
// but a template must be visible.
friend ::error() {}
// ERROR: a qualified friend cannot be a definition
};
In our previous examples, we declared the friend functions in an ordinary class. The same rules apply when we declare them in class templates, but the template parameters may participate in identifying the function that is to be a friend:
template <typename T>
class Node {
Node<T>* allocate();
…
};
template <typename T>
class List {
friend Node<T>* Node<T>::allocate();
…
};
However, an interesting effect occurs when a friend function is defined in a class template because anything that is only declared in a template isn't a concrete entity until the template is instantiated. Consider the following example:
template <typename T>
class Creator {
friend void appear() { // a new function ::appear(), but it doesn't
… // exist until Creator is instantiated
}
};
Creator<void> miracle; // ::appear() is created at this point
Creator<double> oops; // ERROR: ::appear() is created a second time!
In this example, two different instantiations create two identical definitionsa direct violation of the ODR (see Appendix A).
We must therefore make sure the template parameters of the class template appear in the type of any friend function defined in that template (unless we want to prevent more than one instantiation of a class template in a particular file, but this is rather unlikely). Let's apply this to a variation of our previous example:
template <typename T>
class Creator {
friend void feed(Creator<T>*){ // every T generates a different
… // function ::feed()
}
};
Creator<void> one; // generates ::feed(Creator<void>*)
Creator<double> two; // generates ::feed(Creator<double>*)
In this example, every instantiation of Creator generates a different function. Note that even though these functions are generated as part of the instantiation of a template, the functions themselves are ordinary functions, not instances of a template.
Also note that because the body of these functions is defined inside a class definition, they are implicitly inline. Hence, it is not an error for the same function to be generated in two different translation units. Section 9.2.2 on page 125 and Section 11.7 on page 174 have more to say about this topic.
8.4.2 Friend Templates
Usually when declaring a friend that is an instance of a function or a class template, we can express exactly which entity is to be the friend. Sometimes it is nonetheless useful to express that all instances of a template are friends of a class. This requires a so-called friend template. For example:
class Manager {
template<typename T>
friend class Task;
template<typename T>
friend void Schedule<T>::dispatch(Task<T>*);
template<typename T>
friend int ticket() {
return ++Manager::counter;
}
static int counter;
};
Just as with ordinary friend declarations a friend template can be a definition only if it names an unqualified function name that is not followed by angle brackets.
A friend template can declare only primary templates and members of primary templates. Any partial specializations and explicit specializations associated with a primary template are automatically considered friends too.
|
8.5 Afternotes
The general concept and syntax of C++ templates have remained relatively stable since their inception in the late 1980s. Class templates and function templates were part of the initial template facility. So were type parameters and nontype parameters.
However, there were also some significant additions to the original design, mostly driven by the needs of the C++ standard library. Member templates may well be the most fundamental of those additions. Curiously, only member function templates were formally voted into the C++ standard. Member class templates became part of the standard by an editorial oversight.
Friend templates, default template arguments, and template template parameters are also relatively recent additions to the language. The ability to declare template template parameters is sometimes called higher-order genericity. They were originally introduced to support a certain allocator model in the C++ standard library, but that allocator model was later replaced by one that does not rely on template template parameters. Later, template template parameters came close to being removed from the language because their specification had remained incomplete until very late in the standardization process. Eventually a majority of committee members voted to keep them and their specifications were completed.
|
Chapter 9. Names in Templates
Names are a fundamental concept in most programming languages. They are the means by which a programmer can refer to previously constructed entities. When a C++ compiler encounters a name, it must "look it up" to identify to which entity is being referred. From an implementer's point of view, C++ is a hard language in this respect. Consider the C++ statement x*y; .Ifx and y are the names of variables, this statement is a multiplication, but if x is the name of a type, then the statement declares y as a pointer to an entity of type x.
This small example demonstrates that C++ (like C) is a so-called context-sensitive language: A construct cannot always be understood without knowing its wider context. How does this relate to templates? Well, templates are constructs that must deal with multiple wider contexts: (1) the context in which the template appears, (2) the context in which the template is instantiated, and (3) the contexts associated with the template arguments for which the template is instantiated. Hence it should not be totally surprising that "names" must be dealt with quite carefully in C++.
|
9.1 Name Taxonomy
C++ classifies names in a variety of waysa large variety of ways in fact. To help cope with this abundance of terminology, we provide tables Table 9.1 and Table 9.2, which describe these classifications. Fortunately, you can gain good insight into most C++ template issues by familiarizing yourself with two major naming concepts:
A name is a qualified name if the scope to which it belongs is explicitly denoted using a scoperesolution operator (::) or a member access operator (. or ->). For example, this->count is a qualified name, but count is not (even though the plain count might actually refer to a class member). A name is a dependent name if it depends in some way on a template parameter. For example, std::vector<T>::iterator is a dependent name if T is a template parameter, but it is a nondependent name if T is a known typedef (for example, of int).
Table 9.1. Name Taxonomy (part one)
|
Identifier
|
A name that consists solely of an uninterrupted sequences of letters, underscores (_) and digits. It cannot start with a digit, and some identifiers are reserved for the implementation: You should not introduce them in your programs (as a rule of thumb, avoid leading underscores and double underscores). The concept of "letter" should be taken broadly and includes special universal character names (UCNs) that encode glyphs from nonalphabetical languages.
|
|
Operator-function-id
|
The keyword operator followed by the symbol for an operator for example, operator new and operator [ ]. Many operators have alternative representations. For example, operator & can equivalently be written as operator bitand even when it denotes the unary address of operator.
|
|
Conversion-function-id
|
Used to denote user-defined implicit conversion operatorfor example operator int&, which could also be obfuscated as operator int bitand.
|
|
Template-id
|
The name of a template followed by template arguments enclosed in angle brackets; for example, List<T, int, 0>. (Strictly speaking, the C++ standard allows only simple identifiers for the template name of a template-id. However, this is probably an oversight and an operator-function-id should be allowed too; e.g. operator+<X<int> >.)
|
|
Unqualified-id
|
The generalization of an identifier. It can be any of the above (identifier, operator-function-id, conversion-function-id or template-id) or a "destructor name" (for example, notations like ~Data or ~List<T, T, N>).
|
|
Qualified-id
|
An unqualified-id that is qualified with the name of a class or namespace, or just with the global scope resolution operator. Note that such a name itself can be qualified. Examples are ::X, S::x, Array<T>::y, and ::N::A<T>::z.
|
|
Qualified name
|
This term is not defined in the standard, but we use it to refer to names that undergo so-called qualified lookup. Specifically, this is a qualified-id or an unqualified-id that is used after an explicit member access operator (. or ->). Examples are S::x, this->f, and p->A::m. However, just class_mem in a context that is implicitly equivalent to this->class_mem is not a qualified name: The member access must be explicit.
|
|
Unqualified name
|
An unqualified-id that is not a qualified name. This is not a standard term but corresponds to names that undergo what the standard calls unqualified lookup.
|
Table 9.2. Name Taxonomy (part two)
|
Name
|
Either a qualified or an unqualified name.
|
|
Dependent name
|
A name that depends in some way on a template parameter. Certainly any qualified or unqualified name that explicitly contains a template parameter is dependent. Furthermore, a qualified name that is qualified by a member access operator (. or ->) is dependent if the type of the expression on the left of the access operator depends on a template parameter. In particular, b in this->b is a dependent name when it appears in a template. Finally, the identifier ident in a call of the form ident(x, y, z) is a dependent name if and only if any of the argument expressions has a type that depends on a template parameter.
|
|
Nondependent name
|
A name that is not a dependent name by the above description.
|
It is useful to read through the tables to gain some familiarity with the terms that are sometimes used to describe C++ template issues, but it is not essential to remember the exact meaning of every term. Should the need arise, they can be easily found in the index.
|
9.2 Looking Up Names
There are many small details to looking up names in C++, but we will focus only on a few major concepts. The details are necessary to ensure only that (1) normal cases are treated intuitively, and (2) pathological cases are covered in some way by the standard.
Qualified names are looked up in the scope implied by the qualifying construct. If that scope is a class, then base classes may also be looked up. However, enclosing scopes are not considered when looking up qualified names. The following illustrates this basic principle:
int x;
class B {
public:
int i;
};
class D : public B {
};
void f(D* pd)
{
pd->i = 3; // finds B::i
D::x = 2; // ERROR: does not find ::x in the enclosing scope
}
In contrast, unqualified names are typically looked up in successively more enclosing scopes (although in member function definitions the scope of the class and its base classes is searched before any other enclosing scopes). This is called ordinary lookup. Here is a basic example showing the main idea underlying ordinary lookup:
extern int count; // (1)
int lookup_example(int count) // (2)
{
if (count < 0) {
int count = 1; // (3)
lookup_example(count); // unqualified count refers to (3)
}
return count + ::count; // the first (unqualified) count refers to (2);
} // the second (qualified) count refers to (1)
A more recent twist to the lookup of unqualified names is thatin addition to ordinary lookupthey may sometimes undergo so-called argument-dependent lookup (ADL).
Before proceeding with the details of ADL, let's motivate the mechanism with our perennial max() template:
template <typename T>
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}
Suppose now that we need to apply this template to a type defined in another namespace:
namespace BigMath {
class BigNumber {
…
};
bool operator < (BigNumber const&, BigNumber const&);
…
}
using BigMath::BigNumber;
void g (BigNumber const& a, BigNumber const& b)
{
…
BigNumber x = max(a,b);
…
}
The problem here is that the max() template is unaware of the BigMath namespace, but ordinary lookup would not find the operator < applicable to values of type BigNumber. Without some special rules, this greatly reduces the applicability of templates in the context of C++ namespaces. ADL is the C++ answer to those "special rules."
9.2.1 Argument-Dependent Lookup
ADL applies only to unqualified names that look like they name a nonmember function in a function call. If ordinary lookup finds the name of a member function or the name of a type, then ADL does not happen. ADL is also inhibited if the name of the function to be called is enclosed in parentheses.
Otherwise, if the name is followed by a list of argument expressions enclosed in parentheses, ADL proceeds by looking up the name in namespaces and classes "associated with" the types of the call arguments. The precise definition of these associated namespaces and associated classes is given later, but intuitively they can be thought as being all the namespaces and classes that are fairly directly connected to a given type. For example, if the type is a pointer to a class X, then the associated classes and namespace would include X as well as any namespaces or classes to which X belongs.
The precise definition of the set of associated namespaces and associated classes for a given type is determined by the following rules:
For built-in types, this is the empty set. For pointer and array types, the set of associated namespaces and classes is that of the underlying type. For enumeration types, the associated namespace is the namespace in which the enumeration is declared. For class members, the enclosing class is the associated class. For class types (including union types) the set of associated classes is the type itself, the enclosing class, and any direct and indirect base classes. The set of associated namespaces is the namespaces in which the associated classes are declared. If the class is a class template instantiation, then the types of the template type arguments and the classes and namespaces in which the template template arguments are declared are also included. For function types, the sets of associated namespaces and classes comprise the namespaces and classes associated with all the parameter types and those associated with the return type. For pointer-to-member-of-class-X types, the sets of associated namespaces and classes include those associated with X in addition to those associated with the type of the member. (If it is a pointer-to-member-function type, then the parameter and return types can contribute too.)
ADL then looks up the name in all the associated namespaces as if the name had been qualified with each of these namespaces in turn, except that using-directives are ignored. The following example illustrates this:
// details/adl.cpp
#include <iostream>
namespace X {
template<typename T> void f(T);
}
namespace N {
using namespace X;
enumE{e1};
void f(E) {
std::cout << "N::f(N::E) called\n";
}
}
void f(int)
{
std::cout << "::f(int) called\n";
}
int main()
{
::f(N::e1); // qualified function name: no ADL
f(N::e1); // ordinary lookup finds ::f() and ADL finds N::f(),
} // the latter is preferred
Note that in this example, the using-directive in namespace N is ignored when ADL is performed. Hence X::f() is never even a candidate for the call in main().
9.2.2 Friend Name Injection
A friend function declaration can be the first declaration of the nominated function. If this is the case, then the function is assumed to be declared in the nearest namespace scope (or perhaps the global scope) enclosing the class containing the friend declaration. A relatively controversial issue is whether that declaration should be visible in the scope in which it is "injected." It is mostly a problem with templates. Consider the following example:
template<typename T>
class C {
…
friend void f();
friend void f(C<T> const&);
…
};
void g (C<int>* p)
{
f(); // Is f() visible here?
f(*p); // Is f(C<int> const&) visible here?
}
The trouble is that if friend declarations are visible in the enclosing namespace, then instantiating a class template may make visible the declaration of ordinary functions. Some programmers find this surprising, and the C++ standard therefore specifies that friend declarations do not ordinarily make the name visible in the enclosing scope.
However, there is an interesting programming technique that depends on declaring (and defining) a function in a friend declaration only (see Section 11.7 on page 174). Therefore the standard also specifies that friend functions are found when the class of which they are a friend is among the associated classes considered by ADL.
Reconsider our last example. The call f() has no associated classes or namespaces because there are no arguments: It is an invalid call in our example. However, the call f(*p) does have the associated class C<int> (because this is the type of *p), and the global namespace is also associated (because this is the namespace in which the type of *p is declared). Therefore the second friend function declaration could be found provided the class C<int> was actually fully instantiated prior to the call. To ensure this, it is assumed that a call involving a lookup for friends in associated classes actually causes the class to be instantiated (if not done already).
9.2.3 Injected Class Names
The name of a class is "injected" inside the scope of that class itself and is therefore accessible as an unqualified name in that scope. (However, it is not accessible as a qualified name because this is the notation used to denote the constructors.) For example:
// details/inject.cpp
#include <iostream>
int C;
class C {
private:
int i[2];
public:
static int f() {
return sizeof(C);
}
};
int f()
{
return sizeof(C);
}
int main()
{
std::cout << "C::f() = " <<C::f() << ","
<< " ::f() = " <<::f() << std::endl;
}
The member function C::f() returns the size of type C whereas the function ::f() returns the size of the variable C (in other words, the size of an int object).
Class templates also have injected class names. However, they're stranger than ordinary injected class names: They can be followed by template arguments (in which case they are injected class template names), but if they are not followed by template arguments they represent the class with its parameters as its arguments (or, for a partial specialization, its specialization arguments). This explains the following situation:
template<template<typename> class TT> class X {
};
template<typename T> class C {
Ca; // OK: same as ''C<T> a;''
C<void> b; // OK
X<C> c; // ERROR: C without a template argument list
// does not denote a template
X<::C> d; // ERROR: <: is an alternative token for [
X< ::C> e; // OK: the space between < and :: is required
}
Note how the unqualified name refers to the injected name and is not considered the name of the template if it is not followed by a list of template arguments. To compensate, we can force the name of the template to be found by using the file scope qualifier ::. This works, but we must then be careful not to create a so-called digraph token <:, which is interpreted as a left bracket. Although relatively rare, such errors result in perplexing diagnostics.
|
9.3 Parsing Templates
Two fundamental activities of compilers for most programming languages are tokenizationalso called scanning or lexingand parsing. The tokenization process reads the source code as a sequence of characters and generates a sequence of tokens from it. For example, on seeing the sequence of characters int* p=0;, the "tokenizer" will generate token descriptions for a keyword int,a symbol/operator *, an identifier p, a symbol/operator =, an integer literal 0, and a symbol/operator ;.
A parser will then find known patterns in the token sequence by recursively reducing tokens or previously found patterns into higher level constructs. For example, the token 0 is a valid expression, the combination * followed by an identifier p is a valid declarator, and that declarator followed by "=" followed by the expression "0" is also a valid declarator. Finally, the keyword int is a known type name, and, when followed by the declarator *p=0, you get the initializating declaration of p.
9.3.1 Context Sensitivity in Nontemplates
As you may know or expect, tokenizing is easier than parsing. Fortunately, parsing is a subject for which a solid theory has been developed, and many useful languages are not hard to parse using this theory. However, the theory works best for so-called context-free language, and we have already noted that C++ is context sensitive. To handle this, a C++ compiler will couple a symbol table to the tokenizer and parser: When a declaration is parsed, it is entered in the symbol table. When the tokenizer finds an identifier, it looks it up and annotates the resulting token if it finds a type.
For example, if the C++ compiler sees
x*
the tokenizer looks up x. If it finds a type, the parser sees
identifier, type, x
symbol, *
and concludes that a declaration has started. However, if x is not found to be a type, then the parser receives from the tokenizer
identifier, nontype, x
symbol, *
and the construct can be parsed validly only as a multiplication. The details of these principles are dependent on the particular implementation strategy, but the gist should be there.
Another example of context sensitivity is illustrated in the following expression:
X<1>(0)
If X is the name of a class template, then the previous expression casts the integer 0 to the type X<1> generated from that template. If X is not a template, then the previous expression is equivalent to
(X<1)>0
In other words, X is compared with 1, and the result of that comparisontrue or false, implicitly converted to 1 or 0 in this caseis compared with 0. Although code like this is rarely used, it is valid C++ (and valid C, for that matter). A C++ parser will therefore look up names appearing before a < and treat the < as an angle bracket only if the name is that of a template; otherwise, the < is an ordinary "less than" operator.
This form of context sensitivity is an unfortunate consequence of having chosen angle brackets to delimit template argument lists. Here is another such consequence:
template<bool B>
class Invert {
public:
static bool const result = !B;
};
void g()
{
bool test = B<(1>0)>::result; // parentheses required!
}
If the parentheses in B<(1>0)> were omitted, the "larger than" symbol would be mistaken for the closing of the template argument list. This would make the code invalid because the compiler would read it to be equivalent to ((B<1>))0>::result.
The tokenizer isn't spared problems with the angle-bracket notation either. We have already cautioned (see Section 3.2 on page 27) to introduce whitespace when nesting template-ids, as in
List<List<int> > a;
// ^-- whitespace is not optional!
Indeed, the whitespace between the two closing angle brackets is not optional: Without this whitespace, the two > characters combine into a right shift token >>, and hence are never treated as two separate tokens. This is a consequence of the so-called maximum munch tokenization principle: A C++ implementation must collect as many consecutive characters as possible into a token.
This particular issue is a very common stumbling block for beginning template users. Several C++ compiler implementations have therefore been modified to recognize this situation and treat the >> as two separate > in this particular situation (and with a warning that it is not really valid C++). The C++ committee is also considering mandating this behavior in a revision of the standard (see Section 13.1 on page 205).
Another example of the maximum munch principle is the less known fact that the scope resolution operator (::) must also be used carefully with angle brackets:
class X {
…
};
List<::X> many_X; // SYNTAX ERROR!
The problem in the previous example is that the sequence of characters <: is a so-called digraph
: an alternative representation for the symbol [. Hence, the compiler really sees the equivalent of List[:X> many_X;, which makes no sense at all. Again, the solution is to add some whitespace:
List< ::X> many_X;
// ^-- whitespace is not optional!
9.3.2 Dependent Names of Types
The problem with names in templates is that they cannot always be sufficiently classified. In particular, one template cannot look into another template because the contents of that other template can be made invalid by an explicit specialization (see Chapter 12 for details). The following contrived example illustrates this:
template<typename T>
class Trap {
public:
enum{x}; // (1) x is not a type here
};
template<typename T>
class Victim {
public:
int y;
void poof() {
Trap<T>::x*y; // (2) declaration or multiplication?
}
};
template<>
class Trap<void> { // evil specialization!
public:
typedef int x; // (3) x is a type here
};
void boom(Trap<void>& bomb)
{
bomb.poof();
}
As the compiler is parsing line (2), it must decide whether it is seeing a declaration or a multiplication. This decision in turn depends on whether the dependent qualified name Trap<T>::x is a type name. It may be tempting to look in the template Trap at this point and find that, according to line (1), Trap<T>::x is not a type, which would leave us to believe that line (2) is a multiplication. However, a little later the source corrupts this idea by overriding the generic X<T>::x for the case where T is void. In this case, Trap<T>::x is in fact type int.
The language definition resolves this problem by specifying that in general a dependent qualified name does not denote a type unless that name is prefixed with the keyword typename. If it turns out, after substituting template arguments, that the name is not the name of a type, the program is invalid and your C++ compiler should complain at instantiation time. Note that this use of typename is different from the use to denote template type parameters. Unlike type parameters, you cannot equivalently replace typename with class. The typename prefix to a name is required when the name
Appears in a template Is qualified Is not used as in a list of base class specifications or in a list of member initializers introducing a constructor definition Is dependent on a template parameter
Furthermore, the typename prefix is not allowed unless at least the first three previous conditions hold. To illustrate this, consider the following erroneous example
:
template<typename1 T>
struct S: typename2 X<T>::Base {
S(): typename3 X<T>::Base(typename4 X<T>::Base(0)) {}
typename5 X<T> f() {
typename6 X<T>::C * p; // declaration of pointer p
X<T>::D * q; // multiplication!
}
typename7 X<int>::C * s;
};
struct U {
typename8 X<int>::C * pc;
};
Each occurrence of typenamecorrect or notis numbered with a subscript for easy reference. The first, typename1, indicates a template parameter. The previous rules do not apply to this first use. The second and third typenames are disallowed by the third item in the previous rules. Names of base classes in these two contexts cannot be preceded by typename. However, typename4 is required. Here, the name of the base class is not used to denote what is being initialized or derived from. Instead, the name is part of an expression to construct a temporary X<T>::Base from its argument 0 (a sort of conversion, if you will). The fifth typename is prohibited because the name that follows it, X<T>, is not a qualified name. The sixth occurrence is required if this statement is to declare a pointer. The next line omits the typename keyword and is, therefore, interpreted by the compiler as a multiplication. The seventh typename is optional because it satisfies all the previous rules except the last. Finally, typename8 is prohibited because it is not used inside a template.
9.3.3 Dependent Names of Templates
A problem very similar to the one encountered in the previous section occurs when a name of a template is dependent. In general, a C++ compiler is required to treat a < following the name of a template as the beginning of a template argument list; otherwise, it is a "less than" operator. As is the case with type names, a compiler has to assume that a dependent name does not refer to a template unless the programmer provides extra information using the keyword template:
template<typename T>
class Shell {
public:
template<int N>
class In {
public:
template<int M>
class Deep {
public:
virtual void f();
};
};
};
template<typename T, int N>
class Weird {
public:
void case1(Shell<T>::template In<N>::template Deep<N>* p) {
p->template Deep<N>::f(); // inhibit virtual call
}
void case2(Shell<T>::template In<T>::template Deep<T>& p) {
p.template Deep<N>::f(); // inhibit virtual call
}
};
This somewhat intricate example shows how all the operators that can qualify a name (::, ->, and .) may need to be followed by the keyword template. Specifically, this is the case whenever the type of the name or expression preceding the qualifying operator is dependent on a template parameter, and the name that follows the operator is a template-id (in other words, a template name followed by template arguments in angle brackets). For example, in the expression
p.template Deep<N>::f()
the type of p depends on the template parameter T. Consequently, a C++ compiler cannot look up Deep to see if it is a template, and we must explicitly indicate that Deep is the name of a template by inserting the prefix template. Without this prefix, p.Deep<N>::f() is parsed as ((p.Deep)<N)>f(). Note also that this may need to happen multiple times within a qualified name because qualifiers themselves may be qualified with a dependent qualifier. (This is illustrated by the declaration of the parameters of case1 and case2 in the previous example.)
If the keyword template is omitted in cases such as these, the opening and closing angle brackets are parsed as "less than" and "greater than" operators. However, if the keyword is not strictly needed, it is in fact not allowed at all.
You cannot "just sprinkle" template qualifiers throughout your code.
9.3.4 Dependent Names in Using-Declarations
Using-declarations can bring in names from two places: namespaces and classes. The namespace case is not relevant in this context because there are no such things as namespace templates. Using-declarations that bring in names from classes can, in fact, bring in names only from a base class to a derived class. Such using-declarations behave like "symbolic links" or "shortcuts" in the derived class to the base declaration, thereby allowing the members of the derived class to access the nominated name as if it were actually a member declared in that derived class. A short nontemplate example illustrates the idea better than mere words:
class BX {
public:
void f(int);
void f(char const*);
void g();
};
class DX : private BX {
public:
using BX::f;
};
The previous using-declaration brings in the name f of the base class BX into the derived class DX. In this case, this name is associated with two different declarations, thus emphasizing that we are dealing with a mechanism for names and not individual declarations of such names. Note also that this kind of using-declaration can make accessible an otherwise inaccessible member. The base BX (and thus its members) are private to the class DX, except that the functions BX::f have been introduced in the public interface of DX and are therefore available to the clients of DX. Because using-declarations enable this, the earlier mechanism of access declarations is deprecated in C++ (meaning that future revisions of C++ may not contain the mechanism):
class DX : private BX {
public:
BX::f; // access declaration syntax is deprecated
// use using BX::f instead
};
By now you can probably perceive the problem when a using-declaration brings in a name from a dependent class. Although we know about the name, we don't know whether it's the name of a type, a template, or something else:
template<typename T>
class BXT {
public:
typedef T Mystery;
template<typename U>
struct Magic;
};
template<typename T>
class DXTT : private BXT<T> {
public:
using typename BXT<T>::Mystery;
Mystery* p; // would be a syntax error if not for the typename
};
Again, if we want a dependent name to be brought in by a using-declaration to denote a type, we must explicitly say so by inserting the keyword typename. Strangely, the C++ standard does not provide for a similar mechanism to mark such dependent names as templates. The following snippet illustrates the problem:
template<typename T>
class DXTM : private BXT<T> {
public:
using BXT<T>::template Magic; // ERROR: not standard
Magic<T>* plink; // SYNTAX ERROR: Magic is not a
}; // known template
Most likely this is an oversight in the standard specifications and future revisions will probably make the previous construct valid.
9.3.5 ADL and Explicit Template Arguments
Consider the following example:
namespace N {
class X {
…
};
template<int I> void select(X*);
}
void g (N::X* xp)
{
select<3>(xp); // ERROR: no ADL!
}
In this example, we may expect that the template select() is found through ADL in the call select<3>(xp). However, this is not the case because a compiler cannot decide that xp is a function call argument until it has decided that <3> is a template argument list. Conversely, we cannot decide that <3> is a template argument list until we have found select() to be a template. Because this chicken and egg problem cannot be resolved, the expression is parsed as (select<3)>(xp), which makes no sense.
|
9.4 Derivation and Class Templates
Class templates can inherit or be inherited from. For many purposes, there is nothing significantly different between the template and nontemplate scenarios. However, there is one important subtlety when deriving a class template from a base class referred to by a dependent name. Let's first look at the somewhat simpler case of nondependent base classes.
9.4.1 Nondependent Base Classes
In a class template, a nondependent base class is one with a complete type that can be determined without knowing the template arguments. In other words, the name of this base is denoted using a nondependent name. For example:
template<typename X>
class Base {
public:
int basefield;
typedef int T;
};
class D1: public Base<Base<void> > { // not a template case really
public:
void f() { basefield = 3; } // usual access to inherited member
};
template<typename T>
class D2 : public Base<double> { // nondependent base
public:
void f() { basefield = 7; } // usual access to inherited member
T strange; // T is Base<double>::T, not the template parameter!
};
Nondependent bases in templates behave very much like bases in ordinary nontemplate classes, but there is a slightly unfortunate surprise: When an unqualified name is looked up in the templated derivation, the nondependent bases are considered before the list of template parameters. This means that in the previous example, the member strange of the class template D2 always has the type T corresponding to Base<double>::T (in other words, int). For example, the following function is not valid C++ (assuming the previous declarations):
void g (D2<int*>& d2, int* p)
{
d2.strange = p; // ERROR: type mismatch!
}
This is counterintuitive and requires the writer of the derived template to be aware of names in the nondependent bases from which it deriveseven when that derivation is indirect or the names are private. It would probably have been preferable to place template parameters in the scope of the entity they "templatize."
9.4.2 Dependent Base Classes
In the previous example, the base class is fully determined. It does not depend on a template parameter. This implies that a C++ compiler can look up nondependent names in those base classes as soon as the template definition is seen. An alternativenot allowed by the C++ standardwould consist in delaying the lookup of such names until the template is instantiated. The disadvantage of this alternative approach is that it also delays any error messages resulting from missing symbols until instantiation. Hence, the C++ standard specifies that a nondependent name appearing in a template is looked up as soon as it is encountered. Keeping this in mind, consider the following example:
template<typename T>
class DD : public Base<T> { // dependent base
public:
void f() { basefield = 0; } // (1) problem…
};
template<> // explicit specialization
class Base<bool> {
public:
enum { basefield = 42 }; // (2) tricky!
};
void g (DD<bool>& d)
{
d.f(); // (3) oops?
}
At point (1) we find our reference to a nondependent name basefield: It must be looked up right away. Suppose we look it up in the template Base and bind it to the int member that we find therein. However, shortly after this we override the generic definition of Base with an explicit specialization. As it happens, this specialization changes the meaning of the basefield member to which we already committed! So, when we instantiate the definition of DD::f at point (3), we find that we too eagerly bound the nondependent name at point (1). There is no modifiable basefield in DD<bool> that was specialized at point (2), and an error message should have been issued.
To circumvent this problem, standard C++ says that nondependent names are not looked up in dependent base classes
(but they are still looked up as soon as they are encountered). So, a standard C++ compiler will emit a diagnostic at point (1). To correct the code, it suffices to make the name basefield dependent because dependent names can be looked up only at the time of instantiation, and at that time the exact base specialization that must be explored will be known. For example, at point (3), the compiler will know that the base class of DD<bool> is Base<bool> and that this has been explicitly specialized by the programmer. In this case, our preferred way to make the name dependent is as follows:
// Variation 1:
template<typename T>
class DD1 : public Base<T> {
public:
void f() { this->basefield = 0; } // lookup delayed
};
An alternative consists in introducing a dependency using a qualified name:
// Variation 2:
template<typename T>
class DD2 : public Base<T> {
public:
void f() { Base<T>::basefield = 0; }
};
Care must be taken with this solution, because if the unqualified nondependent name is used to form a virtual function call, then the qualification inhibits the virtual call mechanism and the meaning of the program changes. Nonetheless, there are situations when the first variation cannot be used and this alternative is appropriate:
template<typename T>
class B {
public:
enumE{e1=6,e2=28,e3=496};
virtual void zero(E e = e1);
virtual void one(E&);
};
template<typename T>
class D : public B<T> {
public:
void f() {
typename D<T>::E e; // this->E would not be valid syntax
this->zero(); // D<T>::zero() would inhibit virtuality
one(e); // one is dependent because its argument
} // is dependent
};
Note that the name one in the call one(e) is dependent on the template parameter simply because the type of one of the call's explicit arguments is dependent. Implicitly used default arguments with a type that depends on a template parameter do not count because the compiler cannot verify this until it already has decided the lookupa chicken and egg problem. To avoid subtlety, we prefer to use the this-> prefix in all situations that allow iteven for nontemplate code.
If you find that the repeated qualifications are cluttering up your code, you can bring a name from a dependent base class in the derived class once and for all:
// Variation 3:
template<typename T>
class DD3 : public Base<T> {
public:
using Base<T>::basefield; // (1) dependent name now in scope
void f() { basefield = 0; } // (2) fine
};
The lookup at point (2) succeeds and finds the using-declaration of point (1). However, the using-declaration is not verified until instantiation time and our goal is achieved. There are some subtle limitations to this scheme. For example, if multiple bases are derived from, the programmer must select exactly which one contains the desired member.
|
9.5 Afternotes
The first compiler really to parse template definitions was developed by a company called Taligent in the mid-1990s. Before thatand even after thatmost compilers treated templates as a sequence of tokens to be played back through the parser at instantiation time. Hence no parsing was done, except for a minimal amount sufficient to find the end of a template definition. Bill Gibbons was Taligent's representative to the C++ committee and was the principal advocate for making templates unambiguously parsable. The Taligent effort was not released until the compiler was acquired and completed by Hewlett-Packard (HP), to become the aC++ compiler. Among its competitive advantages, the aC++ compiler was quickly recognized for its high quality diagnostics. The fact that template diagnostics were not always delayed until instantiation time undoubtedly contributed to this perception.
Relatively early during the development of templates, Tom Pennelloa widely recognized parsing expert working for Metawarenoted some of the problems associated with angle brackets. Stroustrup also comments on that topic in [StroustrupDnE] and argues that humans prefer to read angle brackets rather than parentheses. However, other possibilities exist, and Pennello specifically proposed braces (for example, List{::X}) at a C++ standards meeting in 1991 (held in Dallas).
At that time the extent of the problem was more limited because templates nested inside other templatesso-called member templateswere not valid and thus the discussion of Section 9.3.3 on page 132 was largely irrelevant. As a result, the committee declined the proposal to replace the angle brackets.
The name lookup rule for nondependent names and dependent base classes that is described in Section 9.4.2 on page 136 was introduced in the C++ standard in 1993. It was described to the "general public" in Bjarne Stroustrup's [StroustrupDnE] in early 1994. Yet the first generally available implementation of this rule did not appear until early 1997 when HP incorporated it into their aC++ compiler, and by then large amounts of code derived class templates from dependent bases. Indeed, when the HP engineers started testing their implementation, they found that most of the programs that used templates in nontrivial ways no longer compiled.
In particular, all implementations of the STL
broke the rule in many hundredsand sometimes thousandsof places. To ease the transition process for their customers, HP softened the diagnostic associated with code that assumed that nondependent names could be found in dependent base classes as follows. When a nondependent name used in the scope of a class template is not found using the standard rules, aC++ peeks inside the dependent bases. If the name is still not found, a hard error is issued and compilation fails. However, if the name is found in a dependent base, a warning is issued, and the name is marked to be treated as if it were dependent, so that lookup will be reattempted at instantiation time.
The lookup rule that causes a name in nondependent bases to hide an identically named template parameter (Section 9.4.1 on page 135) is an oversight, and it is not impossible that this will be changed in a revision of the standard. In any case, it is probably wise to avoid code with template parameter names that are also used in nondependent base classes.
Andrew Koenig first proposed ADL for operator functions only (which is why ADL is sometimes called Koenig lookup). The motivation was primarily esthetic: explicitly qualifying operator names with their enclosing namespace looks awkward at best (for example, instead of a+b we may need to write N::operator+(a, b)) and having to write using declarations for every operator can lead to unwieldy code. Hence, it was decided that operators would be looked up in the namespaces associated with arguments. ADL was later extended to ordinary function names to accommodate a limited kind of friend name injection and to support a two-phase lookup model for templates and their instantiations (Chapter 10). The generalized ADL rules are also called extended Koenig lookup.
|
Chapter 10. Instantiation
Template instantiation is the process that generates types and functions from generic template definitions.
The concept of instantiation of C++ templates is fundamental but also somewhat intricate. One of the underlying reasons for this intricacy is that the definitions of entities generated by a template are no longer limited to a single location in the source code. The location of the template, the location where the template is used, and the locations where the template arguments are defined all play a role in the meaning of the entity.
In this chapter we explain how we can organize our source code to enable proper template use. In addition, we survey the various methods that are used by the most popular C++ compilers to handle template instantiation. Although all these methods should be semantically equivalent, it is useful to understand basic principles of your compiler's instantiation strategy. Each mechanism comes with its set of little quirks when building real-life software and, conversely, each influenced the final specifications of standard C++.
|
10.1 On-Demand Instantiation
When a C++ compiler encounters the use of a template specialization, it will create that specialization by substituting the required arguments for the template parameters.
This is done automatically and requires no direction from the client code (or from the template definition for that matter). This on-demand instantiation feature sets C++ templates apart from similar facilities in other compiled languages. It is sometimes also called implicit or automatic instantiation.
On-demand instantiation implies that the compiler usually needs access to the full definition (in other words, not just the declaration) of the template and some of its members at the point of use. Consider the following tiny source code file:
template<typename T> class C; // (1) declaration only
C<int>* p = 0; // (2) fine: definition of C<int> not needed
template<typename T>
class C {
public:
void f(); // (3) member declaration
}; // (4) class template definition completed
void g (C<int>& c) // (5) use class template declaration only
{
c.f(); // (6) use class template definition;
} // will need definition of C::f()
At point (1) in the source code, only the declaration of the template is available, not the definition (such a declaration is sometimes called a forward declaration). As is the case with ordinary classes, you do not need the definition of a class template to be in scope to declare pointers or references to this type (as was done at point (2)). For example, the type of the parameter of function g does not require the full definition of the template C. However, as soon as a component needs to know the size of a template specialization or if it accesses a member of such a specialization, the entire class template definition is required to be in scope. This explains why at point (6) in the source code, the class template definition must seen; otherwise, the compiler cannot verify that the member exists and is accessible (not private or protected).
Here is another expression that needs the instantiation of the previous class template because the size of C<void> is needed:
C<void>* p = new C<void>;
In this case, instantiation is needed so that the compiler can determine the size of C<void>.You might observe that for this particular template, the type of the argument X substituted for T will not influence the size of the template because in any case, C<X> is an empty class. However, a compiler is not required to detect this. Furthermore, instantiation is also needed in this example to determine whether C<void> has an accessible default constructor and to ensure C<void> does not declare private operators new or delete.
The need to access a member of a class template is not always very explicitly visible in the source code. For example, C++ overload resolution requires visibility into class types for parameters of candidate functions:
template<typename T>
class C {
public:
C(int); // a constructor that can be called with a single parameter
}; // may be used for implicit conversions
void candidate(C<double> const&); // (1)
void candidate(int) {} // (2)
int main()
{
candidate(42); // both previous function declarations can be called
}
The call candidate(42) will resolve to the overloaded declaration at point (2). However, the declaration at point (1) could also be instantiated to check whether it is a viable candidate for the call (it is in this case because the one-argument constructor can implicitly convert 42 to an rvalue of type C<double>). Note that the compiler is allowed (but not required) to perform this instantiation if it can resolve the call without it (as could be the case in this example because an implicit conversion would not be selected over an exact match). Note also that the instantiation of C<double> could trigger an error, which may be surprising.
|
10.2 Lazy Instantiation
The examples so far illustrate requirements that are not fundamentally different from the requirements when using nontemplate classes. Many uses require a class type to be complete. For the template case, the compiler will generate this complete definition from the class template definition.
A pertinent question now arises How much of the template is instantiated? A vague answer is the following: Only as much as is really needed. In other words, a compiler should be "lazy" when instantiating templates. Let's look at exactly what this laziness entails.
When a class template is implicitly instantiated, each declaration of its members is instantiated as well, but the corresponding definitions are not. There are a few exceptions to this. First, if the class template contains an anonymous union, the members of that union's definition are also instantiated.
The other exception occurs with virtual member functions. Their definitions may or may not be instantiated as a result of instantiating a class template. Many implementations will, in fact, instantiate the definition because the internal structure that enables the virtual call mechanism requires the virtual functions actually to exist as linkable entities.
Default function call arguments are considered separately when instantiating templates. Specifically, they are not instantiated unless there is a call to that function (or member function) that actually makes use of the default argument. If, on the other hand, that function is called with explicit arguments that override the default, then the default arguments are not instantiated.
Let's put together an example that illustrates all these issues:
// details/lazy.cpp
template <typename T>
class Safe {
};
template <int N>
class Danger {
public:
typedef char Block[N]; // would fail for N<=0
};
template <typename T, int N>
class Tricky {
public:
virtual ~Tricky() {
}
void no_body_here(Safe<T> = 3);
void inclass() {
Danger<N> no_boom_yet;
}
// void error() { Danger<0> boom; }
// void unsafe(T (*p)[N]);
T operator->();
// virtual Safe<T> suspect();
struct Nested {
Danger<N> pfew;
};
union { // anonymous union
int align;
Safe<T> anonymous;
};
};
int main()
{
Tricky<int, 0> ok;
}
First consider the previous example without the function main(). A standard C++ compiler normally compiles the template definitions to check the syntax and general semantic constraints. It will, however, "assume the best" when checking constraints involving template parameters. For example, the parameter N in the member typedef for Block could be zero of negative (which would be invalid), but it is assumed that this isn't the case. Similarly, the default argument specification (= 3) on the declaration of the member no_body_here() is suspicious because the template Safe isn't initializable with an integer, but the assumption is that the default argument won't actually be needed for the generic definition of Safe<T>. If it weren't commented out, the member error() would trigger an error while the template is compiled because the use of Danger<0> requires a complete definition of the class Danger<0>, and generating that class runs into an attempt to typedef an array with zero elements! This is the case even though the member error() may not be used and therefore may not be instantiated. The error is triggered during the processing of the generic template. The declaration of the member unsafe(T (*p) [N]), in contrast, is not a problem when N is still an unsubstituted template parameter.
Now let's analyze what happens when we add the function main(). It causes the compiler to substitute int for T and 0 for N in the template Tricky. Not all the member definitions will be needed, but the default constructor (implicitly declared in this case) and the destructor are definitely called, and hence their definitions must be available somehow (which is the case in our example). In practice, the definitions of virtual members should also be provided; otherwise, linker errors are likely to occur. This may have been a problem if we had uncommented the declaration of the virtual member suspect() for which no definition was provided. The definitions of the members inclass() and struct Nested would need the complete type Danger<0> (which contains an invalid typedef as we discussed earlier) but because these definitions are not used, they are not generated, and no error is triggered. However, all the member declarations are generated, and these could contain invalid types as the result of our substitution. For example, if we uncommented the declaration of unsafe(T (*p) [N]), we would again create an array type with zero elements, and this time it would be an error. Similarly, had the member anonymous been declared with type Danger<N> instead of Safe<T>, an error would be triggered because type Danger<0> cannot be completed.
Finally, we need to take note of operator->. Normally, this operator must return a pointer type or another class type to which operator-> applies. This suggests that the completion of Tricky<int, 0> triggers an error because it declares a return type of int for operator->. However, because certain natural class template definitions
trigger these kinds of definitions, the language rule was made more flexible. A user-defined operator-> must return only a type to which another (for example, builtin) operator-> applies if that operator is actually selected by the overload resolution rules. This is true even outside templates (although it is less useful in those contexts). Hence, the declaration here triggers no error, even though int is subsituted for the return type.
|
10.3 The C++ Instantiation Model
Template instantiation is the process of obtaining a regular class or function from a corresponding template entity by appropriately substituting the template parameters. This may sound fairly straightforward, but in practice many details need to be formally established.
10.3.1 Two-Phase Lookup
In Chapter 9 we saw that dependent names cannot be resolved when parsing templates. Instead, they are looked up again at the point of instantiation. Nondependent names, however, are looked up early so that many errors can be diagnosed when the template is first seen. This leads to the concept of two-phase lookup
: The first phase is the parsing of a template, and the second phase is its instantiation.
During the first phase, nondependent names are looked up while the template is being parsed using both the ordinary lookup rules and, if applicable, the rules for argument-dependent lookup (ADL). Unqualified dependent names (which are dependent because they look like the name of a function in a function call with dependent arguments) are also looked up that way, but the result of the lookup is not considered complete until an additional lookup is performed when the template is instantiated.
During the second phase, which occurs when templates are instantiated at a point called the point of instantiation (POI), dependent qualified names are looked up (with the template parameters replaced with the template arguments for that specific instantiation), and an additional ADL is performed for the unqualified dependent names.
10.3.2 Points of Instantiation
We have already illustrated that there are points in the source of template clients where a C++ compiler must have access to the declaration or the definition of a template entity. A point of instantiation (POI) is created when a code construct refers to a template specialization in such a way that the definition of the corresponding template needs to be instantiated to create that specialization. The POI is a point in the source where the substituted template could be inserted. For example:
class MyInt {
public:
MyInt(int i);
};
MyInt operator - (MyInt const&);
bool operator > (MyInt const&, MyInt const&);
typedef MyInt Int;
template<typename T>
void f(T i)
{
if (i>0) {
g(-i);
}
}
// (1)
void g(Int)
{
// (2)
f<Int>(42); // point of call
// (3)
}
// (4)
When a C++ compiler sees the call f<Int>(42), it knows the template f will need to be instantiated for T substituted with MyInt: A POI is created. Points (2) and (3) are very close to the point of call, but they cannot be POIs because C++ does not allow us to insert the definition of ::f<Int>(Int) there. The essential difference between point (1) and point (4) is that at point (4) the function g(Int) is visible, and hence the template-dependent call g(-i) can be resolved. However, if point (1) were the POI, then that call could not be resolved because g(Int) is not yet visible. Fortunately, C++ defines the POI for a reference to a nonclass specialization to be immediately after the nearest namespace scope declaration or definition that contains that reference. In our example, this is point (4).
You may wonder why this example involved the type MyInt rather than simple int. The answer lies in the fact that the second lookup performed at the POI is only an ADL. Because int has no associated namespace, the POI lookup would therefore not take place and would not find function g. Hence, if you were to replace the typedef for Int with
typedef int Int;
the previous example should no longer compile.
For class specializations, the situation is different, as the following example illustrates:
template<typename T>
class S {
public:
T m;
};
// (5)
unsigned long h()
{
// (6)
return (unsigned long)sizeof(S<int>);
// (7)
}
// (8)
Again, the function scope points (6) and (7) cannot be POIs because a definition of a namespace scope class S<int> cannot appear there (and templates cannot appear in function scope). If we were to follow the rule for nonclass instances, the POI would be at point (8), but then the expression sizeof(S<int>) is invalid because the size of S<int> cannot be determined until point (8) is reached. Therefore, the POI for a reference to a generated class instance is defined to be the point immediately before the nearest namespace scope declaration of definition that contains the reference to that instance. In our example, this is point (5).
When a template is actually instantiated, the need for additional instantiations may appear. Consider a short example:
template<typename T>
class S {
public:
typedef int I;
};
// (1)
template<typename T>
void f()
{
S<char>::I var1 = 41;
typename S<T>::I var2 = 42;
}
int main()
{
f<double>();
}
// (2): (2a), (2b)
Our preceding discussion already established that the POI for f<double> is at point (2). The function template f() also refers to the class specialization S<char> with a POI that is therefore at point (1). It references S<T> too, but because this is still dependent, we cannot really instantiate it at this point. However, if we instantiate f<double> at point (2), we notice that we also need to instantiate the definition of S<double>. Such secondary or transitive POIs are defined slightly differently. For nonclass entities, the secondary POI is exactly the same as the primary POI. For class entities, the secondary POI immediately precedes (in the nearest enclosing namespace scope) the primary POI. In our example, this means that the POI of f<double> can be placed at point (2b), and just before itat point (2a)is the secondary POI for S<double>. Note how this differs from the POI for S<char>.
A translation unit usually contains multiple POIs for the same instance. For class template instances, only the first POI in each translation unit is retained, and the subsequent ones are ignored (they are not really considered POIs). For nonclass instances, all POIs are retained. In either case, the ODR requires that the instantiations occurring at any of the retained POIs be equivalent, but a C++ compiler does not need to verify and diagnose violations of this rule. This allows a C++ compiler to pick just one nonclass POI to perform the actual instantiation without worrying that another POI might result in a different instantiation.
In practice, most compilers delay the actual instantiation of noninline function templates to the end of the translation unit. This effectively moves the POIs of the corresponding template specializations to the end of the translation unit. The intention of the C++ language designers was for this to be a valid implementation technique, but the standard does not make this clear.
10.3.3 The Inclusion and Separation Models
Whenever a POI is encountered, the definition of the corresponding template must somehow be accessible. For class specializations this means that the class template definition must have been seen earlier in the translation unit. For nonclass POIs this is also possible, and typically nonclass template definitions are simply added to header files that are #included into the translation unit. This source model for template definitions is called the inclusion model, and at the time of this writing it is by far the most popular approach.
For nonclass POIs an alternative exists: The nonclass template can be declared using export and defined in another translation unit. This is known as the separation model. The following code excerpt illustrates this with our perennial max() template:
// Translation unit 1:
#include <iostream>
export template<typename T>
T const& max (T const&, T const&);
int main()
{
std::cout << max(7, 42) << std::endl; // (1)
}
// Translation unit 2:
export template<typename T>
T const& max (T const& a, T const& b)
{
return a<b?b:a; // (2)
}
When compiling the first file, a compiler will notice the POI for T substituted with int created by the statement at point (1). The compilation system must then make sure that the definition in the second file is instantiated to satisfy that POI.
Looking Across Translation Units
Suppose the first file just shown (translation unit 1) is rewritten as follows:
// Translation unit 1:
#include <iostream>
export template<typename T> T const& max(T const&, T const&);
namespace N {
class I {
public:
I(int i): v(i) {}
int v;
};
bool operator < (I const& a, I const& b) {
return a.v<b.v;
}
}
int main()
{
std::cout << max(N::I(7), N::I(42)).v << std::endl; // (3)
}
The POI created at point (3) again requires the definition in the second file (translation unit 2). However, this definition uses the < operator which now refers to the overloaded operator declared in translation unit 1 and which is not visible in translation unit 2. For this to work, it is clear that the instantiation process needs to refer to two different declaration contexts.
The first context is the one in which the template is defined, and the second context is the one in which type I is declared. To involve these two contexts, names in templates are therefore looked up in two phases as explained in Section 10.3.1 on page 146.
The first phase occurs when templates are parsed (in other words, when a C++ compiler first sees the template definition). At this stage, nondependent names are looked up using both the ordinary lookup rules and the ADL rules. In addition, unqualified names of functions that are dependent (because their arguments are dependent) are looked up using the ordinary lookup rules, but the result is memorized without attempting overload resolutionthis is done after the second phase.
The second phase occurs at the point of instantiation. At this point, dependent qualified names are looked up using both ordinary and argument-dependent lookup rules. Dependent unqualified names (which were looked up using ordinary lookup rules during the first phase) are now looked up using ADL rules only, and the result of the ADL is then combined with the result of the ordinary lookup that occurred during the first phase. It is this combined set that is used to select the called function through overload resolution.
Although this two-phase lookup mechanism seems essential to enable the separation model, it is also the mechanism used with the inclusion model. However, many early implementations of the inclusion model delayed all lookups until the point of instantiation.
10.3.5 Examples
A few examples illustrate more effectively the effect of what we just described. Our first example is a simple case of the inclusion model:
template<typename T>
void f1(T x)
{
g1(x); // (1)
}
void g1(int)
{
}
int main()
{
f1(7); // ERROR: g1 not found!
} // (2) POI for f1<int>(int)
The call f1(7) creates a point of instantiation for f1<int>(int) just outside of main() function (at point (2)). In this instantiation, the key issue is the lookup of function g1. When the definition of the template f1 is first encountered, it is noted that the unqualified name g1 is dependent because it is the name of a function in a function call with dependent arguments (the type of the argument x depends on the template parameter T). Therefore, g1 is looked up at point (1) using ordinary lookup rules; however, no g1 is visible at this point. At point (2), the POI, the function is looked up again in associated namespaces and classes, but the only argument type is int, and it has no associated namespaces and classes. Therefore, g1 is never found even though ordinary lookup at the POI would have found g1.
The second example demonstrates how the separation model can lead to overload ambiguities across translation units. The example consists of three files (one of which is a header file):
// File common.hpp:
export template<typename T>
void f(T);
class A {
};
class B {
};
class X {
public:
operator A() { return A(); }
operator B() { return B(); }
};
// File a.cpp:
#include "common.hpp"
void g(A)
{
}
int main()
{
f<X>(X());
}
// File b.cpp:
#include "common.hpp"
void g(B)
{
}
export template<typename T>
void f(T x)
{
g(x);
}
The main() function calls f<X>(X()) in file a.cpp which resolves to the exported template defined in file b.cpp. The call g(x) is therefore instantiated with an argument of type X. Function g() is looked up twice: once using ordinary lookup in file b.cpp (when the template is parsed) and once using ADL in file a.cpp (where the template is instantiated). The first lookup finds g(B), and the second lookup finds g(A). Both are viable functions through a user-defined conversion, and hence the call is really ambiguous.
Note that in file b.cpp the call g(x) does not seem ambiguous at all. It is the two-phase lookup mechanism that brings in possibly unexpected candidate functions. Extreme care should therefore be taken when writing and documenting exported templates.
|
10.4 Implementation Schemes
In this section we review some ways in which popular C++ implementations support the inclusion model. All these implementations rely on two classic components: a compiler and a linker. The compiler translates source code to object files, which contain machine code with symbolic annotations (cross-referencing other object files and libraries). The linker creates executable programs or libraries by combining the object files and resolving the symbolic cross-references they contain. In what follows, we assume such a model even though it is entirely possible (but not popular) to implement C++ in other ways. For example, you could imagine a C++ interpreter.
When a class template specialization is used in multiple translation units, a compiler will repeat the instantiation process in every translation unit. This poses very few problems because class definitions do not directly create low-level code. They are used only internally by a C++ implementation to verify and interpret various other expressions and declarations. In this regard, the multiple instantiations of a class definition are not materially different from the multiple inclusions of a class definitiontypically through header file inclusionin various translation units.
However, if you instantiate a (noninline) function template, the situation may be different. If you were to provide multiple definitions of an ordinary noninline function, you would violate the ODR. Assume, for example, that you compile and link a program consisting of the following two files:
// File a.cpp:
int main()
{
}
// File b.cpp:
int main()
{
}
C++ compilers will compile each module separately without any problems because indeed they are valid C++ translation units. However, your linker will most likely protest if you try to link the two together. Duplicate definitions are not allowed.
In contrast, consider the template case:
// File t.hpp:
// common header (inclusion model)
template<typename T>
class S {
public:
void f();
};
template<typename T>
void S::f() // member definition
{
}
void helper(S<int>*);
// File a.cpp:
#include "t.hpp"
void helper(S<int>* s)
{
s->f(); // (1) first point of instantiation of S::f
}
// File b.cpp:
#include "t.hpp"
int main()
{
S<int> s;
helper(&s);
s.f(); // (2) second point of instantiation of S::f
}
If the linker treats instantiated members of templates just like it does ordinary functions or member functions, the compiler needs to ensure that it generates code at only one of the two POIs: at points (1) or (2), but not both. To achieve this, a compiler has to carry information from one translation unit to the other, and this is something C++ compilers were never required to do prior to the introduction of templates. In what follows, we discuss the three broad classes of solutions that are en vogue among C++ implementers.
Note that the same problem occurs with all linkable entities produced by template instantiation: instantiated function templates and member function templates, as well as instantiated static data members.
10.4.1 Greedy Instantiation
The first C++ compilers that popularized greedy instantiation were produced by a company called Borland. It has grown to be the most commonly used technique among the various C++ systems, and in particular it is almost universally the mechanism of choice in development environments for Microsoft Windows-based personal computers.
Greedy instantiation assumes that the linker is aware that certain entitieslinkable template instantiations in particularmay in fact appear in duplicate across the various object files and libraries. The compiler will typically mark these entities in a special way. When the linker finds multiple instances, it keeps one and discards all the others. There is not much more to it than that.
In theory, greedy instantiation has some serious drawbacks:
The compiler may be wasting time on generating and optimizing N instantiations, of which only one will be kept. Linkers typically do not check that two instantiations are identical because some insignificant differences in generated code can validly occur for multiple instances of one template specialization. These small differences should not cause the linker to fail. (These differences could result from tiny differences in the state of the compiler at the instantiation times.) However, this often also results in the linker not noticing more substantial differences, such as when one instantiation was compiled for maximum performance whereas the other was compiled for most convenient debugging. The sum of all the object files could potentially be much larger than with alternatives because the same code may be duplicated many times.
In practice, these shortcomings do not seem to have caused major problems. Perhaps this is because greedy instantiation contrasts very favorably with the alternatives in one important aspect: The traditional source-object dependency is preserved. In particular, one translation unit generates but one object file, and each object file contains compiled code for all the linkable definitions in the corresponding source file (which includes the instantiated definitions).
Finally, it may be worth noting that the linker mechanism that allows duplicate definitions of linkable entities is also typically used to handle duplicate spilled inlined functions
and virtual function dispatch tables.
If this mechanism is not available, the alternative is usually to emit these items with internal linkage, at the expense of generating larger code.
10.4.2 Queried Instantiation
The most popular implementation in this category is provided by a company called Sun Microsystems, starting with release 4.0 of their C++ compiler. Queried instantiation is conceptually remarkably simple and elegant and yet it is chronologically the most recent class of instantiation schemes that we review here. In this scheme, a database shared by the compilations of all translation units participating in a program is maintained. This database keeps track of which specializations have been instantiated and on what source code they depend. The generated specializations themselves are typically stored with this information in the database. Whenever a point of instantiation for a linkable entity is encountered, one of three things can happen:
No specialization is available: In this case, instantiation occurs, and the resulting specialization is entered in the database. A specialization is available but is out of date because source changes have occurred since it was generated. Here, too, instantiation occurs, but the resulting specialization replaces the one previously stored in the database. An up-to-date specialization is available in the database. Nothing needs to be done.
Although conceptually simple, this design presents a few implementation challenges:
It is not trivial to maintain correctly the dependencies of the database contents with respect to the state of the source code. Although it is not incorrect to mistake the third case for the second, doing so increases the amount of work done by the compiler (and hence overall build time). It is quite common to compile multiple source files concurrently. Hence, an industrial-strength implementation needs to provide the appropriate amount of concurrency control in the database.
Despite these challenges, the scheme can be implemented quite efficiently. Furthermore, there are no obvious pathological cases that would make this solution scale poorly, in contrast, for example, with greedy instantiation, which may lead to a lot of wasted work.
The use of a database may also present some problems to the programmer, unfortunately. The origin of most of these problems lies in that fact that the traditional compilation model inherited from most C compilers no longer applies: A single translation unit no longer produces a single stand-alone object file. Assume, for example, that you wish to link your final program. This link operation needs not only the contents of each of the object files associated with your various translation units, but also the object files stored in the database. Similarly, if you create a binary library, you need to ensure that the tool that creates that librarytypically a linker or an archiveris aware of the contents of the database. More generally, any tool that operates on object files may need to be made aware of the database contents. Many of these problems can be alleviated by not storing the instantiations in the database, but instead by emitting the object code in the object file that caused the instantiation in the first place.
Libraries present yet another challenge. A number of generated specializations may be packaged in a library. When the library is added to another project, that project's database may need to be made aware of the instantiations that are already available. If not, and if the project creates some of its own points of instantiation for the specializations present in the library, duplicate instantiation may occur. A possible strategy to deal with such situations is to use the same linker technology that enables greedy instantiation: Make the linker aware of generated specializations and have it weed out duplicates (which should nonetheless occur much less frequently than with greedy instantiation). Various other subtle arrangements of sources, object files, and libraries can lead to frustrating problems such as missing instantiations because the object code containing the required instantiation was not linked in the final executable program. Such problems should not be construed as shortcomings of the queried instantiation approach but rather should be taken as a solid argument against complex and subtle software build environments.
10.4.3 Iterated Instantiation
The first compiler to support C++ templates was Cfront 3.0a direct descendant of the compiler that Bjarne Stroustrup wrote to develop the language.
An inflexible constraint on Cfront was that it had to be very portable from platform to platform, and this meant that it (1) used the C language as a common target representation across all target platforms and (b) used the local target linker. In particular, this implied that the linker was not aware of templates. In fact, Cfront emitted template instantiations as ordinary C functions, and therefore it had to avoid duplicate instantiations. Although the Cfront source model was different from the standard inclusion and separation models, its instantiation strategy can be adapted to fit the inclusion model. As such, it also merits recognition as the first incarnation of iterated instantiation. The Cfront iteration can be described as follows:
-
Compile the sources without instantiating any required linkable specializations.
-
Link the object files using a prelinker.
-
The prelinker invokes the linker and parses its error messages to determine whether any are the result of missing instantiations. If so, the prelinker invokes the compiler on sources that contain the needed template definitions, with options to generate the missing instantiations.
-
Repeat step 3 if any definitions are generated.
The need to iterate step 3 is prompted by the observation that the instantiation of one linkable entity may lead to the need for another such entity that was not yet instantiated. Eventually the iteration will "converge," and the linker will succeed in building a complete program.
The drawbacks of the original Cfront scheme are quite severe:
The perceived time to link is augmented not only by the prelinker overhead but also by the cost of every required recompilation and relinking. Some users of Cfront-based systems reported link times of "a few days" compared with "about an hour" with the alternative schemes reported earlier. Diagnostics (errors, warnings) are delayed until link time. This is especially painful when linking becomes expensive and the developer must wait hours just to find out about a typo in a template definition. Special care must be taken to remember where the source containing a particular definition is located (step 1). Cfront in particular used a central repository, which had to deal with some of the challenges of the central database in the queried instantiation approach. In particular, the original Cfront implementation was not engineered to support concurrent compilations.
Despite these shortcomings, the iteration principle was refined for the two compilation systems that would later pioneer the more advanced C++ template features
: the Edison Design Group's (EDG) implementation and HP's aC++.
In what follows, we expand on the technique developed by EDG to demonstrate its C++ front-end technology.
EDG's iteration enables two-way communication between the prelinker and the various compilation steps: The prelinker can direct instantiations performed for a particular translation unit through an instantiation request file, and the compiler can notify the prelinker about possible points of instantiation either by embedding information in the object files or by producing separate template information files. The instantiation request files and the template information files have names that correspond to the name of the file being compiled, but with suffixes .ii and .ti respectively. The iteration works as follows:
-
While compiling the source of a translation unit, the EDG compiler reads the corresponding .ii file if one exists and creates the instantiations directed therein. At the same time, it writes which points of instantiation it could have honored to the object file resulting from this compilation or to a separate .ti file. It also writes how this file is compiled.
-
The link step is intercepted by the prelinker, which examines the object files and corresponding .ti files that participate in the link step. For each instantiation that has not yet been generated, the required directive is added to a .ii file corresponding to a translation unit that can honor the directive.
-
If any .ii files are modified, the prelinker reinvokes the compiler (step 1) for the corresponding sources files, and the prelinker iteration repeats.
-
When closure is been achieved, a single actual link step is performed.
This scheme addresses the issue of concurrent builds by maintaining global information on a pertranslation-unit basis. The perceived link time can still be significantly higher than with greedy and queried instantiation, but because no actual linking is performed, the growth is much less catastrophic. More important, because the prelinker maintains global consistency among the .ii files, these files can be reused in the next build cycle. Specifically, after having made some changes to the source, the programmer restarts a build of the files affected by the modifications. Each resulting compilation immediately instantiates the specializations requested by the .ii files that lingered from the previous compilation of that file and chances are good that the prelinker will not need to trigger additional recompiles at link time.
In practice, EDG's scheme works quite well, and, although a build "from scratch" is typically more time-consuming than the alternative schemes, subsequent build times are quite competitive.
|
10.5 Explicit Instantiation
It is possible to create explicitly a point of instantiation for a template specialization. The construct that achieves this is called an explicit instantiation directive. Syntactically, it consists of the keyword template followed by a declaration of the specialization to be instantiated. For example:
template<typename T>
void f(T) throw(T)
{
}
// four valid explicit instantiations:
template void f<int>(int) throw(int);
template void f<>(float) throw(float);
template void f(long) throw(long);
template void f(char);
Note that every instantiation directive is valid. Template arguments can be deduced (see Chapter 11), and exception specifications can be omitted. If they are not omitted, they must match the one of the template.
Members of class templates can also be explicitly instantiated in this way:
template<typename T>
class S {
public:
void f() {
}
};
template void S<int>::f();
template class S<void>;
Furthermore, all the members of a class template specialization can be explicitly instantiated by explicitly instantiating the class template specialization.
Many early C++ compilation systems did not have automatic instantiation capabilities when they first implemented support for templates. Instead, some systems required that the function template specializations used by a program be manually instantiated in a single location. This manual instantiation usually involved implementation-specific #pragma directives.
The C++ standard therefore codified this practice by specifying a clean syntax for it. The standard also specifies that there can be at most one explicit instantiation of a certain template specialization in a program. Furthermore, if a template specialization is explicitly instantiated, it should not be explicitly specialized, and vice versa.
In the original context of manual instantiations, these limitations may seem harmless, but in current practice they cause some grief.
First, consider a library implementer who releases a first version of a function template:
// File toast.hpp:
template<typename T>
void toast(T const& x)
{
…
}
Client code is free to include this header and explicitly instantiate its template:
// Client code:
#include "toast.hpp"
template void toast(float);
Unfortunately, if the library writer decides to specialize toast<float> explicitly, the client code becomes invalid. This is even more delicate when the library is a standard library implemented by different vendors. Some may explicitly specialize some standard templates, whereas others may not (or may specialize different specializations). The client code can therefore not specify the explicit instantiation of library components in a portable manner.
At the time of this writing (2002), the C++ standardization committee appears inclined to state that if an explicit instantiation directive follows an explicit specialization for the same entity, then the directive is without effect. (The final decision in this matter is still pending and may not occur if it appears technically infeasible.)
A second challenge with the current limitations on explicit template instantiation stems from their use as a means to improve compilation times. Indeed, many C++ programmers have observed that automatic template instantiation has a nontrivial negative impact on build times. A technique to improve build times consists in manually instantiating certain template specializations in a single location and inhibiting the instantiation in all other translation units. The only portable way to ensure this inhibition is not to provide the template definition except in the translation unit where it is explicitly instantiated. For example:
// Translation unit 1:
template<typename T> void f(); // no definition: prevents instantiation
// in this translation unit
void g()
{
f<int>();
}
// Translation unit 2:
template<typename T> void f()
{
}
template void f<int>(); // manual instantiation
void g();
int main()
{
g();
}
This solution works well, but it requires control of the source code that provides the template interface. Often, this is not the case. The source code providing the template cannot be modified and always provides the definition of the templates.
One "trick" that is sometimes used is to declare a template as specialized in all translation units (which does inhibit the automatic instantiation of that specialization) except in the translation unit in which that specialization is explicitly instantiated. To illustrate this, let's modify our previous example to include a definition for the template:
// Translation unit 1:
template<typename T> void f()
{
}
template<> void f<int>(); // declared but not defined
void g() {
f<int>();
}
// Translation unit 2:
template<typename T> void f()
{
}
template void f<int>(); // manual instantiation
void g();
int main()
{
g();
}
Unfortunately, this assumes that the object code for a call to an explicitly specialized specialization is identical to a call to the matching generic specialization. This assumption is not correct. Several C++ compilers generate different mangled names for the two entities.
With these compilers, the code does not link to a complete executable program.
Some compilers provide an extension to indicate that a template specialization should not be instantiated in that translation unit. A popular (but nonstandard) syntax consists in prepending the keyword extern before an explicit instantiation directive that would otherwise trigger the instantiation. The first file in our last example can be rewritten as follows for compilers supporting that extension:
// Translation unit 1:
template<typename T> void f()
{
}
extern template void f<int>(); // declared but not defined
void g()
{
f<int>();
}
|
10.6 Afternotes
This chapter deals with two related but different issues: the C++ template compilation models and various C++ template instantiation mechanisms.
The compilation model determines the meaning of a template at various stages of the translation of a program. In particular, it determines what the various constructs in a template mean when it is instantiated. Name lookup is an essential ingredient of the compilation model of course. When we talk about the inclusion model and the separation model, we talk about compilation models. These models are part of the language definition.
The instantiation mechanisms are the external mechanisms that allow C++ implementations to create instantiations correctly. These mechanisms may be constrained by requirements of the linker and other software building tools.
However, the original (Cfront) implementation of templates transcended these two concepts. It created new translation units for the instantiation of templates using a particular convention for the organization of source files. The resulting translation unit was then compiled using what is essentially the inclusion model (although the C++ name lookup rules were substantially different back then). So although Cfront did not implement "separate compilation" of templates, it managed to create an illusion of separate compilation by creating implicit inclusions. Various later implementations provided a somewhat similar implicit inclusion mechanism by default (Sun Microsystems) or as an option (HP, EDG) to provide some amount of compatibility with existing code developed for Cfront.
An example illustrates the details of the Cfront implementation scheme:
// File template.hpp:
template<class T> // Cfront doesn't know typename
void f(T);
// File template.cpp:
template<class T> // Cfront doesn't know typename
void f(T)
{
}
// File app.hpp:
class App {
…
};
// File main.cpp:
#include "app.hpp"
#include "template.hpp"
int main()
{
App a;
f(a);
}
At link time, Cfront's iterated instantiation scheme then creates a new translation unit including files it expects to contain the implementation of the templates it found in header files. Cfront's convention for this is to replace the .h (or similar) suffix of header files by .c (or one of a few other suffixes like .C or .cpp). In this case, the generated translation unit becomes
// File main.cpp:
#include "template.hpp"
#include "template.cpp"
#include "app.hpp"
static void _dummy_(App a1)
{
f(a1);
}
This translation unit is then compiled with a special option to disable the code generation of any entity defined in an included file. This prevents the inclusion of template.cpp (which was presumably already compiled to another object file) from generating duplicate definitions of any linkable entities it may contain.
The function _dummy_ is used to create references to the specializations that must be instantiated. Note also the reordering of the header files: Cfront actually includes header analysis code that causes unused headers to be omitted from the generated translation unit. Unfortunately, the technique is relatively brittle in the presence of macros with scopes that cross header boundaries.
In contrast, the standard C++ separation model involves the separate translation of two (or more) translation units, followed by an instantiation that has access to the entities of both translation units (primarily enabled by ADL across translation units). Because it is not based on inclusion, it does not impose a particular header file convention, nor do macro definitions in one translation unit pollute the other translation units. However, as we illustrated earlier in this chapter, macros aren't the only way to create surprises in C++, and the export model is exposed to other forms of "pollution."
|
|
|
|
|
LINUX