Templates Mangling my Mind

[wulfsdad]

For my data-structures class, I am attempting to create a binary search tree template to be used to create an AVL tree. I've written a Generic_Tree template for the BST to inherit from, and before I jump into implementing the AVL tree I'm testing the BST member functions. Everything was compiling fine until I added the
BST insert() function. Now, I'm getting the following error message from my linker:

undefined reference to 'BST<void>::insert(int, void*)'

Stemming from the call in main line 16.

my makefile compiles with:
g++ -Wall -g Generic_Tree.cpp BST.cpp barfing.cpp main.cpp

Generic_Tree:

template < typename NODE_DATA, unsigned MAX_KIDS >
class Tree
{
   protected:
      struct NODE {
         NODE_DATA* contents;
         Tree* child[MAX_KIDS];
         Tree* parent;
      };
      
      NODE* root;
...

};/* End Tree Class Template */

BST:

#include "Generic_Tree.h"

#define NO_KEY -1
typedef int KEY;

template < typename NODE_DATA >
class BST : protected Tree<NODE_DATA,2>
{
   protected:
      KEY value;
      using Tree<NODE_DATA,2>::root;
      using typename Tree<NODE_DATA,2>::NODE;
      
      void set_key(KEY);
   public:
      /* Constructors & Destructor */
      BST(){ value = 0; }
     ~BST(){;}
     
      /* KEY Retrieval Functions */
      KEY get_key() const { return value; }
      KEY min() const;
      KEY max() const;
      KEY predecessor() const;
      KEY successor() const;
      
      NODE_DATA* search(KEY) const;
      
      /* Structure Manipulation Functions */
      void insert(KEY, NODE_DATA*);
//       void remove(KEY);
      
};/* End BST Template */

...

template < typename NODE_DATA >
void BST<NODE_DATA>::insert( KEY nukey , NODE_DATA* nudat )
{
   if( root.is_empty() ) {
      root = new typename Tree<NODE_DATA,2>::NODE;
      root.set_key(nukey);
      root.contents = nudat;
   } else if( root.get_key() > nukey ) root.child[LEFT].insert(nukey,nudat);
   else root.child[RIGHT].insert(nukey,nudat);
}/* End insert Func */

main:

int main(int argc, char* argv[])
{
   BST<void> The_Tree;
   KEY nukey = NO_KEY;
   int job = REDO;
   bool run = true;
   bool auto_print = display_intro();
   
   
   while( run )
   {	
      while( (job = menu( &nukey )) == REDO );
      if( job == QUIT   ) run = false;
      else{
         cout << "Not Quitting... ";
         if( job == INSERT ) The_Tree.insert( nukey, NULL );//cout << "\nKEY: " << nukey << endl;//
         if( job == DELETE ) cout << "\nKEY: " << nukey << endl;//The_Tree.remove( nukey );
         if(( job == PRINT  )||( auto_print )) ;//;The_Tree.display( INORDER );
      }/* end job processing if-else */
   }/* end run while */
   
	return 0;
}/* end main func */

I'm use to c and havn't used classes or templates before (except for declaring instances of them). The whole syntax is mystifying to me, I would appreciate some elucidation.

[Cubbi]

undefined reference to 'BST<void>::insert(int, void*)'

That's probably the simplest problem to fix here: templates go into header files, not into the cpp files.

Remember, C++ has a separate compilation model: when the compiler compiles BST.cpp, it has no idea that somewhere out there exists a main.cpp that will try to instantiate BST<void>. As far as it knows, nobody needs this template, no code is compiled.

[wulfsdad]

templates go into header files, not into the cpp files.

I have the templates and their member prototypes in header files and the member function implementations in cpp files. What I've pasted above under BST is the header, "...", and part of the cpp (sorry, I was trying to save space). I also didn't past above that in main I #include "BST.h". Is my problem with my g++ usage?

[ne555]

The implementation should be in the header too
http://cplusplus.com/forum/general/91603/#msg492300

(this is getting ridiculous common, ¿where is the FAQ?)

[cire]

(this is getting ridiculous common, ¿where is the FAQ?)

http://www.parashift.com/c++-faq-lite/separate-template-class-defn-from-decl.html