Overloading operator<< for a templated class

Question

I'm trying to implement a method for a binary tree which returns a stream. I want to use the stream returned in a method to show the tree in the screen or to save the tree in a file:

These two methods are in the class of the binary tree:

Declarations:

void streamIND(ostream&,const BinaryTree<T>*);
friend ostream& operator<<(ostream&,const BinaryTree<T>&);

template <class T>
ostream& operator<<(ostream& os,const BinaryTree<T>& tree) {
    streamIND(os,tree.root);
    return os;
}

template <class T>
void streamIND(ostream& os,Node<T> *nb) {
    if (!nb) return;
    if (nb->getLeft()) streamIND(nb->getLeft());
    os << nb->getValue() << " ";
    if (nb->getRight()) streamIND(nb->getRight());
}

This method is in UsingTree class:

void UsingTree::saveToFile(char* file = "table") {
    ofstream f;
    f.open(file,ios::out);
    f << tree;
    f.close();
}

So I overloaded the operator "<<" of the BinaryTree class to use: cout << tree and ofstream f << tree, but I receive the next error message: undefined reference to `operator<<(std::basic_ostream >&, BinaryTree&)'

P.S. The tree stores Word objects (a string with an int).

I hope you understand my poor English. Thank you! And I'd like to know a good text for beginners about STL which explains all necessary because i waste all my time in errors like this.

EDIT: tree in saveToFile() is declared: BinaryTree< Word > tree.

Answer 1

The problem is that the compiler is not trying to use the templated operator<< you provided, but rather a non-templated version.

When you declare a friend inside a class you are injecting the declaration of that function in the enclosing scope. The following code has the effect of declaring (and not defining) a free function that takes a non_template_test argument by constant reference:

class non_template_test
{
   friend void f( non_template_test const & );
};
// declares here:
// void f( non_template_test const & ); 

The same happens with template classes, even if in this case it is a little less intuitive. When you declare (and not define) a friend function within the template class body, you are declaring a free function with that exact arguments. Note that you are declaring a function, not a template function:

template<typename T>
class template_test
{
    friend void f( template_test<T> const & t );
};
// for each instantiating type T (int, double...) declares:
// void f( template_test<int> const & );
// void f( template_test<double> const & );

int main() {
    template_test<int> t1;
    template_test<double> t2;
}

Those free functions are declared but not defined. The tricky part here is that those free functions are not a template, but regular free functions being declared. When you add the template function into the mix you get:

template<typename T> class template_test {
   friend void f( template_test<T> const & );
};
// when instantiated with int, implicitly declares:
// void f( template_test<int> const & );

template <typename T>
void f( template_test<T> const & x ) {} // 1

int main() {
   template_test<int> t1;
   f( t1 );
}

When the compiler hits the main function it instantiates the template template_test with type int and that declares the free function void f( template_test<int> const & ) that is not templated. When it finds the call f( t1 ) there are two f symbols that match: the non-template f( template_test<int> const & ) declared (and not defined) when template_test was instantiated and the templated version that is both declared and defined at 1. The non-templated version takes precedence and the compiler matches it.

When the linker tries to resolve the non-templated version of f it cannot find the symbol and it thus fails.

What can we do? There are two different solutions. In the first case we make the compiler provide non-templated functions for each instantiating type. In the second case we declare the templated version as a friend. They are subtly different, but in most cases equivalent.

Having the compiler generate the non-templated functions for us:

template <typename T>
class test 
{
   friend void f( test<T> const & ) {}
};
// implicitly

This has the effect of creating as many non-templated free functions as needed. When the compiler finds the friend declaration within the template test it not only finds the declaration but also the implementation and adds both to the enclosing scope.

Making the templated version a friend

To make the template a friend we must have it already declared and tell the compiler that the friend we want is actually a template and not a non-templated free function:

template <typename T> class test; // forward declare the template class
template <typename T> void f( test<T> const& ); // forward declare the template
template <typename T>
class test {
   friend void f<>( test<T> const& ); // declare f<T>( test<T> const &) a friend
};
template <typename T> 
void f( test<T> const & ) {}

In this case, prior to declaring f as a template we must forward declare the template. To declare the f template we must first forward declare the test template. The friend declaration is modified to include the angle brackets that identify that the element we are making a friend is actually a template and not a free function.

Back to the problem

Going back to your particular example, the simplest solution is having the compiler generate the functions for you by inlining the declaration of the friend function:

template <typename T>
class BinaryTree {
   friend std::ostream& operator<<( std::ostream& o, BinaryTree const & t ) {
      t.dump(o);
      return o;
   }
   void dump( std::ostream& o ) const;
};

With that code you are forcing the compiler into generating a non-templated operator<< for each instantiated type, and that generated function delegates on the dump method of the template.

Answer 2

you dont need the template operator declaration and you have to declare the operator "friend" for your class to have granted access to other classes, in this case std::cout

friend std::ostream& operator << ( std::ostream& os, BinaryTree & tree )
{
    doStuff( os, tree );
    return os;
}

recomended reading: http://www.parashift.com/c++-faq-lite/friends.html

Answer 3

When overloading the << operator you want to use a const reference:

template <class T>
std::ostream& operator << (std::ostream& os, const BinaryTree<T>& tree) 
{
    // output member variables here... (you may need to make
    // this a friend function if you want to access private
    // member variables...

    return os;
}