C++ template function compiles in header but not implementation

Question

I'm trying to learn templates and I've run into this confounding error. I'm declaring some functions in a header file and I want to make a separate implementation file where the functions will be defined. Here's the code that calls the header (dum.cpp):

#include <iostream>
#include <vector>
#include <string>
#include "dumper2.h"

int main() {
    std::vector<int> v;
    for (int i=0; i<10; i++) {
        v.push_back(i);
    }
    test();
    std::string s = ", ";
    dumpVector(v,s);
}

Now, here's a working header file (dumper2.h):

#include <iostream>
#include <string>
#include <vector>

void test();

template <class T> void dumpVector( std::vector<T> v,std::string sep);

template <class T> void dumpVector(std::vector<T> v, std::string sep) {
    typename std::vector<T>::iterator vi;

    vi = v.begin();
    std::cout << *vi;
    vi++;
    for (;vi<v.end();vi++) {
        std::cout << sep << *vi ;
    }
    std::cout << "\n";
    return;
}

With implementation (dumper2.cpp):

#include <iostream>
#include "dumper2.h"

void test() {
    std::cout << "!olleh dlrow\n";
}

The weird thing is that if I move the code that defines dumpVector from the .h to the .cpp file, I get the following error.

g++ -c dumper2.cpp -Wall -Wno-deprecated
g++ dum.cpp -o dum dumper2.o -Wall -Wno-deprecated
/tmp/ccKD2e3G.o: In function `main':
dum.cpp:(.text+0xce): undefined reference to `void dumpVector<int>(std::vector<int, std::allocator<int> >, std::basic_string<char, std::char_traits<char>, std::allocator<char> >)'
collect2: ld returned 1 exit status
make: *** [dum] Error 1

So why does it work one way and not the other? Clearly the compiler can find test(), so why can't it find dumpVector?

Solution 1

The problem you're having is that the compiler doesn't know which versions of your template to instantiate. When you move the implementation of your function to x.cpp it is in a different translation unit from main.cpp, and main.cpp can't link to a particular instantiation because it doesn't exist in that context. This is a well-known issue with C++ templates. There are a few solutions:

1) Just put the definitions directly in the .h file, as you were doing before. This has pros & cons, including solving the problem (pro), possibly making the code less readable & on some compilers harder to debug (con) and maybe increasing code bloat (con).

2) Put the implementation in x.cpp, and #include "x.cpp" from within x.h. If this seems funky and wrong, just keep in mind that #include does nothing more than read the specified file and compile it as if that file were part of x.cpp In other words, this does exactly what solution #1 does above, but it keeps them in seperate physical files. When doing this kind of thing, it is critical that you not try to compile the #included file on it's own. For this reason, I usually give these kinds of files an hpp extension to distinguish them from h files and from cpp files.

File: dumper2.h

#include <iostream>
#include <string>
#include <vector>

void test();
template <class T> void dumpVector( std::vector<T> v,std::string sep);
#include "dumper2.hpp"

File: dumper2.hpp

template <class T> void dumpVector(std::vector<T> v, std::string sep) {
  typename std::vector<T>::iterator vi;

  vi = v.begin();
  std::cout << *vi;
  vi++;
  for (;vi<v.end();vi++) {
    std::cout << sep << *vi ;
  }
  std::cout << "\n";
  return;

}

3) Since the problem is that a particular instantiation of dumpVector is not known to the translation unit that is trying to use it, you can force a specific instantiation of it in the same translation unit as where the template is defined. Simply by adding this: template void dumpVector<int>(std::vector<int> v, std::string sep); ... to the file where the template is defined. Doing this, you no longer have to #include the hpp file from within the h file:

File: dumper2.h

#include <iostream>
#include <string>
#include <vector>

void test();
template <class T> void dumpVector( std::vector<T> v,std::string sep);

File: dumper2.cpp

template <class T> void dumpVector(std::vector<T> v, std::string sep) {
  typename std::vector<T>::iterator vi;

  vi = v.begin();
  std::cout << *vi;
  vi++;
  for (;vi<v.end();vi++) {
    std::cout << sep << *vi ;
  }
  std::cout << "\n";
  return;
}

template void dumpVector<int>(std::vector<int> v, std::string sep);

By the way, and as a total aside, your template function is taking a vector by-value. You may not want to do this, and pass it by reference or pointer or, better yet, pass iterators instead to avoid making a temporary & copying the whole vector.

Solution 2

This was what the export keyword was supposed to accomplish (i.e., by exporting the template, you'd be able to put it in a source file instead of a header. Unfortunately, only one compiler (Comeau) ever really implemented export completely.

As to why the other compilers (including gcc) didn't implement it, the reason is pretty simple: because export is extremely difficult to implement correctly. Code inside the template can change meaning (almost) completely, based on the type over which the template is instantiated, so you can't generate a conventional object file of the result of compiling the template. Just for example, x+y might compile to native code like mov eax, x/add eax, y when instantiated over an int, but compile to a function call if instantiated over something like std::string that overloads operator+.

To support separate compilation of templates, you have to do what's called two-phase name lookup (i.e., lookup the name both in the context of the template and in the context where the template is being instantiated). You typically also have the compiler compile the template to some sort of database format that can hold instantiations of the template over an arbitrary collection of types. You then add in a stage between compiling and linking (though it can be built into the linker, if desired) that checks the database and if it doesn't contain code for the template instantiated over all the necessary types, re-invokes the compiler to instantiate it over the necessary types.

Due to the extreme effort, lack of implementation, etc., the committee has voted to remove export from the next version of the C++ standard. Two other, rather different, proposals (modules and concepts) have been made that would each provide at least part of what export was intended to do, but in ways that are (at least hoped to be) more useful and reasonable to implement.

Solution 3

Template parameters are resolved as compile time.

The compiler finds the .h, finds a matching definition for dumpVector, and stores it. The compiling is finished for this .h. Then, it continues parsing files and compiling files. When it reads the dumpVector implementation in the .cpp, it's compiling a totally different unit. Nothing is trying to instantiate the template in dumper2.cpp, so the template code is simply skipped. The compiler won't try every possible type for the template, hoping there will be something useful later for the linker.

Then, at link time, no implementation of dumpVector for the type int has been compiled, so the linker won't find any. Hence why you're seeing this error.

The export keyword is designed to solve this problem, unfortunately few compilers support it. So keep your implementation with the same file as your definition.

Solution 4

A template function is not real function. The compiler turns a template function into a real function when it encounters a use of that function. So the entire template declaration has to be in scope it finds the call to DumpVector, otherwise it can't generate the real function.
Amazingly, a lot of C++ intro books get this wrong.

Solution 5

This is exactly how templates work in C++, you must put the implementation in the header.

When you declare/define a template function, the compiler can't magically know which specific types you may wish to use the template with, so it can't generate code to put into a .o file like it could with a normal function. Instead, it relies on generating a specific instantiation for a type when it sees the use of that instantiation.

So when the implementation is in the .C file, the compiler basically says "hey, there are no users of this template, don't generate any code". When the template is in the header, the compiler is able to see the use in main and actually generate the appropriate template code.

View more solutions