Problem with templates

navderm (93)
So I wanted to work on Binary trees and binary search trees

the node is defined like this:
1
2
3
4
5
6
 
template<class C> struct BSTNode
{
    C val;
    BSTNode<C>* left;
    BSTNode<C>* right;
};


and a class is defined which has an element of the node like this :
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<class C> class BSTree
{
    private:
        BSTNode<C>* rootPtr;
    protected:
    public:
    //constructors
        BSTree<C>();
    //desctructors
        virtual ~BSTree<C>();
    //other functions
        friend static int lookUp(BSTNode<C>*, C);
};


I want a friend function because i want to use the function as a recursion and using the nodes , not the first pointer that is contained in the class.

But I have trouble declaring and defining this function along with the templates
this is how I am trying to do :

FUNCTION DECLARATION
1
2
 
//function declaration
static int lookUp(BSTNode<C>*, C);


FUNCTION DEFINITION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
static int lookUp(BSTNode<C>* nodePtr, <C> chkVal)
{
    if (nodePtr == NULL)
    {
        //this means the whole tree is empty.
        return 0;
    }
    else
    {
        if (nodePtr.val == chkVal)
            return true;
        else
        {
            if (nodePtr.val < chkVal)
                lookUp(nodePtr.right, chkVal);
            else if (nodePtr.val > chkVal)
                lookUp(nodePtr.left, chkVal);
        }
    }
}


Can someone direct my in right direction to use those templates used for classes in the friend function. the places i have highlighted are particularly confusing.

Thx !
~cheers!
navderm
PanGalactic (1658)
Why don't you make BSTNode a full-fledged class with private data and public left() and right() member functions? That way lookup() doesn't have to be anyone's friend.
guestgulkan (2942)
The friend function needs to be declared as a template function.

You have at least two options here:

1. As the first mention (declaration) of the friend function LookUp is in the
BSTree class then you can do this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
template<class C> struct BSTNode
{
    C val;
    BSTNode<C>* left;
    BSTNode<C>* right;
};


template<class C> class BSTree
{
    private:
        BSTNode<C>* rootPtr;
    protected:
    public:
    //constructors
        BSTree<C>();
    //desctructors
        virtual ~BSTree<C>();
    
    //other functions*******************************
    template <typename T>
        friend  int lookUp(BSTNode<T>*, T);
};


template <typename T>
 int lookUp(BSTNode<T>* nodePtr, T chkVal)
{
    if (nodePtr == NULL)
    {
        //this means the whole tree is empty.
        return 0;
    }
    else
    {
        if (nodePtr.val == chkVal)
            return true;
        else
        {
            if (nodePtr.val < chkVal)
                lookUp(nodePtr.right, chkVal);
            else if (nodePtr.val > chkVal)
                lookUp(nodePtr.left, chkVal);
        }
    }
}


or you can do it like
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
template<class C> struct BSTNode
{
    C val;
    BSTNode<C>* left;
    BSTNode<C>* right;
};

//***********Declaration of  friend function outside
template <typename T>
int lookUp(BSTNode<T>*, T);

template<class C> class BSTree
{
    private:
        BSTNode<C>* rootPtr;
    protected:
    public:
    //constructors
        BSTree<C>();
    //desctructors
        virtual ~BSTree<C>();
    //other functions
    //specify which version of friend function we want
        friend  int lookUp<>(BSTNode<C>*, C);
};


template <typename T>
 int lookUp(BSTNode<T>* nodePtr, T chkVal)
{
    if (nodePtr == NULL)
    {
        //this means the whole tree is empty.
        return 0;
    }
    else
    {
        if (nodePtr.val == chkVal)
            return true;
        else
        {
            if (nodePtr.val < chkVal)
                lookUp(nodePtr.right, chkVal);
            else if (nodePtr.val > chkVal)
                lookUp(nodePtr.left, chkVal);
        }
    }
}
navderm (93)
Also,
for a friend function, is the storage class specifier "static" not allowed ? Why is that ??

~Cheers!
navderm
navderm (93)
@guestgulkan:

what exactly is the difference between writing "typename" and "class" . I see you have used typename for friend function and class for the templates in class definition /

@PanGalactic:

ya i could do that... but this way seems a better learning curve exploitation ;) .
guestgulkan (2942)
I prefer the use of typename - the bit where I used class is just where I copied and pasted your code.
navderm (93)
so are they used interchangeably ? or, more aptly, can they be used interchangeably?

