Templates Basics II : Templates Basics II Pavel Popov
22.Mai 2006 Proseminar
Contents : Contents Fundamentals In Depth
Names in Templates
Instantiation
Template Argument Deduction
Specialization and Overloading
Fundamentals In Depth : Fundamentals In Depth Member Templates
Linkage of Templates
Primary Templates
Template Parameters
Template Arguments
Friends
Member Templates : Member Templates Declared like ordinary classes, except for the parameterization clause
Member Function Templates cannot be declared virtual template
Class List{ //a namespace scope class template
public:
template //an in-class member function template
List(List const&); //(constructor)
...
template //an in-class member class template
class Node { ... } //definition
...};
template
int length (List const&); //a namespace scope function template
...
Linkage of Templates : Linkage of Templates Every template must have a unique name within its scope
Can not be declared in a function
Class templates cannot share a name with a different kind of entity:
C linkage is not allowed, C++ linkage is the default:
int X;
template
Class X; //Error extern “C“ template
void invalid (); //Error
extern “C++“ template
void normal ();
Primary Templates : Primary Templates Declared without adding template arguments in angle brackets after the template name:
Function templates must always be primary templates! template class Box; //OK Primary Template
template class Box ; //Error
template void translate(T*); //OK Primary Template
template void translate(T*); //Error
Template Parameters : Template Parameters Type parameters
Intoduced with keyword „typename“ or „class“ (entirely eqiuvalent)
A type parameter acts like a typedef name (within a template declaration)
Nontype Parameters
Constant values that can be determined at compile or link time
The type of the value for which it stands must be
An int or enum type
A pointer type
A reference type
Declared much like variables but cannot have nontype specifiers (like static, mutable etc.)
Always rvalues (their address cannot be taken and cannot be assigned to)
Slide8 : Template Template Parameters (higher order genericity)
Placeholder for class templates
Declared much like class templates but without keywords like struct or union:
In the scope of their declaration used like other class templates
The parameters of template template parameters can have default template arguments
template class C>
void f ( *p); template class Container>
class Adaptation{
Container storage;
//Container //equivalent!
Template Arguments : Template Arguments Function Template Arguments (specified explicit or deduced)
Not all template arguments can be deduced! template
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}
int main(){
max (1.0, -3.0); //explicitly specify to be double
max(1.0, -3.0); //implicitly deduced to be double
max(1.0, 3.0); //the explicit inhibits the
//deduction, => the result has type int
Slide10 : Type Arguments – the values specified for template type parameters
Commonly used types can be used as template arguments except:
Local classes and enumerations
Types that involve unnamed class types or unnamed enumeration
types (except typedef declaration)
Nontype Arguments - the values substituted for nontype parameters
Another nontype template parameter (that has the right type)
Constant value (int or enum)
Reference
Pointer to member constant (&C::m) template class C;
C * c1; //integer type
int a;
C * c2; //address of an external variable
Slide11 : Template Template Arguments – must be a class template with parameters that exactly match the parameters of the template template parameter it substitutes template > class Container> //(1)
class Relation {
public:
...
private:
Container dom1;
Container dom2;
};
int main() {
Relation rel;
Slide12 : General constraint of template Arguments:
Compiler or linker must be able to express their value when the program is being built
Not valid constant values:
Null pointer constants
Floating point numbers
String literals
Friends : Friends Complications:
A friend declaration may be the only declaration of an entity
A friend declaration can be a definition
Class templates must be visible at the point where one of its instances is made a friend of a class or a class template. template
class Node;
template
class Tree{
friend class Node ;
...};
Slide14 : 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.
template
void combine(T1, T2);
class Mixer {
friend void combine<>(int&, int&); //ok: T1 = int&; T2 = int&
friend void combine(int, int); //ok: T1=int; T2=int
friend void combine(char, int); //ok: T1=char, T2=int
friend void combine(char&, int); //error: doesn‘t match // combine () template
friend void combine<>(long, long) {...} //error: definition not allowed
};
Names in Templates : Names in Templates Naming Concepts
Looking up Names
Friend Name Injection
Parsing Templates - Context Sensivity
Nontemplates
Dependent Names of Types
Dependent Names of Templates
Dependent Names in Using-Declarations
2 major naming concepts: : 2 major naming concepts: Qualified name – if there is scope resolution operator (::) or member access operator (. or ->)
this->count; s::X; p->A::m;
Dependent name – if it depends in some way on a template parameter
dependent if T is a template parameter
nondependent if T is a known typedef (int)
std::vector::iterator
Looking up names : Looking up names ordinary look up
qualified names are looked up in the scope implied by the qualifying construct.
unqualified names are typically looked up in a successively more enclosing scopes. extern int count; //(1)
int lookup_example(int count){ //(2)
if (count < 0){
int count = 1; //(3)
lookup_example(count); //unqualified count reffers to (3)
}
return count + ::count; //(2) + (1)
}
Argument-Dependent Look up : Argument-Dependent Look up Applies only to unqualified names (in addition to ordinary lookup)
ADL is inhibited if the name of the function to be called is enclosed in the parentheses.
...
namespace X {
template void f(T);
}
namespace N {
using namespace X; enum E {e1}; void f(E) {...} }
void f(int) {...}
int main() {
::f(N::e1); //qualified function name: no ADL
f(N::e1); //ordinary lookup finds ::f() and ADL finds N::f()
//and the later is preffered
Friend Name Injection : Friend Name Injection Friend functions are found when the class of which they are friend is considered by ADL. template
class C { ...
friend void f();
friend void f(C const&); ...};
void g(C*p) {
f(); //is f () visible here?
f(*p); //is f(C const&) visible here? }
Context Sensivity in Nontemplates : Context Sensivity in Nontemplates template
class Invert {
public:
static bool const result = !B; };
void g() {
bool test = Invert<(1>0)>::result //parentheses required class X { ... };
List<::X> many_X //Syntax Error <: (digraph) altern. repr. of [
List< ::X> many_X
Dependent Names of Types : Dependent Names of Types Question: declaration or multiplication?
Depends on whether the dependent qualified name Trap::x is a type name.
not a type – multiplication
a type – declaration
Language Definition Solution: a dependent qualified name does not denote a type, unless that name is prefixed with the keyword „typename“. Trap::x*y;
Dependent Names of Templates : Dependent Names of Templates All the operators that can quilify a name (::, ->, and . ) may need to be followed by the keyword template.
The Compiler cannot look up Deep (to see if it is template or not), so we must explicitly indicate it with the template prefix.
Without it: parsed as ((p.Deep)f() p.template Deep::f() p.Deep::f()
Dependent Names in Using-Declarations : Dependent Names in Using-Declarations template
class BXT {
public:
typedef T Mystery;
... };
template
class DXTT : private BXT {
public:
using typename BXT::Mystery
Mystery* p; };
Instantiation : Instantiation On-Demand Instantiation
Lazy Instantiation
The C++ Instantiation Model
Point Of Instantiation
The Inclusion And Separation Models
On-Demand Instantiation : On-Demand Instantiation Implies that the compiler usually needs access to the full deffinition (not just declaration) of the template and some of its members at the point of use
Don‘t need the definition of a class template to be in scope to declare pointers or references to a type
As soon as a component needs to know the size of a template specialization or if it accesses a member of such specialization, the entire class template definition is required to be in scope
On-Demand Instantiation : On-Demand Instantiation template class C //(1) declaration only
C* p = 0; //(2) fine definition of C not needed
template class C {
public:
void f(); //(3) member declaration
}; //(4) class member declaration completed
void g (C& c) //(5) use of class template declaration only
{
c.f(); //(6) use of class template definition
} // will need definition of C::f() C* p = new C;
Lazy Instantiation : Lazy Instantiation Question: How much of the template is instantiated?
Only as much as really needed!
When a class template is implicitly instantiated, each declaration of its members is instantiated as well, but the corresponding definitions are not, except:
class template contains anonymous union
virtual functions
default function call arguments
The C++ Instantiation Model : The C++ Instantiation Model Two Phase Lookup
first phase – parsing of a template
second phase – Instantiation
Because dependent names cannot be resolved when parsing templates, they are looked up again at the point of instantiation
Nondependant names however are looked up early so that many errors can be diagnosed when the template is first seen
Leads to the concept of TPL
The second phase occurs when templates are instantiated, at a point called Point of Instantiation (POI)
Point Of Instantiation : Point Of Instantiation Class MyInt {
public:
MyInt(int i);
};
MyInt operator- (MyInt const&);
bool operator> (MyInt const&, MyInt const&);
typedef MyInt Int;
template
void f (T i) { if (i>0) g(-i); }
//(1)
void g(Int) {
//(2)
f(42); //point of call
//(3)
}
//(4)
The Inclusion And Separation Models : The Inclusion And Separation Models Typically nonclass template definitions are simply added to header files, that are #included into the translation unit
Inclusion Model
The nonclass template can be declared using export and defined in another translation unit.
Separation Model
Example : template
void f1 (T x)
{
g1(x); //(1)
}
void g1(int) { ... }
int main(){
f1(7); //error: g1 not found
} //(2) POI for f1(int) Example g1 is never found (even ordinary lookup at the POI would have found it)
Template Argument Deduction : Template Argument Deduction The Deduction Process
Non-Deduced Contexts
Class Template Parameters
Default Call Argument
The Deduction Process : The Deduction Process The Deduction Process compares the types of an argument of a function call with the corresponding parameterized type of a function template and attempts to conclude the correct substitution for one or more of the deduced parameter
Each argument – parameter pair is analyzed independently, and if the conclusions differ in the end, the deduction process fails.
Deduction Prozess fails! template
T const& max (T const& a, T const& b)
{
return a
(Non)Deduced Contexts : (Non)Deduced Contexts Few declaration constructs are not deduced contexts
Qualified type names
Q::X will never be used to deduce a template parameter T
Nontype expressions that are not just nontype parameters
Type name like S will never be used to deduce I. Neither will T be deduced by matching against a parameter of type int(&)[sizeof(S)]
A Nondeduced Context does not automatically imply that the program is in error or even that the parameter being analyzed cannot participate in type deduction!
Class Template parameters : Class Template parameters Template argument deduction applies exclusively to function and Member function templates template
Class S {
public:
S (T b) : a(b) {
}
private:
T a;
};
S x(12); //error: the class template parameter T is not
//deduced from the constructor call argument 12
Default Call Argument : Default Call Argument The default function call argument can depend on a template parameter. Such a dependent default argument is instantiated only if no explicit argument is provided.
Even when a default call argument is not dependent, it cannot be used to deduce template arguments
template
void init (T* loc, T const& val = T() )
{
*loc = val;
}
Specialization and Overloading : Specialization and Overloading Transperent Customization
Overloading Function Templates
Partial Ordering Rules
Explicit Specialization
Full Class Template Specialization
Full Function Template Specialization
Partial Class Template Specialization
Transperent Customization : Transperent Customization All other things being equal, overload resolution preffers the „more specialized“ template template inline
void quick exchange(T* a, T* b){ //(1)
T tmp(*a);
*a = *b;
*b = tmp;
}
template inline
void quick exchange(Array* a, Array* b){ //(2)
a->exchange_with(b);
}
void demo(Array* p1, Array* p2){
int x, y;
quick_exchange(&x, &y); //uses (1)
quick_exchange(p1, p2); //uses (2)
}
Slide39 : template
Class Array {
private:
T* data;
...
public:
Array(Array const&);
void exchange_with(Array* b){
T* tmp = data;
data = b->data;
b->data = tmp;
}
...
};
Overloading Function Templates : Overloading Function Templates Not only both can coexist, but their respective instantiations can coexist even if they have identical parameter and return types!
template
int f(T)
{ return 1; }
template
int f(T*)
{ return 2; }
int main() {
cout << f((int*)0) << endl;
cout << f((int*)0) << endl;
} Ouput:
1
2
Slide41 :
f indicates we want to substitute the first template parameter without relying on template argument deduction!
Because there is more than one template f, an overload set is created containing 2 functions generated from templates:
f(int*)
f(int**)
The Argument of the call (int*)0 has type int*.
f((int*)0)
Slide42 : A function is selected even when explicit template arguments are not provided: template argument deduction comes into play.
Function templates can be overloaded with non-template functions. all else being equal, the non-template function is preferred! template
int f(T)
{ return 1; }
template
int f(T*)
{ return 2; }
int main() {
cout << f(0) << endl;
cout << f((int*)0) << endl;
} yielded functions from the second call:
f(int*)
f(int*)
Partial Ordering Rules : Partial Ordering Rules „more specialized“ ?!?
Create two artificial lists of argument types by substituting every
template parameter as follows:
Replace each template type parameter with a unique „made up“ type.
Replace each template template parameter with a unique „made up class template.
Replace each nontype template parameter with a unique „made up“ value of the appropriate type.
template
void t(T*, T const* = 0, ...); template
void t(T const*, T*, T* = 0);
Explicit Specialization : Explicit Specialization Provides an implementation for a template with template parameters, that are fully substituted: No template parameters remain.
Class templates and function templates can be fully specialized.
The members of a class template that can be defined outside the body of a class definition, can also be fully specialized.
Full Class Template Specialization : Full Class Template Specialization Full class Template specialization is introduced with a sequence of three tokens: template, <, and > template
class S {
public:
void info() {
std::cout << “generic (S::info() ) \n“;
}
};
template<>
class S {
public:
void msg() {
std::cout << “fully specialized (S::msg() ) \n“;
}
};
Full Function Template Specialization : Full Function Template Specialization
The full specialization declaration can omit explicit template arguments, when the template being specialized can be determined via argument deduction and partial ordering.
Can not include default argument values.
It does not declare a template – therefore only one definition of a noninline full function template specialization should appear in program.
We must ensure that a declaration of the full specialization follows the template to prevent attempts at using the function generated from the template
Example : template
int f (T) //(1)
{ return 1; }
template
int f (T*) //(2)
{ return 2; }
template <> int f(int) //OK specialization of (1)
{ return 3; }
template <> int f(int*) //OK specialization of (2)
{ return 4; } template<> int f(int, int i = 35) //error
{return 0;} Example
Partial Class Template Specialization : Partial Class Template Specialization Similar to full specialization but instead of fully substituting the template parameter some parametrization is left in the alternative implementation of a template
Every partial specialization – like every full specialization – is associated with the primary template.
When a template is used, the primary template is aways the one that is looked up, but then the arguments are also matched against those of the associated specialization to determine which template is looked up.
If multiple matching specializations are found – again the „most specialized“ wins!
Only Class templates can be partially specialized!
Limitations : Limitations The arguments of the partial specialization must match in kind (type, nontype, or template) the corresponding parameters of the primary template.
The parameter list of the partial specialization cannot have default arguments. The default arguments of the primary class template are used instead.
The nontype arguments of the partial specialization should be either nondependent values or plain nontype template parameters. They cannot be more complex dependent expressions like 2*T
The list of template arguments of the partial specialization should not be identical (ignoring renaming) to the list of parameters of the primary template.
Examples : template
class S; //Primary Template
template
class S; //Error! parameter kind mismatch
template
class S //Error! no default arguments
template
class S //Error! no nontype expression
template
class S //Error! no significant difference from
//primary template Examples
Slide51 :
Thank You for Your attention!