C++ Template Instantiation

C++ Template Instantiation

1. Template Instantiation
A template is a description of a class or function that is a model for a family of related classes or functions. Template instantiation involves generating a concrete class or function (instance) for a particular combination of template arguments.

In a natural scenario, when a class or function is referenced or used with specifically provided template argument that matching the pre-declared/defined class/function template, an instantiation of this class or function is needed, this instantiation could be done implicitly by the compiler or by the programmer who explicitly use a keyword template to instantiate it.

Before the compiler instantiate a template, a specialization is generated for the specifically provided template type arguments, and then the compiler will instantiate this specialization so that a concrete class or function definition is generated. 

The instantiation of a class template is always done as soon as it is needed in a compilation. However, the instantiations of template functions, member functions of template classes, and static data members of template classes (hereafter referred to as template entities) are not necessarily done immediately, for several reasons:

1. One would like to end up with only one copy of each instantiated entity across all the object files that make up a program. (This of course applies to entities with external linkage.)
   
   The language allows one to write a specialization of a template entity, i.e., a specific version to be used in place of a version generated from the template for a specific data type. (One could, for example, write a version of Stack<int>, or of just Stack<int>::push, that replaces the template-generated version; often, such a specialization provides a more efficient representation for a particular data type.) Since the compiler cannot know, when compiling a reference to a template entity, if a specialization for that entity will be provided in another compilation, it cannot do the instantiation automatically in any source file that references it. (The modern C++ language requires that a specialization be declared in every compilation in which it is used, but for compatibility with existing code and older compilers the Comeau front end does not require that in some modes. See the command-line option --no_distinct_template_signatures.)
2. The language also dictates that template functions that are not referenced should not be compiled, that, in fact, such functions might contain semantic errors that would prevent them from being compiled. Therefore, a reference to a template class should not automatically instantiate all the member functions of that class.

(It should be noted that certain template entities are always instantiated when used, e.g., inline functions.)

From these requirements, one can see that if the compiler is responsible for doing all the instantiations automatically, it can only do so on a program-wide basis. That is, the compiler cannot make decisions about instantiation of template entities until it has seen all the source files that make up a complete program.


2. Automatic InstantiationThe goal of an automatic instantiation mode is to provide painless instantiation. The programmer should be able to compile source files to object code, then link them and run the resulting program, and never have to worry about how the necessary instantiations get done.

In practice, this is hard for a compiler to do, and different compilers use different automatic instantiation schemes with different strengths and weaknesses:

Borland model

Borland C++ solved the template instantiation problem by adding the code equivalent of common blocks to their linker; the compiler emits template instances in each translation unit that uses them, and the linker collapses them together. The advantage of this model is that the linker only has to consider the object files themselves; there is no external complexity to worry about. The disadvantage is that compilation time is increased because the template code is being compiled repeatedly. Code written for this model tends to include definitions of all templates in the header file, since they must be seen to be instantiated. 

Cfront model

The AT&T C++ translator, Cfront, solved the template instantiation problem by creating the notion of a template repository, an automatically maintained place where template instances are stored. A more modern version of the repository works as follows: As individual object files are built, the compiler places any template definitions and instantiations encountered in the repository. At link time, the link wrapper adds in the objects in the repository and compiles any needed instances that were not previously emitted. The advantages of this model are more optimal compilation speed and the ability to use the system linker; to implement the Borland model a compiler vendor also needs to replace the linker. The disadvantages are vastly increased complexity, and thus potential for error; for some code this can be just as transparent, but in practice it can been very difficult to build multiple programs in one directory and one program in multiple directories. Code written for this model tends to separate definitions of non-inline member templates into a separate file, which should be compiled separately.

G++ implements the Borland model on targets where the linker supports it, including ELF targets (such as GNU/Linux), Mac OS X and Microsoft Windows. Otherwise G++ implements neither automatic model.

