Chapter 13
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 the entity being referred. From an implementer’s point of view, C++ is a hard language in this respect. Consider the C++ statement x*y;. If x 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 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++.
13.1 Name Taxonomy
C++ classifies names in a variety of ways—a large variety of ways, in fact. To help cope with this abundance of terminology, we provide Table 13.1 and Table 13.2, which describe these classifications. Fortunately, you can gain good insight into most C++ template issues by familiarizing yourself with two major naming concepts:
1. A name is a qualified name if the scope to which it belongs is explicitly denoted using a scope-resolution 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).
2. A name is a dependent name if it depends in some way on a template parameter. For example, std::vector<T>::iterator is usually a dependent name if T is a template parameter, but it is a nondependent name if T is a known type alias (such as the T from using T = int).
Classification |
Explanation and Notes |
Identifier |
A name that consists solely of an uninterrupted sequences of letters, underscores ( |
Operator-function-id |
The keyword |
Conversion-function-id |
Used to denote a user-defined implicit conversion operator—for example, |
Literal-operator-id |
Used to denote a user-defined literal operator—for example, |
Template-id |
The name of a template followed by template arguments enclosed in angle brackets; for example, |
Unqualified-id |
The generalization of an identifier. It can be any of the above (identifier, operator-function-id, conversion-function-id, literal-operator-id, or template-id) or a “destructor name” (e.g., notations like |
Qualified-id |
An unqualified-id that is qualified with the name of a class, enum, or namespace, or just with the global scope resolution operator. Note that such a name itself can be qualified. Examples are |
Qualified name |
This term is not defined in the standard, but we use it to refer to names that undergo qualified lookup. Specifically, this is a qualifiedid or an unqualified-id that is used after an explicit member access operator ( |
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. |
Name |
Either a qualified or an unqualified name. |
Table 13.1. Name Taxonomy (Part 1)
Classification |
Explanation and Notes |
Dependent name |
A name that depends in some way on a template parameter. Typically, a qualified or unqualified name that explicitly contains a template parameter is dependent. Furthermore, a qualified name that is qualified by a member access operator ( |
Nondependent name |
A name that is not a dependent name by the above description. |
Table 13.2. Name Taxonomy (Part 2)
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 found easily in the index.
13.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 searched. 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 (al-though 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 that—in addition to ordinary lookup—they may sometimes undergo argument-dependent lookup (ADL).2 Before proceeding with the details of ADL, let’s motivate the mechanism with our perennial max() template:
template<typename T>
T max (T a, T b)
{
return b < a ? a : b;
}
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 presence of C++ namespaces. ADL is the C++ answer to those “special rules.”
13.2.1 Argument-Dependent Lookup
ADL applies primarily to unqualified names that look like they name a nonmember function in a function call or operator invocation. ADL does not happen if ordinary lookup finds
• the name of a member function,
• the name of a variable,
• the name of a type, or
• the name of a block-scope function declaration.
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 of 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 instance, 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;
enum E { e1 };
void f(E) {
std::cout << "N::f(N::E) called
";
}
}
void f(int)
{
std::cout << "::f(int) called
";
}
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().
13.2.2 Argument-Dependent Lookup of Friend Declarations
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 (which may be the global scope) enclosing the class containing the friend declaration. However, such a friend declaration is not directly visible in that scope. 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?
}
If friend declarations were visible in the enclosing namespace, then instantiating a class template may make visible the declaration of ordinary functions. This would lead to surprising behavior: The call f() would result in a compilation error unless an instantiation of the class C occurred earlier in the program!
On the other hand, it can be useful to declare (and define) a function in a friend declaration only (see Section 21.2.1 on page 497 for a technique that relies on this behavior). Such a function can be 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).3
The ability of argument-dependent lookup to find friend declarations and definition is sometimes referred to as friend name injection. However, this term is somewhat misleading, because it is the name of a pre-standard C++ feature that did in fact “inject” the names of friend declarations into the enclosing scope, making them visible to normal name lookup. In our example above, this would mean that both calls would be well-formed. This chapter’s afternotes further detail the history of friend name injection.
13.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() << ’
’;
}
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) if the context expects a type, or a template if the context expects a template. This explains the following situation:
template<template<typename> class TT> class X {
};
template<typename T> class C {
C* a; // OK: same as “C<T>* a;”
C<void>& b; // OK
X<C> c; // OK: C without a template argument list denotes the template C
X<::C> d; // OK: ::C is not the injected class name and therefore always
// denotes the template
};
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 ::.
The injected class name for a variadic template has an additional wrinkle: If the injected class name were directly formed by using the variadic template’s template parameters as the template arguments, the injected class name would contain template parameter packs that have not been expanded (see Section 12.4.1 on page 201 for details of pack expansion). Therefore, when forming the injected class name for a variadic template, the template argument that corresponds to a template parameter pack is a pack expansion whose pattern is that template parameter pack:
template<int I, typename… T> class V {
V* a; // OK: same as “V<I, T…>* a;”
V<0, void> b; // OK
};
13.2.4 Current Instantiations
The injected class name of a class or class template is effectively an alias for the type being defined. For a nontemplate class, this property is obvious, because the class itself is the only type with that name and in that scope. However, inside a class template or a nested class within a class template, each template instantiation produces a different type. This property is particularly interesting in that context, because it means that the injected class name refers to the same instantiation of the class template rather than some other specialization of that class template (the same holds for nested classes of class templates).
Within a class template, the injected class name or any type that is equivalent to the injected class name (including looking through type alias declarations) of any enclosing class or class template is said to refer to a current instantiation. Types that depend on a template parameter (i.e., dependent types) but do not refer to a current instantiation are said to refer to an unknown specialization, which may be instantiated from the same class template or some entirely different class template. The following example illustrates the difference:
template<typename T> class Node {
using Type = T;
Node* next; // Node refers to a current instantiation
Node<Type>* previous; // Node<Type> refers to a current instantiation
Node<T*>* parent; // Node<T*> refers to an unknown specialization
};
Identifying whether a type refers to a current instantiation can be confusing in the presence of nested classes and class templates. The injected class names of enclosing classes and class templates (or types equivalent to them) do refer to a current instantiation, while the names of other nested classes or class templates do not:
template<typename T> class C {
using Type = T;
struct I {
C* c; // C refers to a current instantiation
C<Type>* c2; // C<Type> refers to a current instantiation
I* i; // I refers to a current instantiation
};
struct J {
C* c; //C refers to a current instantiation
C<Type>* c2; // C<Type> refers to a current instantiation
I* i; // I refers to an unknown specialization,
// because I does not enclose
JJ* j; // J refers to a current instantiation
};
};
When a type refers to a current instantiation, the contents of that instantiated class are guaranteed to be instantiated from the class template or nested class thereof that is currently being defined. This has implications for name lookup when parsing templates—the subject of our next section—but it also leads to an alternative, more game-like way to determine whether a type X within the definition of a class template refers to a current instantiation or an unknown specialization: If another programmer can write an explicit specialization (described in detail in Chapter 16) such that X refers to that specialization, then X refers to an unknown specialization. For example, consider the instantiation of the type C<int>::J in the context of the above example: We know the definition of C<T>::J used to instantiate the concrete type (since that’s the type we’re instantiating). Moreover, because an explicit specialization cannot specialize a template or member of a template without also specializing all of the enclosing templates or members, C<int> will be instantiated from the enclosing class definition. Hence, the references to J and C<int> (where Type is int) within J refer to a current instantiation. On the other hand, one could write an explicit specialization for C<int>::I as follows:
template<> struct C<int>::I {
// definition of the specialization
};
Here, the specialization of C<int>::I provides a completely different definition than the one that was visible from the definition of C<T>::J, so the I inside the definition of C<T>::J refers to an unknown specialization.
13.3 Parsing Templates
Two fundamental activities of compilers for most programming languages are tokenization—also called scanning or lexing—and 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 a valid init-declarator. Finally, the keyword int is a known type name, and, when followed by the init-declarator *p = 0, you get the initializing declaration of p.
13.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 context-free languages, 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 comparison—true or false, implicitly converted to 1 or 0 in this case—is 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 known to be that of a template; otherwise, the < is treated as 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 = Invert<(1>0)>::result; // parentheses required!
}
If the parentheses in Invert<(1>0)> were omitted, the greater-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 ((Invert<1>))0>::result.4
The tokenizer isn’t spared problems with the angle-bracket notation either. For example, in
List<List<int>> a;
// ^-- no space between right angle brackets
the two > characters combine into a right-shift token >> and hence are never treated as two separate tokens by the tokenizer. This is a consequence of the maximum munch tokenization principle: A C++ implementation must collect as many consecutive characters as possible into a token.5
As mentioned in Section 2.2 on page 28, since C++11, the C++ standard specifically calls out this case—where a nested template-id is closed by a right-shift token >>—and, within the parser, treats the right shift as being equivalent to two separate right angle brackets > and > to close two template-ids at once.6 It’s interesting to note that this change silently changes the meaning of some—admittedly contrived—programs. Consider the following example:
names/anglebrackethack.cpp
#include <iostream>
template<int I> struct X {
static int const c = 2;
};
template<> struct X<0> {
typedef int c;
};
template<typename T> struct Y {
static int const c = 3;
};
static int const c = 4;
int main()
{
std::cout << (Y<X<1> >::c >::c>::c) << ’ ’;
std::cout << (Y<X< 1>>::c >::c>::c) << ’
’;
}
This is a valid C++98 program that outputs 0 3. It is also a valid C++11 program, but there the angle bracket hack makes the two parenthesized expressions equivalent, and the output is 0 0.7
A similar problem existed because of the existence of the digraph <: as an alternative for the source character [ (which is not available on some traditional keyboards). Consider the following example:
template<typename T> struct G {};
struct S;
G<::S> gs; // valid since C++11, but an error before that
Before C++11, that last line of code was equivalent to G[:S> gs;, which is clearly invalid. Another “lexical hack” was added to address that problem: When a compiler sees the characters <:: not immediately followed by : or >, the leading pair of characters <: is not treated as a digraph token equivalent to [.8 This digraph hack can make previously valid (but somewhat contrived) programs invalid:9
#define F(X) X ## :
int a[] = { 1, 2, 3 }, i = 1;
int n = a F(<::)i]; // valid in C++98/C++03, but not in C++11
To understand this, note that the “digraph hack” applies to preprocessing tokens, which are the kinds of tokens acceptable to the preprocessor (they may not be acceptable after preprocessing has completed), and they are decided before macro expansion completes. With that in mind, C++98/C++03 unconditionally transforms <: into [ in the macro invocation F(<::), and the definition of n expands to
int n = a [ :: i];
which is perfectly fine. C++11, however, does not perform the digraph transformation because, before macro expansion, the sequence <:: is not followed by : or >, but by ). Without the digraph transformation, the concatenation operator ## must attempt to glue :: and : into a new preprocessing token, but that doesn’t work because ::: is not a valid concatenation token. That standard makes this undefined behavior, which allows the compiler to do anything. Some compilers will diagnose this problem, while others won’t and will just keep the two preprocessing tokens separate, which is a syntax error because it leads to a definition of n that expands to
int n = a < :: : i];
13.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. 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:
using x = int; // #3 x is a type here
};
void boom(Victim<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 Trap<T>::x for the case where T is void. In this case, Trap<T>::x is in fact type int.
In this example, the type Trap<T> is a dependent type because the type depends on the template parameter T. Moreover, Trap<T> refers to an unknown specialization (described in Section 13.2.4 on page 223), which means that the compiler cannot safely look inside the template to determine whether the name Trap<T>::x is a type or not. Had the type preceding the :: referred to a current instantiation—for example, with Victim<T>::y—the compiler could have looked into the template definition because it is certain that no other specialization could intervene. Thus, when the type preceding :: refers to the current instantiation, qualified name lookup in a template behaves very similarly to qualified name lookup for nondependent types.
However, as illustrated by the example, name lookup into an unknown specialization is still a problem. 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 differs 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 satisfies all of the following conditions:10
1. It is qualified and not itself followed by :: to form a more qualified name.
2. It is not part of an elaborated-type-specifier (i.e., a type name that starts with one of the keywords class, struct, union, or enum).
3. It is not used in a list of base class specifications or in a list of member initializers introducing a constructor definition.11
4. It is dependent on a template parameter.
5. It is a member of an unknown specialization, meaning that the type named by the qualifier refers to an unknown specialization.
Furthermore, the typename prefix is not allowed unless at least the first two previous conditions hold. To illustrate this, consider the following erroneous example:12
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;
using Type = T;
using OtherType = typename8 S<T>::Type;
};
Each occurrence of typename—correct or not—is 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 second 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 the first two rules but not the last two. The eighth typename is also optional, because it refers to a member of a current instantiation (and therefore does not satisfy the last rule).
The last of the rules for determining whether the typename prefix is required can occasionally be tricky to evaluate, because it depends on the rules for determining whether a type refers to a current instantiation or an unknown specialization. In such cases, it is safest to simply add the typename keyword to indicate that you intend the qualified name that follows to be a type. The typename keyword, even if it’s optional, will provide documentation of your intent.
13.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 (
typename Shell<T>::template In<N>::template Deep<N>* p) {
p->template Deep<N>::f(); // inhibit virtual call
}
void case2 (
typename Shell<T>::template In<N>::template Deep<N>& 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 refers to an unknown specialization, 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. As with the typename keyword, one can safely add the template prefix to indicate that the following name is a template-id, even if the template prefix is not strictly needed.
13.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, on the other hand, can 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.
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:
using Mystery = T;
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 without the earlier 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
The standardization committee has not been inclined to address this issue. However, C++11 alias templates do provide a partial workaround:
template<typename T>
class DXTM : private BXT<T> {
public:
template<typename U>
using Magic = typename BXT<T>::template Magic<T>; // Alias template
Magic<T>* plink; // OK
};
This is a little unwieldy, but it achieves the desired effect for the case of class templates. The case of function templates (arguably less common) remains unaddressed, unfortunately.
13.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. Furthermore, a compiler cannot decide that <3> is a template argument list until it has 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.
This example may give the impression that ADL is disabled for template-ids, but it is not. The code can be fixed by introducing a function template named select that is visible at the call:
template<typename T> void select();
Even though it doesn’t make any sense for the call select<3>(xp), the presence of this function template ensures that select<3> will be parsed as a template-id. ADL will then find the function template N::select, and the call will succeed.
13.3.6 Dependent Expressions
Like names, expressions themselves can be dependent on template parameters. An expression that depends on a template parameter can behave differently from one instantiation to the next—for example, selecting a different overloaded function or producing a different type or constant value. Expressions that do not depend on a template parameter, in contrast, provide the same behavior in all instantiations.
An expression can be dependent on a template parameter in several different ways. The most common form of dependent expression is a type-dependent expression, where the type of the expression itself can vary from one instantiation to the next—for example, an expression that refers to a function parameter whose type is that of a template parameter:
template<typename T> void typeDependent1(T x)
{
x; // the expression type-dependent, because the type of x can vary
}
Expressions that have type-dependent subexpressions are generally type-dependent themselves—for example, calling a function f() with the argument x:
template<typename T> void typeDependent2(T x)
{
f(x); // the expression is type-dependent, because x is type-dependent
}
Here, note that type of f(x) can vary from one instantiation to the next both because f might resolve to a template whose result type depends on the argument type and because two-phase lookup (discussed in Section 14.3.1 on page 249) might find completely different functions named f in different instantiations.
Not all expressions that involve template parameters are type-dependent. For example, an expression that involves template parameters can produce different constant values from one instantiation to the next. Such expressions are called value-dependent expressions, the simplest of which are those that refer to a nontype template parameter of nondependent type. For example:
template<int N> void valueDependent1()
{
N; // the expression is value-dependent but not type-dependent,
// because N has a fixed type but a varying constant value
}
Like type-dependent expressions, an expression is generally value-dependent if it is composed of other value-dependent expressions, so N + N or f(N) are also value-dependent expressions.
Interestingly, some operations, such as sizeof, have a known result type, so they can turn a type-dependent operand into a value-dependent expression that is not type-dependent. For example:
template<typename T> void valueDependent2(T x)
{
sizeof(x); // the expression is value-dependent but not type-dependent
}
The sizeof operation always produces a value of type std::size_t, regardless of its input, so a sizeof expression is never type-dependent, even if—as in this case—its subexpression is type-dependent. However, the resulting constant value will vary from one instantiation to the next, so sizeof(x) is a value-dependent expression.
What if we apply sizeof on a value-dependent expression?
template<typename T> void maybeDependent(T const& x)
{
sizeof(sizeof(x));
}
Here, the inner sizeof expression is value-dependent, as noted above. However, the outer sizeof expression always computes the size of a std::size_t, so both its type and constant value are consistent across all instantiations of the template, despite the innermost expression (x) being type-dependent. Any expression that involves a template parameter is an instantiation-dependent expression,13 even if both its type and constant value are invariant across valid instantiations. However, an instantiation-dependent expression may turn out to be invalid when instantiated. For example, instantiating maybeDependent() with an incomplete class type will trigger an error, because sizeof cannot be applied to such types.
Type-, value-, and instantiation-dependence can be thought of as a series of increasingly more inclusive classifications of expressions. Any type-dependent expression is also considered to be value-dependent, because an expression whose type that varies from one instantiation to the next will naturally have its constant value vary from one instantiation to the next. Similarly, an expression whose type or value varies from one instantiation to the next depends on a template parameter in some way, so both type-dependent expressions and value-dependent expressions are instantiation-dependent. This containment relationship is illustrated by Figure 13.1.
Figure 13.1. Containment relationship among type-, value-, and instantiation-dependent expressions
As one proceeds from the innermost context (type-dependent expressions) to the outermost context, more of the behavior of the template is determined when the template is parsed and therefore cannot vary from one instantiation to the next. For example, consider the call f(x): If x is type-dependent, then f is a dependent name that is subject to two-phase lookup (Section 14.3.1 on page 249), whereas if x is value-dependent but not type-dependent, f is a nondependent name for which name lookup can be completely determined at the time that the template is parsed.
13.3.7 Compiler Errors
A C++ compiler is permitted (but not required!) to diagnose errors at the time the template is parsed when all of the instantiations of the template would produce that error. Let’s expand on the f(x) example from the previous section to explore this further:
void f() { }
template<int x> void nondependentCall()
{
f(x); // x is value-dependent, so f() is nondependent;
// this call will never succeed
}
Here, the call f(x) will produce an error in every instantiation because f is a nondependent name and the only visible f accepts zero arguments, not one. A C++ compiler can produce an error when parsing the template or may wait until the first template instantiation: Commonly used compilers differ even on this simple example. One can construct similar examples with expressions that are instantiation-dependent but not value-dependent:
template<int N> void instantiationDependentBound()
{
constexpr int x = sizeof(N);
constexpr int y = sizeof(N) + 1;
int array[x - y]; // array will have a negative size in all instantiations
}
13.4 Inheritance 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.
13.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;
using T = int;
};
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 derives—even 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.”
13.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 alternative—not allowed by the C++ standard—would 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 classes14 (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 concrete base instance 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:
enum E { 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 how we used D<T>::E instead of B<T>::E in this example. In this case, either one works. In multiple-inheritance cases, however, we may not know which base class provides the desired member (in which case using the derived class for qualification works) or multiple base classes may declare the same name (in which case we may have to use a specific base class name for disambiguation).
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 lookup—a chicken-and-egg problem. To avoid subtlety, we prefer to use the this-> prefix in all situations that allow it—even 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.
When searching for a qualified name within the current instantiation, the C++ standard specifies that name lookup first search in the current instantiation and in all nondependent bases, similar to the way it performs unqualified lookup for that name. If any name is found, then the qualified name refers to a member of a current instantiation and will not be a dependent name.15 If no such name is found, and the class has any dependent bases, then the qualified name refers to a member of an unknown specialization. For example:
class NonDep {
public:
using Type = int;
};
template<typename T>
class Dep {
public:
using OtherType = T;
};
template<typename T>
class DepBase : public NonDep, public Dep<T> {
public:
void f() {
typename DepBase<T>::Type t; // finds NonDep::Type;
// typename keyword is optional
typename DepBase<T>::OtherType* ot; // finds nothing; DepBase<T>::OtherType
// is a member of an unknown specialization
}
};
13.5 Afternotes
The first compiler really to parse template definitions was developed by a company called Taligent in the mid-1990s. Before that—and even several years after that—most 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. At the time of this writing, the Microsoft Visual C++ compiler still works this way. The Edison Design Group’s (EDG’s) compiler front end uses a hybrid technique where templates are treated internally as a sequence of annotated tokens, but a “generic parsing” is performed to validate the syntax in modes where that is desirable (EDG’s product emulates multiple other compilers; in particular, it can closely emulate the behavior of Microsoft’s compiler).
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 Pennello—a widely recognized parsing expert working for Metaware—noted 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 (e.g., List{::X}) at a C++ standards meeting in 1991 (held in Dallas).16 At that time the extent of the problem was more limited because templates nested inside other templates—called member templates—were not valid, and thus the discussion of Section 13.3.3 on page 230 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 13.4.2 on page 237 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.17 In particular, all implementations of the Standard Template Library (STL) broke the rule in many hundreds—and sometimes thousands—of places.18 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 13.4.1 on page 236) is an oversight, but suggestions to change the rule have not garnered support from the C++ standardization committee. It is best to avoid code with template parameter names that are also used in nondependent base classes. Good naming conventions are helpful for such problems.
Friend name injection was considered harmful because it made the validity of programs more sensitive to the ordering of instantiations. Bill Gibbons (who at the time was working on the Taligent compiler) was among the most vocal supporters of addressing the problem, because eliminating instantiation order dependencies enabled new and interesting C++ development environments (on which Taligent was rumored to be working). However, the Barton-Nackman trick (Section 21.2.1 on page 497) required a form of friend name injection, and it is this particular technique that caused it to remain in the language in its current (weakened) form based on ADL.
Andrew Koenig first proposed ADL for operator functions only (which is why ADL is sometimes called Koenig lookup). The motivation was primarily aesthetics: Explicitly qualifying operator names with their enclosing namespace looks awkward at best (e.g., 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 14). The generalized ADL rules are also called extended Koenig lookup.
The specification for the angle bracket hack was added to C++11 by David Vandevoorde through his paper N1757. He also added the digraph hack via the resolution of Core issue 1104, to address a request of the United States’ review of a draft of the C++11 standard.
2 In C++98/C++03, this was also called Koenig lookup (or extended Koenig lookup) after Andrew Koenig, who first proposed a variation of this mechanism.
3 Although this was clearly intended by those who wrote the C++ standard, it is not clearly spelled out in the standard.
4 Note the double parentheses to avoid parsing (Invert<1>)0 as a cast operation—yet another source of syntactic ambiguity.
5 Specific exceptions were introduced to address tokenization issues described in this section.
6 The 1998 and 2003 versions of the C++ standard did not support this “angle bracket hack.” However, the need to introduce a space between the two consecutive right angle brackets was such a common stumbling block for beginning template users that the committee decided to codify this hack in the 2011 standard.
7 Some compilers that provide a C++98 or C++03 mode keep the C++11 behavior in those modes and thus print 0 0 even when formally compiling C++98/C++03 code.
8 This is therefore an exception to the aforementioned maximum munch principle.
9 Thanks to Richard Smith for pointing that out.
10 Note that C++20 will probably remove the need for typename in most cases (see Section 17.1 on page 354 for details).
11 Syntactically, only type names are permitted within these contexts, so a qualified name is always assumed to name a type.
12 Adapted from [VandevoordeSolutions], proving once and for all that C++ promotes code reuse.
13 The terms type-dependent expression and value-dependent expression are used in the C++ standard to describe the semantics of templates, and they have an effect on several aspects of template instantiation (Chapter 14). On the other hand, the term instantiation-dependent expression is mainly only used by the authors of C++ compilers. Our definition of a instantiation-dependent expression comes from the Itanium C++ ABI [ItaniumABI], which provides the basis for binary interoperability among a number of different C++ compilers.
14 This is part of the two-phase lookup rules that distinguish between a first phase when template definitions are first seen and a second phase when templates are instantiated (see Section 14.3.1 on page 249).
15 However, the lookup is nonetheless repeated when the template is instantiated, and if a different result is produced in that context, the program is ill-formed.
16 Braces are not entirely without problems either. Specifically, the syntax to specialize class templates would require nontrivial adaptation.
17 Fortunately, they found out before they released the new functionality.
18 Ironically, the first of these implementations had been developed by HP as well.