Sign in to follow this  
RandomPixel

Link errors with templates

Recommended Posts

Could anyone help me fix this? It's driving me crazy. :( I'm trying to use a Binary Search Tree template. But can't understand how to use it. Errors:
error LNK2019: unresolved external symbol "public: class BSTNode<int> * * __thiscall BinarySearchTree<int>::search(int)"
 (?search@?$BinarySearchTree@H@@QAEPAPAV?$BSTNode@H@@H@Z) referenced in function _WinMain@16

error LNK2019: unresolved external symbol "public: void __thiscall BinarySearchTree<int>::insert(int)" (?insert@?$BinarySearchTree@H@@QAEXH@Z) 
referenced in function _WinMain@16


Source: main.cpp
#include <windows.h>

#include "bst.h"

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd)
{
	BinarySearchTree<int> *pList = new BinarySearchTree<int>;

	pList->insert(2);
	pList->insert(1);
	pList->insert(3);

	BSTNode<int> **data = pList->search(1);
	int result = (*data)->getData();

	delete pList;

	return(0);
}


bst.cpp
/* Copyright (c) 2008 the authors listed at the following URL, and/or
the authors of referenced articles or incorporated external code:
http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?action=history&offset=20080521005910

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Retrieved from: http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?oldid=13424
*/

#include <algorithm>

#include "bst.h"

template <class T>
BSTNode<T>** BinarySearchTree<T>::search(T data) {
    BSTNode<T>** node = &root;
    while (*node != NULL) {
          if (data < (*node)->data)
            node = &(*node)->left;
        else if ((*node)->data < data)
            node = &(*node)->right;
        else
            break;
    }
    return node;
}

template <class T>
void BinarySearchTree<T>::insert(T data) {
    BSTNode<T>** node = search(data);
    if (*node == NULL) {
        *node = new BSTNode<T>(data);
    }
}

template <class T>
void BinarySearchTree<T>::delete_node(BSTNode<T>** node) {
    BSTNode<T>* old_node = *node;
    if ((*node)->left == NULL) {
        *node = (*node)->right;
        delete old_node;
    } else if ((*node)->right == NULL) {
        *node = (*node)->left;
        delete old_node;
    } else {
        BSTNode<T>** pred = &(*node)->left;
	while ((*pred)->right != NULL) {
	    pred = &(*pred)->right;
	}

	std::swap((*pred)->data, (*node)->data);
	delete(pred);

    }
}


bst.h
/* Copyright (c) 2008 the authors listed at the following URL, and/or
the authors of referenced articles or incorporated external code:
http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?action=history&offset=20080521005910

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Retrieved from: http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?oldid=13424
*/

#ifndef _BST_H_
#define _BST_H_

template <class T>
class BSTNode {
public:
    BSTNode(T data);
    T getData() { return data; }
private:
    T data;
    BSTNode<T>* left;
    BSTNode<T>* right;
};

template <class T>
class BinarySearchTree {
public:
    BSTNode<T>** search(T data);
    void insert(T data);
    void delete_node(BSTNode<T>** node);
private:
    BSTNode<T>* root;
    friend class BSTNode<T>;
};

#endif


Share this post


Link to post
Share on other sites
Well, the linker isn't finding the code because it has never been instantiated. Remember that the code for foobar<T> will only be generated if you actually use it, and either the definition of the template is available in the same translation unit or it has been declared as export. Since in your case the template is neither defined in the same translation unit nor exported, the code isn't generated.

Also bear in mind that the vast majority of compilers does not support template exporting. Therefore, you might want to inline the definition of your template.

Share this post


Link to post
Share on other sites
When defining a template, all the code must be in the header file, including the function definitions. Moving the definitions from bst.cpp to bst.h should solve the problem.

EDIT: More info.

Share this post


Link to post
Share on other sites
EDIT: Disregard that last note..

But I still get the same error if I copy the whole code in the header file


test error LNK2019: unresolved external symbol "public: __thiscall BSTNode<int>::BSTNode<int>(int)" (??0?$BSTNode@H@@QAE@H@Z) referenced in function
"public: void __thiscall BinarySearchTree<int>::insert(int)"
(?insert@?$BinarySearchTree@H@@QAEXH@Z)

bst.h:




/* Copyright (c) 2008 the authors listed at the following URL, and/or
the authors of referenced articles or incorporated external code:
http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?action=history&offset=20080521005910

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Retrieved from: http://en.literateprograms.org/Binary_search_tree_(C_Plus_Plus)?oldid=13424
*/


#ifndef _BST_H_
#define _BST_H_

template <class T>
class BSTNode {
public:
BSTNode(T data);
T getData() { return data; }
public:
T data;
BSTNode<T>* left;
BSTNode<T>* right;
};

template <class T>
class BinarySearchTree {
public:
BSTNode<T>** search(T data);
void insert(T data);
void delete_node(BSTNode<T>** node);
public:
BSTNode<T>* root;
friend class BSTNode<T>;
};

template <class T>
BSTNode<T>** BinarySearchTree<T>::search(T data) {
BSTNode<T>** node = &root;
while (*node != NULL) {
if (data < (*node)->data)
node = &(*node)->left;
else if ((*node)->data < data)
node = &(*node)->right;
else
break;
}
return node;
}

template <class T>
void BinarySearchTree<T>::insert(T data) {
BSTNode<T>** node = search(data);
if (*node == NULL) {
*node = new BSTNode<T>(data);
}
}

template <class T>
void BinarySearchTree<T>::delete_node(BSTNode<T>** node) {
BSTNode<T>* old_node = *node;
if ((*node)->left == NULL) {
*node = (*node)->right;
delete old_node;
} else if ((*node)->right == NULL) {
*node = (*node)->left;
delete old_node;
} else {
BSTNode<T>** pred = &(*node)->left;
while ((*pred)->right != NULL) {
pred = &(*pred)->right;
}

std::swap((*pred)->data, (*node)->data);
delete(pred);

}
}

#endif




Share this post


Link to post
Share on other sites
You need to give BSTNode<T>'s constructor a definition.

But before going any further with this:

Did you write this code? If you downloaded it from somewhere else, I suggest that you stop using it. It is not particularly well written.

Also, if you don't understand how templates work, you will encounter many problems down the road which you probably won't know how to solve.

Finally, why are you using this code? If want to code a binary tree yourself (for practice), I suggest that you do so without using templates first. After you learn more about how templates work, you can convert your code to use them.

If, on the other hand, you just want to use something already made, I would suggest looking at std::map or some other STL container.

Share this post


Link to post
Share on other sites
I didn't write this code. I wanted to learn how to use templates. Since my code failed, I tried to borrow code from somebody else. But you are right, maybe I should just avoid templates for now. Thanks :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this