Thread: Templates + ref to pointer + linker error.

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    98

    Templates + ref to pointer + linker error.

    header/cpp file combined in .h file since using templates:
    Code:
    template <class Entry>
    struct Binary_node
    {
    	Entry data;
    	Binary_node<Entry> *left;
    	Binary_node<Entry> *right;
    	Binary_node(); //constructors
    	Binary_node(const Entry &x);
    };
    
    template <class Entry>
    class Binary_tree
    {
    public:
    	Binary_tree();
    	void insert(const Entry &);
    private:
    	Binary_node<Entry> *root;
    	void recursive_insert (Binary_node<Entry> *&sub_root, const Entry &data);
    };
    
    template <class Entry>
    Binary_node<Entry>::Binary_node()
    {left=right=NULL;}
    
    template <class Entry>
    Binary_tree<Entry>::Binary_tree()
    {
    	this->root=NULL;
    }
    
    template <class Entry>
    void Binary_tree<Entry>::insert(const Entry &data)
    {
    	recursive_insert(root,data);
    }
    
    template <class Entry>
    void Binary_tree<Entry>::recursive_insert(Binary_node<Entry> *&sub_root, const Entry &data)
    {
    	if (sub_root==NULL)
    		sub_root=new Binary_node<Entry>(data);
    	else
    		if (data.key<sub_root->data.key)
    			recursive_insert(sub_root->left,data);
    		else
    			recursive_insert(sub_root->right,data);
    }
    Main:

    Code:
    struct datanode
    {
    	int key;
    	float gpa;
    };
    
    int main ()
    {
    	Binary_tree<datanode> tree;
    	datanode data;
    
    	data.key=89;
    	data.gpa=3.3;
    
    	tree.insert(data);
    }
    Getting this linker error:

    error LNK2019: unresolved external symbol "public: __thiscall Binary_node<struct datanode>::Binary_node<struct datanode>(struct datanode const &)" (??0?$Binary_node@Udatanode@@@@QAE@ABUdatanode@@@Z ) referenced in function "private: void __thiscall Binary_tree<struct datanode>::recursive_insert(struct Binary_node<struct datanode> * &,struct datanode const &)" (?recursive_insert@?$Binary_tree@Udatanode@@@@AAEX AAPAU?$Binary_node@Udatanode@@@@ABUdatanode@@@Z)
    [edit] - Sorry copied the wrong main, corrected... linker error is for the current one.
    Last edited by Sparrowhawk; 05-18-2009 at 02:40 PM.

  2. #2
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    You've never defined
    Code:
        Binary_node(const Entry & x);

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Code:
    struct Binary_node
    {
    	Entry data;
    	Binary_node<Entry> *left;
    	Binary_node<Entry> *right;
    	Binary_node(); //constructors
    	Binary_node(const Entry &x); // Where is the implementation?
    };
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Got it but now I've got another error, here's the implementation:

    Code:
    template <class Entry>
    Binary_node<Entry>::Binary_node(const Entry &x)
    {
    	left=right=x;
    }
    error C2440: '=' : cannot convert from 'const datanode' to 'Binary_node<Entry> *'
    Not sure, but I thought "const Entry &x" passes a reference to x to the Binary_node constructor so I should be able to equate left and right to it... no ?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Sparrowhawk
    Not sure, but I thought "const Entry &x" passes a reference to x to the Binary_node constructor so I should be able to equate left and right to it... no ?
    But left and right are pointers, not Binary_node objects or references. Anyway, it looks like you should initialise those member pointers to be null pointers instead. What you should do with x is to use it to initialise the data member variable.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Quote Originally Posted by laserlight View Post
    But left and right are pointers, not Binary_node objects or references. Anyway, it looks like you should initialise those member pointers to be null pointers instead. What you should do with x is to use it to initialise the data member variable.
    I suppose that makes a lot more sense.

    Question... Is the only difference between preorder and inorder traversal of a BT, that in preorder you want to hit the root first then everything else in order? where inorder is everything is inorder including the root?

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Sparrowhawk View Post
    I suppose that makes a lot more sense.

    Question... Is the only difference between preorder and inorder traversal of a BT, that in preorder you want to hit the root first then everything else in order? where inorder is everything is inorder including the root?
    I'm not sure I'd call that the "only" difference (in the sense of a small difference) but yes.

    In-order:

    process_left();
    process_root();
    process_right();

    Pre-order:

    process_root();
    process_left();
    process_right();

    Post-order:

    process_left();
    process_right();
    process_root();

    Note that in all three cases, left is processed before right, so there are another 3 twins of these sequences with left/right swapped. Those don't have names, as far as I can tell.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    98
    Ok adding onto this... I want to do a fill tree function that takes an input file and reads in keys and gpas from it. But datanode (which defines the struct with keys/gpas) is in my main and this function is a member function of my bintree class.

    How can I do this? and with templates..?


    [edit] - Humm I got it, hope this isn't meant to be polymorphic... heh
    Last edited by Sparrowhawk; 05-18-2009 at 03:41 PM.

  9. #9
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    Sparrowhawk - I saw you mention that you solved your first problem, but didn't see how you resolved it. Could you explain what the issue was? Was it because you needed to either 1) typedef your struct, or 2) declare the tree as:
    Binary_tree<struct datanode> tree;

    Thanks
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Beginner Needs help in Dev-C++
    By Korrupt Lawz in forum C++ Programming
    Replies: 20
    Last Post: 09-28-2010, 01:17 AM
  2. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 03:07 AM
  3. Another syntax error
    By caldeira in forum C Programming
    Replies: 31
    Last Post: 09-05-2008, 01:01 AM
  4. Using VC Toolkit 2003
    By Noobwaker in forum Windows Programming
    Replies: 8
    Last Post: 03-13-2006, 07:33 AM
  5. pointer to array of objects of struct
    By undisputed007 in forum C++ Programming
    Replies: 12
    Last Post: 03-02-2004, 04:49 AM