You have the following options for dealing with template instantiations:

1. Do nothing. Code written for the Borland model works fine, but each translation unit contains instances of each of the templates it uses. The duplicate instances will be discarded by the linker, but in a large program, this can lead to an unacceptable amount of code duplication in object files or shared libraries.Duplicate instances of a template can be avoided by defining an explicit instantiation in one object file, and preventing the compiler from doing implicit instantiations in any other object files by using an explicit instantiation declaration, using the extern template syntax:
   

             extern template int max (int, int);
   

   This syntax is defined in the C++ 2011 standard, but has been supported by G++ and other compilers since well before 2011.
   Explicit instantiations can be used for the largest or most frequently duplicated instances, without having to know exactly which other instances are used in the rest of the program. You can scatter the explicit instantiations throughout your program, perhaps putting them in the translation units where the instances are used or the translation units that define the templates themselves; you can put all of the explicit instantiations you need into one big file; or you can create small files like
   

             #include "Foo.h"
             #include "Foo.cc"
             
             template class Foo<int>;
             template ostream& operator <<
                             (ostream&, const Foo<int>&);
   

   for each of the instances you need, and create a template instantiation library from those.
   This is the simplest option, but also offers flexibility and fine-grained control when necessary. It is also the most portable alternative and programs using this approach will work with most modern compilers.
2. Compile your template-using code with -frepo. The compiler generates files with the extension ‘.rpo’ listing all of the template instantiations used in the corresponding object files that could be instantiated there; the link wrapper, ‘collect2’, then updates the ‘.rpo’ files to tell the compiler where to place those instantiations and rebuild any affected object files. The link-time overhead is negligible after the first pass, as the compiler continues to place the instantiations in the same files.This can be a suitable option for application code written for the Borland model, as it usually just works. Code written for the Cfront model needs to be modified so that the template definitions are available at one or more points of instantiation; usually this is as simple as adding #include <tmethods.cc> to the end of each template header.
   For library code, if you want the library to provide all of the template instantiations it needs, just try to link all of its object files together; the link will fail, but cause the instantiations to be generated as a side effect. Be warned, however, that this may cause conflicts if multiple libraries try to provide the same instantiations. For greater control, use explicit instantiation as described in the next option.
3. Compile your code with -fno-implicit-templates to disable the implicit generation of template instances, and explicitly instantiate all the ones you use. This approach requires more knowledge of exactly which instances you need than do the others, but it's less mysterious and allows greater control if you want to ensure that only the intended instances are used.If you are using Cfront-model code, you can probably get away with not using -fno-implicit-templates when compiling files that don't ‘#include’ the member template definitions.
   If you use one big file to do the instantiations, you may want to compile it without -fno-implicit-templates so you get all of the instances required by your explicit instantiations (but not by any other files) without having to specify them as well.
   In addition to forward declaration of explicit instantiations (with extern), G++ has extended the template instantiation syntax to support instantiation of the compiler support data for a template class (i.e. the vtable) without instantiating any of its members (with inline), and instantiation of only the static data members of a template class, without the support data or member functions (with static):
   

             inline template class Foo<int>;
             static template class Foo<int>;

Implicit Instantiation
The use of a class template or function template introduces the need for an instance(a concrete definition of the class or function).  If that instance does not already exist, the compiler implicitly instantiates the template for that combination of template arguments.

Unless a template specialization has been explicitly instantiated or explicitly specialized, the compiler will generate a specialization for the template only when it needs the definition.
Note: The compiler does not need to generate the specialization for non-class, non-inline entities when an explicit instantiation declaration is present.


At the point that a compiler must instantiate a class template specialization, a definition of the template must be provided.

For example, if you declare a pointer to a class, the definition of that class is not needed and the class will not be implicitly instantiated. The following example demonstrates when the compiler instantiates a template class:

template<class T> class X {
  public:
    X* p;
    void f();
    void g();
1};

