Introduction

Compiling template classes is not nearly as straightforward as it should be. While the goal of writing a template class is to improve "resusability", this is from the perspective of the programmer.

However, for each kind of template instantiation, the compiler generates specific code for that instantiation. For example, consider the SimpleMap template class. It takes two template type parameters.

Suppose in main(), you had the following declarations for SimpleMap.

int main() {
   SimpleMap<string, Movie> x;
   SimpleMap<string, Student> y;
   SimpleMap<int, float> z;
}

Each line of declaration refers to a different instantiation. When you instantiate a template class, you are picking classes for the template class. For example, there is code that is created for SimpleMap<string, Movie>, and there is code created for SimpleMap<string, Student>, and there is also code created for SimpleMap<int, float>.

While most of the code is very similar, each is specific for the two types that the class has been instantiated to. For example, the class methods might refer to the output operator method. The code for printing a Movie, Student, and float are all different.

If you think this is wasteful, you are right. You write template code because you want to avoid writing the same class over and over, but the only change between the classes is the type. You would think that the compiler would somehow try to "factor" out the common code. For efficiency reasons, it does not do that.

Instead, it creates code for each kind of instantiated type. This is quicker, but it means that for every instantiation of a template class, the compiler must generate new code. If you have N different kinds of instantiations, you will have N different copies of the SimpleMap code, each tailored to the types to which it has been instantiated.

Because of this, compiling template classes is not nearly as nice as one would like. Let's see where the problem lies.

What's the Problem?

Recall that C/C++ uses separate compilation to compile multiple files. What does this mean? If you have a compile command, like the following:

cxx -w0 -std strict_ansi  Foo.cpp Bar.cpp Baz.cpp

the compiler compiles each file separately. First it compiles Foo.cpp, then Bar.cpp, and finally Baz.cpp. When it compiles any of these files, it does NOT pass information between the two. In fact, compiling above is almost the equivalent of doing the following

cxx -w0 -std strict_ansi Foo.cpp -c
cxx -w0 -std strict_ansi Bar.cpp -c
cxx -w0 -std strict_ansi Baz.cpp -c

The difference in THIS version is that there is no linking to create the executable (and that the object files are placed in the directory). Other than that, the two ways of compiling are quite similar.

So what happens when, say, Foo.cpp is compiled? It looks at the code in Foo.cpp and generates code based upon that. Now, if Foo.cpp is good C++ code, it should only #include header files. Thus, if Foo refers to a Bar object, it only accesses the method names in Bar.h.

In fact, the only thing the compiler does is to make sure the any calls to Bar methods have the correct number of arguments and types. It doesn't create code for those Bar methods! Why not? It doesn't have access to code in Bar methods! That code will be created when Bar.cpp is compiled. Foo.cpp will eventually have access to the code in Bar.cpp at the linking phase. When code is linked, the linker sees that Foo methods require access to Bar methods, and looks for Bar code (which is in the object code, Bar.o). The job of the linker is to find code that is provided by other objects (it mainly does "address resolution").

Normally, this works just fine. However, template classes create a problem.

Suppose, in main.cpp, you declare a variable of type SimpleMap<string, Movie>. When does the code for the instantiation of this class get generated by the compiler?

There are two choices:

• when compiling the file with the instantiation of the template class
• when compiling the template class

As it turns out, both have problems.

Can the code for SimpleMap class be generated when main.cpp is being compiled? The answer is no. Why not? main.cpp includes #include "SimpleMap.h", which is merely the header file. There is no code in the header file!

How about when SimpleMap.cpp is compiled? Is it possible to generate the code for SimpleMap<string, Movie>? The answer is no. Consider the following. What would it take to compile SimpleMap<string, Movie>? It requires function calls to string and Movie methods. The minimum requirement is checking to see if the methods exist for these classes, which requires the header files for string and Movie.

Does it make any sense to have the header files for these two classes in SimpleMap? Not really. Even if you include these files in SimpleMap, what happens to future instantiations?

In fact, consider this very likely scenario. Some company has produced some code, and you've bought it. They provide only header files and object files. Thus, you can not recompile the object code. You wish to instantiate SimpleMap to a Student and URL class, both of which you've written recently.

When the code for SimpleMap.o was created, there was no way the programmers would know that you wanted to instantiate it to Student and URL.

Template code is tricky because it is code that is not quite complete. It requires the instantiated types to generate the code. Because of this, solutions to the problem are not nice and clean.

We'll look at four different solutions to the problem.

Four Solutions to Template Instantiation

