Caveat: It is not necessary to put the implementation in the header file, see the alternative solution at the end of this answer.

Anyway, the reason your code is failing is that, when instantiating a template, the compiler creates a new class with the given template argument. For example:

template<typename T>
struct Foo
{
    T bar;
    void doSomething(T param) {/* do stuff using T */}
};

// somewhere in a .cpp
Foo<int> f; 

When reading this line, the compiler will create a new class (let's call it FooInt), which is equivalent to the following:

struct FooInt
{
    int bar;
    void doSomething(int param) {/* do stuff using int */}
};

Consequently, the compiler needs to have access to the implementation of the methods, to instantiate them with the template argument (in this case int). If these implementations were not in the header, they wouldn't be accessible, and therefore the compiler wouldn't be able to instantiate the template.

A common solution to this is to write the template declaration in a header file, then implement the class in an implementation file (for example .tpp), and include this implementation file at the end of the header.

Foo.h

template <typename T>
struct Foo
{
    void doSomething(T param);
};

#include "Foo.tpp"

Foo.tpp

template <typename T>
void Foo<T>::doSomething(T param)
{
    //implementation
}

This way, implementation is still separated from declaration, but is accessible to the compiler.

Alternative solution

Another solution is to keep the implementation separated, and explicitly instantiate all the template instances you'll need:

Foo.h

// no implementation
template <typename T> struct Foo { ... };

Foo.cpp

// implementation of Foo's methods

// explicit instantiations
template class Foo<int>;
template class Foo<float>;
// You will only be able to use Foo with int or float

If my explanation isn't clear enough, you can have a look at the C++ Super-FAQ on this subject.

The reason Herb said what he said is because of cases like this.

Let's say I have function A which calls function B, which calls function C. And A passes a string through B and into C. A does not know or care about C; all A knows about is B. That is, C is an implementation detail of B.

Let's say that A is defined as follows:

void A()
{
  B("value");
}

If B and C take the string by const&, then it looks something like this:

void B(const std::string &str)
{
  C(str);
}

void C(const std::string &str)
{
  //Do something with `str`. Does not store it.
}

All well and good. You're just passing pointers around, no copying, no moving, everyone's happy. C takes a const& because it doesn't store the string. It simply uses it.

Now, I want to make one simple change: C needs to store the string somewhere.

void C(const std::string &str)
{
  //Do something with `str`.
  m_str = str;
}

Hello, copy constructor and potential memory allocation (ignore the Short String Optimization (SSO)). C++11's move semantics are supposed to make it possible to remove needless copy-constructing, right? And A passes a temporary; there's no reason why C should have to copy the data. It should just abscond with what was given to it.

Except it can't. Because it takes a const&.

If I change C to take its parameter by value, that just causes B to do the copy into that parameter; I gain nothing.

So if I had just passed str by value through all of the functions, relying on std::move to shuffle the data around, we wouldn't have this problem. If someone wants to hold on to it, they can. If they don't, oh well.

Is it more expensive? Yes; moving into a value is more expensive than using references. Is it less expensive than the copy? Not for small strings with SSO. Is it worth doing?

It depends on your use case. How much do you hate memory allocations?