Skip to main content
gamedev.net
🔒 Locked

linker errors in my templated binary tree code

Started by guywithknife 6 replies 1.5k views
Original Post
guywithknife
guywithknife
I keep getting linker errors (undefined references) with the following code: 

BinaryTree<int, int> foo;
foo.insert(1, 10);
This gives the following linker errors: 

[Linker error] undefined reference to `BinaryTree<int, int>::_insert(BinaryTree<int, int>::Node*, int&, int&)' 
[Linker error] undefined reference to `BinaryTree<int, int>::_clear(BinaryTree<int, int>::Node*)'
If I call other member functions I get a linker error for the corresponding private members too. Heres my BinaryTree code: binarytree.h 


#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

#include <vector>
#include <utility>

template <class DATA, class KEY>
class BinaryTree
{
private:
	struct Node {
		DATA data;
		KEY key;
		Node* left;
		Node* right;
	};
	Node* root;
	
	bool _insert 			(Node*, KEY&, DATA&);
	bool _find 				(Node*, KEY&, DATA&);
	bool _remove 			(Node*, KEY&);
	void _traverseInOrder 	(Node*, std::vector<std::pair<KEY, DATA> >&);
	void _traversePreOrder 	(Node*, std::vector<std::pair<KEY, DATA> >&);
	void _traversePostOrder (Node*, std::vector<std::pair<KEY, DATA> >&);
	void _clear 			(Node*);
	
public:
	BinaryTree () {root = NULL;}
	~BinaryTree () {clear();}
	
	inline bool insert   (KEY key, DATA data) {return _insert(root, key, data);}
	inline bool find     (KEY key, DATA data) {return _find(root, key, data);  }
	inline bool remove   (KEY key) 			{return _remove(root, key);		 }
	inline void traverse (	std::vector<std::pair<KEY, DATA> >& list,
							unsigned int type)
	{
		if (type == InOrder)
		{
			_traverseInOrder(root, list);
		} else if (type == PreOrder)
		{
			_traversePreOrder(root, list);
		} else if (type == PostOrder)
		{
			_traversePostOrder(root, list);
		}
	}
	inline void clear () {_clear(root); root=NULL;}
	
	inline DATA operator[] (KEY k)
	{
		DATA d;
		find(k, d);
		return d;
	}
	inline void operator() (KEY& k, DATA& d) {insert(k, d);}
	
	static const unsigned int InOrder	= 0;
	static const unsigned int PreOrder	= 1;
	static const unsigned int PostOrder	= 2; 
};
#endif
binarytree.cpp 

#include "binarytree.h"

template <class DATA, class KEY>
bool BinaryTree<DATA, KEY>::_insert (Node* cur, KEY& k, DATA& d)
{
	if (cur)
	{
		if (cur->key == k)
		{
			return false;
		} else if (cur->key > k)
		{
			return _insert(cur->left, k, d);
		} else {
			return _insert(cur->right, k, d);
		}
	} else {
		Node* temp = new Node;
		temp->left = NULL;
		temp->right = NULL;
		temp->data = d;
		temp->key = k;
		cur = temp;
		return true;
	}
}

template <class DATA, class KEY>
bool BinaryTree<DATA, KEY>::_find (Node* cur, KEY& k, DATA& d)
{
	if (cur)
	{
		if (cur.key == k)
		{
			d = cur.data;
			return true;
		} else if (cur.key > k)
		{
			return _find(cur->left, k, d);
		} else {
			return _find(cur->right, k, d);
		}
	} else {
		return false;
	}
}

template <class DATA, class KEY>
bool BinaryTree<DATA, KEY>::_remove (Node* cur, KEY& k)
{
	if (cur)
	{
		if (cur->key == k)
		{
			Node* temp = cur;
			cur = temp->left;
			_insert(cur, (temp->right)->key, (temp->right)->data);
			delete temp;
			return true;
		} else if (cur->key > k)
		{
			return _remove(cur->left, k);
		} else {
			return _remove(cur->right, k);
		}
	} 
	return false;
}

template <class DATA, class KEY>
void BinaryTree<DATA, KEY>::_traverseInOrder (Node* cur, std::vector<std::pair<KEY, DATA> >& list)
{
	if (cur->left) _traverseInOrder(cur->left, list);
	list.push_back(std::pair<KEY, DATA>(sur->key, cur->data));
	if (cur->right) _traverseInOrder(cur->right, list);
}

template <class DATA, class KEY>
void BinaryTree<DATA, KEY>::_traversePreOrder (Node* cur, std::vector<std::pair<KEY, DATA> >& list)
{
	list.push_back(std::pair<KEY, DATA>(sur->key, cur->data));
	if (cur->left) _traverseInOrder(cur->left, list);
	if (cur->right) _traverseInOrder(cur->right, list);		
}

template <class DATA, class KEY>
void BinaryTree<DATA, KEY>::_traversePostOrder (Node* cur, std::vector<std::pair<KEY, DATA> >& list)
{
	if (cur->left) _traverseInOrder(cur->left, list);
	if (cur->right) _traverseInOrder(cur->right, list);
	list.push_back(std::pair<KEY, DATA>(sur->key, cur->data));
}

template <class DATA, class KEY>
void BinaryTree<DATA, KEY>::_clear (Node* cur)
{
	if (cur->left) _clear(cur->left);
	if (cur->right) _clear(cur->right);
	delete cur;
}
Any suggestions would be greatly appreciated. [Edited by - issch on April 7, 2005 12:21:30 PM]
_DarkWIng_
_DarkWIng_
Someone can probably explain it better but the point is that you can't split template like that. Copy all the code from .cpp to .h and it will work.
You should never let your fears become the boundaries of your dreams.
Toolmaker
Toolmaker
You've made a common mistake with templates:
You seperated the implementations from the definitions. In other words: You're using a .h for the class definition and a .cpp for the implementations.

Solution is to move all your code into the header. That, or using extern, but I haven't tried that as I always wrote my templated code IN the headers.

Toolmaker
 
snk_kid
snk_kid
unless your compiler supports the export keyword (which nearly none do) templates must be defined in the same translation unit they where declared in, meaning you need to put definitions in the header, you can still define them outside the class they just need to be in the same translation unit.
guywithknife
guywithknife
Thanks for the replies.
I guess I'll do that, but I was sure I saw templated code split like that somewhere before..


EDIT:
The template tutorial here has templates split amongst files:

B.h
template <class t>class b{public:	b() ;	~b() ;} ;


B.cpp
#include "B.H"template <class t>b<t>::b(){}template <class t>b<t>::~b(){}


main.cpp
#include "B.H"void main(){	 b<int> bi ;	 b <float> bf ;}
snk_kid
snk_kid
Quote:
Original post by issch
but I was sure I saw templated code split like that somewhere before..


It's really not split, they just put the definitions into some file and include it at the end of the header it's not really the samething.
snk_kid
snk_kid
Quote:
Original post by issch
EDIT:
The template tutorial here has templates split amongst files:


If that is the actual example it's incorrect, it wont work unless your compiler supports export which i can pretty much guarnetee yours wont, the closest you'll get to that is putting the definition into some file and including at the end of the header but it's not the same.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.