Categories
Code

Don’t Define Template Functions In .cpp Files

This is another gotcha from my recent C++ work. When I learned C++ I was taught to put the interface (function declarations) in a header file and the implentation (function definitions) in a .cpp module source file. Some small functions could be written inline in the class declarations, usually just get/set member functions for private data. At one point (or possibly just in C) having if/else statements in a header was not allowed, the compiler complained about branching. I recently realized (about 10 years after everyone else, it seems) that there is actually a very good reason to put implementation of templated functions in the header file.

Recently I was working on my interpolation classes, which are templates, like

template 
class Interpolation1D : public Interpolation
{
public:
    ...
    T GetValue(const T& x)
    {
        // vectors hold interpolation points and values near 'x'
        vector xa(_order), ya(_order); 
        ...    // set up the points to interpolate
        return Neville (_order, xa, ya, x);
    }
protected:
    ...
};

The function GetValue(x) retrieved the interpolated value of the function position x. The Interpolation2D class has a similar GetValue(x,y) member. Both of these GetValue functions use Neville’s algorithm to determine the value at the interpolation point, which is a pretty fast polynomial approximation technique. In fact, they basically do exactly the same thing, except the 2-D version builds an intermediate 1-D set of values (using Neville’s algorithm) and then interpolates that in the same manner as the 1-D version.

Naturally I wrote a function to perform the Neville interpolation, and that too had to be templated, in order to be used inside the templated interpolation classes.

template 
T Neville(const size_t& order, const vector& xa, 
         const vector& ya, const T& x)
{ ... }

I put the declaration for the Neville function in the header file interpolation.h, and the implentation in interpolation.cpp. Everything compiled just fine (I compiled this into a library) but when I came to link the main program, which used a Interpolation1D instance, the compiler started complaining that it couldn’t find the double version of Neville:

double Neville(const size_t&, const vector&, 
       const vector&, const double)

I spent a good while double checking the function declaration was the same as the definition (since the main program did compile, only the linking failed. Using nm to examine the object code in interpolation.o showed that in fact NO version of Neville() was present.

Anyway, to cut a long story short, the answer is one of those C++ things that is obvious after you figure it out: The compiler, when it compiles interpolation.cpp into interpolation.o, only builds creates implentations of templated functions that it sees are being used, in this case, none, since no code within interpolation.cpp calls Neville (or Neville).

The solution was to move the definition of Neville into interpolation.h, which is #included in the interpolation1d.h file. When the compiler builds an object file relying on the Interpolation1D class (ie code which #includes interpolation1d.h and hence interpolation.h) it sees that it needs to create the object code for Neville and does so.