X<int>* q;
X<int> r;
X<float>* s;
r.f();
s->g();

The compiler requires the instantiation of the following classes and functions:

• X<int> when the object r is declared
• X<int>::f() at the member function call r.f()
• X<float> and X<float>::g() at the class member access function call s->g()

Therefore, the functions X<T>::f() and X<T>::g() must be defined in order for the above example to compile. (The compiler will use the default constructor of class X when it creates object r.) The compiler does not require the instantiation of the following definitions:

• class X when the pointer p is declared
• X<int> when the pointer q is declared
• X<float> when the pointer s is declared

The compiler will implicitly instantiate a class template specialization if it is involved in pointer conversion or pointer to member conversion. The following example demonstrates this:

template<class T> class B { };
template<class T> class D : public B<T> { };

void g(D<double>* p, D<int>* q)
{
  B<double>* r = p;
  delete q;
}

The assignment B<double>* r = p converts p of type D<double>* to a type of B<double>*; the compiler must instantiate D<double>. The compiler must instantiate D<int> when it tries to delete q.

If the compiler implicitly instantiates a class template that contains static members, those static members are not implicitly instantiated. The compiler will instantiate a static member only when the compiler needs the static member's definition. Every instantiated class template specialization has its own copy of static members. The following example demonstrates this:

template<class T> class X {
public:
   static T v;
};

template<class T> T X<T>::v = 0;

X<char*> a;
X<float> b;
X<float> c;

Object a has a static member variable v of type char*. Object b has a static variable v of type float. Objects b and c share the single static data member v.

An implicitly instantiated template is in the same namespace where you defined the template.

If a function template or a member function template specialization is involved with overload resolution, the compiler implicitly instantiates a declaration of the specialization.

Explicit instantiation

As we know now, the compiler implicitly instantiates templates only for those templates(with specific template arguments provided) that are actually used. This approach may be inappropriate for the construction of libraries that provide templates. Explicit instantiation lets you create an instantiation of a templated class or function without actually using it in your code. This is useful when you are creating library (.lib) files that use templates for distribution, because uninstantiated template definitions will not be put into object (.obj) files.
Another circumstance that an explicit instantiation is needed it that  if you separate declaration and definition of a template in .h file and .cpp file, and then when you use the template in another .cpp file, an error will appear in the link phase indicating you that the definition of the template is not found, in such case, put an explicit instantiation statement in the definition .cpp file will solve.

C++ provides a facility to explicitly instantiate templates

You can explicitly tell the compiler when it should generate a definition from a template. This is called explicit instantiation. Explicit instantiation includes two forms: explicit instantiation declaration and explicit instantiation definition.

Note: C++0x is a new version of the C++ programming language standard. This is a draft standard and has not been officially adopted in its entirety. The implementation of C++0x is based on IBM's interpretation of the draft C++0x standard and is subject to change at any time without notice. IBM makes no attempt to maintain compatibility with earlier releases and therefore the C++0x language extension should not be relied on as a stable programming interface.

Explicit instantiation declaration

The explicit instantiation declarations feature is introduced in the C++0x standard. With this feature, you can suppress the implicit instantiation of a template specialization or its members. The extern keyword is used to indicate explicit instantiation declaration. The usage of extern here is different from that of a storage class specifier.

Explicit instantiation declaration syntax

extern template template_declaration<parameter-list>

You can provide an explicit instantiation declaration for a template specialization if an explicit instantiation definition of the template exists in other translation units or later in the same file. If one translation unit contains the explicit instantiation definition, other translation units can use the specialization without having the specialization instantiated multiple times. The following example demonstrates this concept:

//sample1.h:
template<typename T, T val>
union A{
   T foo();
};
extern template union A<int, 55>;

template<class T, T val>
T A<T,val>::foo(void){
   return val;
}

//sampleA.C"
#include "sample1.h"

template union A<int,55>;

