Undefined reference to function template when used with string (GCC)

Question

I need to write a templated function replace_all in C++ which will take a string, wstring, glibmm::ustring etc. and replace all occurrences of search in subject with replace.

replace_all.cc

template < class T >
T replace_all(
        T const &search,
        T const &replace,
        T const &subject
) {
        T result;

        typename T::size_type done = 0;
        typename T::size_type pos;
        while ((pos = subject.find(search, done)) != T::npos) {
                result.append (subject, done, pos - done);
                result.append (replace);
                done = pos + search.size ();
        }
        result.append(subject, done, subject.max_size());
        return result;
}

test.cc

#include <iostream>

template < class T >
T replace_all(
        T const &search,
        T const &replace,
        T const &subject
);

// #include "replace_all.cc"

using namespace std;

int main()
{
        string const a = "foo bar fee boor foo barfoo b";
        cout << replace_all<string>("foo", "damn", a) << endl;
        return 0;
}

When I try to compile this using gcc 4.1.2

g++ -W -Wall -c replace_all.cc  
g++ -W -Wall -c test.cc  
g++ test.o replace_all.o  

I get:

test.o: In function `main':
test.cc:(.text+0x13b): undefined reference to `
   std::basic_string<char, std::char_traits<char>, std::allocator<char> >
   replace_all< std::basic_string<char, std::char_traits<char>, std::allocator<char> > >(
       std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&,
       std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&,
       std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&
   )
'
collect2: ld returned 1 exit status

But when I uncomment #include "replace_all.cc" in test.cc and compile this way:

g++ -W -Wall test.cc

The program links and produces expected output:

damn bar fee boor damn bardamn b

Why linking fails and what can I do to make it work?

Solution 1

You can't link templates as compiler don't know which code to generate before someone tries to use ( instantiate ) templates.

You can "ask" compiler to instantiate template if you knows which types are you going to use or if you know that they are limited.
If you want - put this to your .cc file:

template std::string replace_all( std::string const& search,
                                  std::string const& replace,
                                  std::string const& subject );


template glibmm::ustring replace_all( glibmm::ustring const& search,
                                      glibmm::ustring const& replace,
                                      glibmm::ustring const& subject );

Solution 2

The compiler needs to see the template definition at the point of instantiation, else the code specialized for the type you instantiate the template with cannot be generated. The correct way is to put the implementation of the template functions in the header file or to #include the .cc like you did.