guestgulkan (2942)
Also,
for a friend function, is the storage class specifier "static" not allowed ? Why is that ??


Where you declare the friend function inside the class like this:
1
2
3
4
5
6
7
 
template<class C> class BSTree
{
 
    //other functions*******************************
    template <typename T>
        friend  int lookUp(BSTNode<T>*, T);
};

Then static keyword on the friend function declaration would be illegal because friend functions are not class members .

However it would be legal if the function was declared out side the class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
template <typename T>
static int lookUp(BSTNode<T>*, T); 

template<class C> class BSTree
{
    private:
        BSTNode<C>* rootPtr;
    protected:
    public:
    //constructors
        BSTree<C>();
    //desctructors
        virtual ~BSTree<C>();
    //other functions
        friend  int lookUp<>(BSTNode<C>*, C);
};

Last edited on
navderm (93)
Ok.
these may be coupled with some stupid mistakes I am making but I can't get it to work .

this is my main !
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>
#include "BST.h"

using namespace std;

int main()
{
     BSTree<int> dictTree;
    int exists;
    exists = dictTree.lookMeUpWith(10);
    if (exists == 0)
        cout <<endl<< "The No. entered does not exist";
    else
        cout <<endl<< "The No. entered exists";
    cout << "Hello world!" << endl;
    return 0;
}


THIS IS MY BST.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#ifndef BST_H
#define BST_H

#include <iostream>
using namespace std;

template<class C> struct BSTNode
{
    C val;
    BSTNode<C>* left;
    BSTNode<C>* right;
};

template<class C> class BSTree
{
    private:
        //BSTNode<C> node;
        BSTNode<C>* rootPtr;
    protected:
    //friend function declaration
        template<class T> friend int lookUp(BSTNode<T>*, T);     // the function is defined in the class. hence no extra variable is required
    public:
    //constructors
        BSTree<C>();
    //desctructors
        virtual ~BSTree<C>();
    //other functions
        int lookMeUpWith(C);
};

//all friend functions to the class BSTree
template<class T> int lookUp(BSTNode<T>*, T);

#endif // BST_H


AND THIS IS BST.CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include "BST.h"

template<class C> BSTree<C>::BSTree()
{
    //ctor
}

template<class C> BSTree<C>::~BSTree()
{
    //dtor
}


// other functions
template<class C> int BSTree<C>::lookMeUpWith(C chkVal)
{
    // i had to call it this way as i don't want the main.cpp to deal with the struct and node pointers
    return (lookUp((rootPtr), chkVal));
}


//all friend function definitions to the class BSTree
template<class T> int lookUp(BSTNode<T>* nodePtr, T chkVal)
{
    if (nodePtr == NULL)
    {
        //this means the whole tree is empty.
        return 0;
    }
    else
    {
        if (nodePtr.val == chkVal)
            return true;
        else
        {
            if (nodePtr.val < chkVal)
                lookUp(nodePtr.right, chkVal);
            else if (nodePtr.val > chkVal)
                lookUp(nodePtr.left, chkVal);
        }
    }
}


when i try to run this code the errors given is :

In main.cpp : Line 8 : undefined reference to 'BSTree<int>::BSTree()
In main.cpp : Line 10 : undefined reference to 'BSTree<int>::lookMeUpWith(int)
In main.cpp : Line 16 : undefined reference to 'BSTree<int>::~BSTree()
In main.cpp : Line 16 : undefined reference to 'BSTree<int>::~BSTree()


Why is it not being able to find these functions when they already exist.
Is defining a new object of the class the way i have done in main.cpp wrong ?
or is there some other problem ?


navderm (93)
and ...
if i declare the object like this :
 
 
BSTree<int> dictTree();


I get an error :

In main.cpp : Line 10 : request for member "lookMeUpWith" in dictTree which is of non class type BSTREE<int>()



I dunno where I am going wrong and why ? Kindly plz help .
ne555 (10692)
http://www.cplusplus.com/forum/beginner/33453/#msg180122

If you already have a find method in the class, why the friend function?
Last edited on
navderm (93)
the class has a private variable root. Hence if i want to call the function Lookup , i cannot do that since it cannot point to any other nodes in the tree. hence i need another fn which is not a member of class and which can take in a parameter as the pointer to the nodes so that i can call it recursively.
navderm (93)
@ne555 :
the link you gave worked fine. Its working now !! Wow! didn't know i could have compiler errors coz of templates.
Thanks a lot !!
:)
Topic archived. No new replies allowed.