Meaning of 'instantiation' with respect to templates

Question

Note that code is instantiated only for member functions that are called. For class templates, member functions are instantiated only when they are used.

The above quote is from the book: C++ Templates by Addison Wesley.

I want to understand the meaning of the jargon "code is instantiated". Does it mean that only a particular memory is reserved, or only that code is compiled or something else?

Answer 1

This is a quite interesting question that should be done in the wider context of how templates are processed by the compiler. Basically templates are code patterns from which the compiler generates classes of functions. A template can be used to generate anything from no code at all (if never used) to an indefinite number of instantiations.

Templates are not directly compiled into any short of entity that is later used with different arguments (that is true in C# generics, but not C++), but rather the code is parsed by the compiler and maintained in memory in case it is later use while processing the current translation unit. That is, the compiler processes the template (template in italics is used in the english form of a pattern from which to create things, not the precise C++ meaning) from which it will create the code (classes or functions) when needed. Instantiation is the process by which the compiler determines that a particular template is used with a particular set of arguments and performs argument substitution on the template to generate the class or function to compile and the final compilation into binary code of the template.

There are two types of template instantiations, implicit and explicit, and the quote you refer to is about implicit template instantiations. I will start with explicit template instantiation just because it is simpler though. When you explicitly instantiate a template (google for the syntax) you tell the compiler that you want code generated from that template applied to the particular arguments that you provide. In the case of a class-template, that forces the instantiation of all of the member functions, which basically means that the compiler will substitute types and compile the result of that into binary objects.

Implicit instantiation, on the other hand, is performed on demand. When you use a class template, the bits and pieces that are actually used get generated from the template and compiled into the translation unit. If you create a variable definition std::vector<int> v;, the compiler will apply the type int (and the defaulted type std::allocator<int>) to the template std::vector and create a type std::vector<int>, but in doing so, it does not compile all of the member functions, but only those needed, which in this case it would be the default constructor std::vector<int>::vector(), and the destructor std::vector<int>::~vector(). The rest of the methods do not get compiled and there will be no code in the binary for them.

There are a few reasons for not instantiating all of the member functions, and the reasons range in complexity from simple to deep in language details. For some of the simpler ones, you can consider performance of compilation (not having to generate/compile all member functions just because one of them is used will reduce compile time by quite a bit). Slightly more complex is the fact that different member functions in the template might impose different requirements on the instantiating type. For example, operator[] on a map requires that the type of the value is default-constructible, as the operator will create a new element if it did not exist in the map already, on the other hand, if you always use find and insert, you can use std::map with types that are not default constructible. By not forcing the compilation of all member functions, the language allows you to use the template with arguments that would not meet all of the requirements of all of the methods, as long as it does meet the requirements of those methods that are actually used.

I have employed the term used quite a bit in the descriptions above, but I have not yet defined it. For a precise definition you would have to go to the standard, but you can consider as a good approximation that a member function is used if it is called directly or indirectly from your code (i.e. you call it, or some other member function that you instantiate calls it) or if your obtain the address of the member function.