How Does the Compilation of Templates Work

How does the compilation of templates work?

The compiler generates the code for the specific types given in the template class instantiation.

If you have for instance a template class declaration as

template<typename T>
class Foo
{
public:
     T& bar()
     {
         return subject; 
     }
private:
     T subject;
};

as soon you have for example the following instantiations

Foo<int> fooInt;
Foo<double> fooDouble;

these will effectively generate the same linkable code as you would have defined classes like

class FooInt
{
public:
     int& bar()
     {
         return subject; 
     }
private:
     int subject;
}

and

class FooDouble
{
public:
     double& bar()
     {
         return subject; 
     }
private:
     double subject;
}

and instantiate the variables like

FooInt fooInt;
FooDouble fooDouble;

Regarding the point that template definitions (don't confuse with declarations regardless of templates) need to be seen with the header (included) files, it's pretty clear why:

The compiler can't generate this code without seeing the definition. It can refer to a matching instantiation that appeared first at linking stage though.

What does a non-template member function have that allows for it to
be defined outside of the header that a template function doesn't
have?

The declaration of a non-template class/member/function gives a predefined entry point for the linker. The definition can be drawn from a single implementation seen in a compiled object file (== .cpp == compilation unit).

In contrast the declaration of a templated class/member/function might be instantiated from arbitrary compilation units given the same or varying template parameters. The definition for these template parameters need's to be seen at least once. It can be either generic or specialized.

Note that you can specialize template implementations for particular types anyway (included with the header or at a specific compilation unit).
If you would provide a specialization for your template class in one of your compilation units, and don't use your template class with types other than specialized, that also should suffice for linking it all together.

I hope this sample helps clarifying what's the difference and efforts done from the compiler.

C++ How do compilers handle templates

let's say you write a function using templates:

template <typename T>
void function(T t){
 doSomething();
}

for each data type you call this function, the compiler simply replaces the 'T' with that data type, say 'int' and generates code for that like you've written this function with 'int' instead of 'T' since the beginning.
This is probably the right (but not the complete) answer if others agreed.

How does C++ partial compilation with templates work?

This is a slightly more complicated question than what most people will realize.

In the general and simplest case, the template definition is present in the header, and it behaves as inline functions. The compiler will generate the code for those functions needed in each translation unit that needs them. Then the linker will resolve the duplicate symbols by removing all but one. Since the standard requires that they are exactly equivalent, the linker can pick any one from the list.

If the template need only work with a couple of types, you can move the definition to a single translation unit and explicitly instantiate the template for those types there. This would behave as a non-inline function in the general case.

Somewhere in between, if the template can be instantiated with any type but it is commonly instantiated with a few of them, the implementor of the template can use a mixed approach, where the template and the members are defined in the header, but explicit instantiations are also declared. Then in a single translation unit, those explicit instantiations can be done.

This approach can be used, for example, to minimize compile and link time when using std::string (which is really std::basic_string<char, std::char_traits<char>, std::allocator<char> >). The compiler can, in a single translation unit provide all of the functions for the common instantiation, but still provide the definition of the template functions in the header so that if you opt to use a different instantiation of the basic_string template it will still work for you. In all translation units that only use std::string, the compiler knows not to generate the code for all members as those will be available to the linker.

Templates and separate compilation

Template classes need to have the method definitions inside the header file.

Move the code you have in the .cpp file inside the header, or create a file called .impl or .imp, move the code there, and include it in the header.

The compiler needs to know the method definitions to generate code for all specializations.

Before you ask, no, there is no way to keep the implementation outside the header.

C++ compilation process: Place for templates

Is there a step, prior to the translation to assembly, in where all of the templates are resolved?

No, there is no such separate step. Template code can and does depend on non-template code and vice versa, so they are processed together. Template code is also not specified to have any kind of equivalent non-template code in the C++ standard. Although one can come up with such template-to-non-template-code equivalence, modern compilers normally translate templates directly to some kind of internal representation rather than to non-template source code.

This is in contrast with preprocessor code, which can never depend on non-preprocessor code, and which always has precisely defined translation to non-preprocessor code. This translation is specified by the standard as one of the conceptual steps in the overall program translation process. Compilers usually implement this conceptual step as an actual translation step.

How C++ compilation handles shared library and template

If a library wants to provide templates which its clients can instantiate with arbitrary types, it must provide the templates' complete definitions in header files. This is why a lot of C++ libraries, including most of Boost, are header-only. The compiler then has access to the template's definition and can instantiate it with any types/values the client provides as template arguments.

For a detailed treatment of the topic, please refer to the Stack Overflow question Why can templates only be implemented in the header file?.

Note that this only applies if, as I said, the templates are intended for use with arbitrary types. If the set of instantiations is limited and can be determined at the time the shared library is built, the library can create explicit instantiations of all the templates it wants all combinations of template arguments it wants to support. Then, exposing the definitions of the templates is not necessary, but of course, it will not be possible to instantiate the templates with different types in client code.

As an example of this, there are some geometric libraries which provide their definitions as templates so that they can work with both float and double to represent floating-point numbers, but do not expose the template definitions; they simply pre-instantiate all their code with float and double. Clients can then use these instantiations, but cannot use them with for exmaple long double or MyCustomFloat.

2nd phase compilation in templates

The types determined during compilation time only rely on the static information. A function template that is used with a particular type will generate code for that type, since the option needs to be available in the runtime. If it can be statically determined that a function call will never happen, though, I think that the compiler might omit that implementation, but there are certain cases that'd still force that.
You can't test for all datatypes, since that's an infinite set. You can create a set of all standard types, but you obviously can't check every user-defined type ever. The idea in generic code is to not depend on the particulars of the type you're allowing to pass it. Alternatively, you might close the set of possible instances to only include the types you sanction.

How does the compiler know to use a template specialization instead of its own instantiation?

The issue is that you've violated the one definition rule. In main.C, you've included Foo.H but not Foo.C (which makes sense since it's a source file). When main.C is compiled, the compiler doesn't know that you've specialized the template in Foo.C, so it uses the generic version (that returns 6) and compiles a Foo class. Then when it compiles Foo.C, it sees a full specialization which it can compile right away -- it doesn't need to wait for it to be instantiated somewhere because all the types are filled in (if you had two template parameters and only specialized one this wouldn't be the case), and it compiles a new and distinct Foo class.

Normally, multiple definitions for the same thing cause a linker error. But template instantiations are "weak symbols", which means that multiple definitions are allowed. The linker assumes all definitions are really the same and then picks one at random (well, probably consistently the first one or the last one, but only as a coincidence of the implementation).

Why make them weak symbols? Because Foo might be used in multiple source files, each of which is compiled individually, and each time Foo is used in a compilation unit a new instantiation is generated. Normally, these are redundant, so it makes sense to throw them away. But you've violated this assumption, by providing a specialization in one compilation unit (foo.C) but not the other (main.C).

If you declare the template specialization in Foo.H, then when main.C is compiled it not generate an instantiation of Foo, thus making sure only one definition exists in your program.

Templates Double Compilation?

Independent on whether the header contains a template or not, the respective header files are processed in each translation unit they end up being included. That is, the code is compiled every time it is included.

When a template is being used in a translation unit it is instantiated. I guess, this is the aspect you are actually interested in. That is, you may end up with an instantiation of a template in multiple object files. If you look at the symbols in an object file (e.g. on UNIX system you can use nm -po object.o; I think on Windows you'd use libtool but it is a long time since I used Windows), you can normally see some function definitions. When the different object files are combined by the linker duplicate definitions will be thrown out, i.e., they don't cause any semantic problems.

It is worth noting that instantiating templates may take quite a bit of time, especially when optimizations are turned on and the same instantiations are used in many translation units. For example, IOStreams and strings are getting used often and typically it is always the same instantiation (either using wchar_t or char). The approach to deal with it as the implementer of a template is to use extern declaration for templates and explicitly instantiate them in suitable translation units (here is some more detail I wrote on this).

How Does the Compilation of Templates Work