//sampleB.C:
#include "sample1.h"

int main(void){
   return A<int, 55>().foo();
}

sampleB.C uses the explicit instantiation definition of A<int, 55>().foo() in sampleA.C.

If an explicit instantiation declaration of a function or class is declared, but there is no corresponding explicit instantiation definition anywhere in the program, the compiler issues an error message. See the following example:

// sample2.C
template <typename T, T val>
struct A{
   virtual T foo();
   virtual T bar();
}

extern template int A<int,55>:foo();

template <class T, T val>
T A<T,val>::foo(void){
   return val;
}

template <class T, T val>
T A<T,val>::bar(void){
   return val;
}

int main(void){
   return A<int,55>().bar();
}

When you use explicit instantiation declaration, pay attention to the following restrictions:

• You can name a static class member in an explicit instantiation declaration, but you cannot name a static function because a static function cannot be accessed by name in other translation units.
• Explicit instantiation declarations have no effect on inline functions. An inline function is still implicitly instantiated even if an explicit instantiation declaration of the inline function is present, but no out-of-line copy of the inline function is generated in this case.
• The explicit instantiation declaration of a class is not equivalent to the explicit instantiation declaration of each of its members.

Explicit instantiation definition

An explicit instantiation definition is an instantiation of a template specialization or a its members.

Explicit instantiation definition syntax

>>-template--template_declaration------------------------------><

Here is an example of explicit instantiation definition:

template<class T> class Array { void mf(); };
template class Array<char>;       /* explicit instantiation definition */
template void Array<int>::mf();   /* explicit instantiation definition */

template<class T> void sort(Array<T>& v) { }
template void sort(Array<char>&); /* explicit instantiation definition */

namespace N {
   template<class T> void f(T&) { }
}

template void N::f<int>(int&);
// The explicit instantiation definition is in namespace N.

int* p = 0;
template<class T> T g(T = &p);
template char g(char);           /* explicit instantiation definition */

template <class T> class X {
   private:
      T v(T arg) { return arg; };
};

template int X<int>::v(int);    /* explicit instantiation definition */

template<class T> T g(T val) { return val;}
template<class T> void Array<T>::mf() { }

An explicit instantiation definition of a template is in the same namespace where you define the template.

Access checking rules do not apply to the arguments in the explicit instantiation definitions. Template arguments in an explicit instantiation definition can be private types or objects. In this example, you can use the explicit instantiation definition template int X<int>::v(int) even though the member function is declared to be private.

The compiler does not use default arguments when you explicitly instantiate a template. In this example, you can use the explicit instantiation definition template char g(char) even though the default argument is an address of the type int.

Explicit instantiation and inline namespace definitions

Inline namespace definitions are namespace definitions with an initial inline keyword. Members of an inline namespace can be explicitly instantiated or specialized as if they were also members of the enclosing namespace. For more information, see Inline namespace definitions (C++0x)

C++11 extern template
You should only use extern template to force the compiler to not instantiate a template when you know that it will be instantiated somewhere else, its used to reduce compile time and reduce object file size.

A usage(this usage may not be practical or conform to the intention of template semantics):
If you define a template class that you only what to work for a couple of explicit types.
Put the template declaration in the header file just like a normal class.
Put the template definition in a source file just like a normal class.
Then at the end of the source file explicitly instantiate only the version you want to be available.
References:
http://en.cppreference.com/w/cpp/language/function_template
http://docs.oracle.com/cd/E19205-01/820-7599/bkafi/index.html
http://www.comeaucomputing.com/4.0/docs/userman/ati.html
https://gcc.gnu.org/onlinedocs/gcc/Template-Instantiation.html
http://www-01.ibm.com/support/knowledgecenter/SS4QVT_8.5.1/com.ibm.xlcpp111.aix.doc/language_ref/implicit_instantiation.html
http://stackoverflow.com/questions/8130602/using-extern-template-c0x