1. #include the .cpp file at the end of the header

   In SimpleMap.h, you #include the .cpp file. It looks like:

   #ifndef SIMPLE_MAP_H
   #define SIMPLE_MAP_H
   
   template <typename First, typename Second>
   class SimpleMap
   {
     // code
   };
   
   // Include the .cpp file
   #include "SimpleMap.cpp"
   #endif
   

   This is a nice, simple solution, but violates one of the principles of header files: don't #include the .cpp file!

   Why does this work? Let's consider main.cpp. In that file, there is a declaration of a SimpleMap<string, Movie> object. Normally, if you include the header, there is not enough information to create code for the object. However, this time you are including both the header file and the implementation. Both pieces of information are enough to create the code.

   The only thing you have to remember is the following: don't compile SimpleMap.cpp and link in SimpleMap.o. For some reason, the compiler objects to linking this code.

   You might think that if you had two files that wanted to use SimpleMap (say, Foo and Bar), and both included SimpleMap.h, then the compiler would complain about SimpleMap.cpp being included and compiled twice. Yet, surprisingly, it doesn't complain in g++ and cxx (although, it may depend on your compiler).

   The good news about this solution is that it requires very little typing. The bad news is that including .cpp code in .h files seems like poor coding practice, and you have to remember NOT to compile and link in the .cpp code.

   Using this technique requires some special care when writing makefiles. In particular, any file that requires a template class file must include, in its dependencies, both the header AND the implementation file.

   For example, if main.cpp includes a declaration for SimpleMap<string, Movie>, then in the makefile, the line for main.o must include SimpleMap.h AND SimpleMap.cpp.

   Why? Recall that SimpleMap.o is not being linked in. When either the header file or the implementation file (the .cpp file) is modified, then the only way to pass that information to the file that uses SimpleMap is to recompile that file. Thus, a change to SimpleMap.cpp needs to cause main.cpp to be recompiled.

2. Write an instantiation file

   The main problem with the previous approach is the awkward including of the .cpp file in the header file. Instantiation files allow you to avoid this problem, but create more problems of their own.

   An instantiation file is a file that includes "declarations" of all the template classes and template functions you want to use. For example, suppose there is a findMin function template and a SimpleMap class template. You look at all the files you want to compile, and figure out how the templates have been instantiated and place them into the instantiation file.

   For example, suppose you want to call findMin on a string array, a Movie array, and a Student array, and you wish to instantiate SimpleMap as shown earlier.

   Create a file called, say, templateInst.cpp.

   #include <string>
   #include "findMin.cpp"    // still include implementation file
   #include "SimpleMap.cpp"  // still include implementation file
   
   #include "Movie.h"   // include header file for non-template classes
   #include "Student.h" // include header file for non-template classes
   
   // Specific instantiations for function template, findMin
   template string  findMin(string arr[], int size);
   template Movie   findMin(Movie arr[], int size);
   template Student findMin(Student arr[], int size);
   
   // Specific instantiations for class template, SimpleMap
   template class SimpleMap<string, Movie>
   template class SimpleMap<string, Student>
   template class SimpleMap<int, float>
   

   This file consists of all the instantiations you will use in the executable. In effect, you are listing out all the instantiation files. Notice that you tell the compiler that you simply want to instantiate by using the keyword "template" in front of what appears to be prototypes of functions or template types, with the types plugged in.

   Just as in the previous solution, you #include .cpp files (but only for template classes and functions---not for non-template classes/functions).

   You compile this file to produce templateInst.o. You do NOT compile findMin.cpp or SimpleMap.cpp since all that information is already in templateInst.cpp.

   Is this solution any better than the first solution? Yes and no. It is better because the header files no longer include .cpp files. It is worse because you have to include all instantiations in this file. If you need to add a new instantiation, you add it to this file. Still, it is a solution that does get practically used (and is supposed to work with Visual C++).

3. the cxx solution

   This solution is a hack, but a clever hack. Basically, whenever a template instantiation occurs, it looks for the implementation file. For example, suppose main.cpp declares a SimpleMap<string, Movie>, object and #include "SimpleMap.h", the compiler assumes that the there must be a SimpleMap.cpp file (or a SimpleMap.cc file), i.e., some file with the correct extension.

   When it locates SimpleMap.cpp, it uses the information in there, and compiles code for each of the methods. Where does the object code go? cxx creates a directory called cxx_repository and places the object code for each SimpleMap method in there. That is, each method as instantiated to string and Movie,

   When the compiler links the code, not only does it look at the .o files being linked, it also looks inside the cxx_reposistory and uses those files too.

   In effect, it gets around the problem of including the .cpp file by looking for the .cpp file when it includes the .h file and determines the .h file holds a function or class template.

   This solution is somewhat better than the first solution, but isn't all that portable. It works fine with cxx, but you have to see if other compilers work this way. Alas, it requires source code for the template classes, or it doesn't work.

4. the powerful linker solution

   The best solution, one that seems not to have been implemented (but I haven't looked hard) is to simply create a powerful linker. Recall the problem from the previous section. The compiler lacks enough information to generate the template code. It doesn't have enough information when a function template is used or a class template is used, because the implementation code is located in the .cpp file of the function or class template.

   There is also not enough in the function or class template file because you simply don't know what type the function or class template will be instantiated to.

   However, this information is known at link time. When the compiler is linking object code, it should notice that main.o, for example, requires the code from SimpleMap, so the linker should obtain that information from SimpleMap.o, and then generate the code needed to create, say, code for SimpleMap<string, Movie>.

   Unfortunately, linkers were never meant to generate new code, only to link .o files together (essentially, .o files provide functions and require functions, and the linker determines who needs what and locates it).

   This solution would mean no cxx_repository and would allow a software vendor to provide only .o files and header files, and not have to reveal their .cpp files. The other three solutions appear to require the need to reveal .cpp files (unless there is some cleverness to hide that). Furthermore, this solution allows you to treat template classes like regular classes, and that is what should have been done in the first place.

Which One to Pick?

The "cxx" solution is the one you must use in your submitted code. However, if you are coding mainly on another compiler, use one that works and after transferring your code to your bt or jm account, use the cxx method.

Web Accessibility