Thread: templates and linker errors

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    32

    Post templates and linker errors

    Hi,
    I'm frustrated!
    For two days now I'm trying to compile my own Linked list template to use with any kind of user defined class and I just don't seem to be able to understand why the compiler (dev-c++) keeps saying there's a linker error.
    The linker error refers to calls to methods in the class "List" that occur in the main.cpp file, inside the main() method.
    Please helppppppppp!!!!!!!!!!!!!!!!!!!!!
    (please ignore erros in my actual code, i wasn't able to debug it)

    errors:
    =====
    [Linker error] undefined reference to `List<int>::add(int*)'
    [Linker error] undefined reference to `List<int>::clear()'


    main.cpp:
    =======
    Code:
    #include "linkedlist.h"
    #include <iostream>
    
    using namespace std;
    
    
    int main()
    {
      List<int>* l1 = new List<int>();
    
      int* p = new int;
      *p = 5;
      l1->add(p);
      
      delete l1;
      
      system("PAUSE");
      return 0;
    }
    linkedlist.h:
    =======
    Code:
    #define LINKEDLIST_H
    #include <stdlib.h>
    
    using namespace std;
    
    template <class Type>
    class Node
    {
        private:
        Type* data;
        Node* next;
        
        public:
        Node(Type* d){data = d; next = NULL;};
       ~Node(){free(data);};
        
        void setData(Type* d){data = d;};
        void setNext(Node* n){next = n;};
        
        Type* getData(){return data;};
        Node* getNext(){return next;}; 
    };
    
    template <class Type>
    class List
    {
        private:
        Node<Type>* anchor;
        
        public:
        List(){anchor = NULL;};
       ~List(){this->clear();};
        void clear();
        void add(Type* d);
        Type* get(int i);
        void remove(int i);
        Type* disconnect(int i);
        int size();
    };
    
    void List<class Type> :: clear()
    {
        if(anchor == NULL)
            return;
        
        Node<Type>* p = anchor;
        Node<Type>* q;
        while(p != NULL)
        {
            q = p;
            p = p->getNext();
            delete q;
        }
        anchor = NULL;
    }
    
    void List<class Type> :: add(Type* d)
    {
        Node<Type>* node = new Node<Type>(d);
        node->setNext(anchor);
        anchor = node;
    }
    
    Type* List<class Type> :: get(int i)
    {
        if(anchor == NULL || i < 0)
            return NULL;
            
        Node<Type>* p = anchor;
        int m = 0;
        
        while(p != NULL && m < i)
        {
            p = p->getNext();
            m++;
        }
        
        if(m == i)
        {
            return p->getData();
        }
        else
            return NULL;
    }
    
    void List<class Type> :: remove(int i)
    {
        if(anchor == NULL || i < 0)
            return;
            
        Node<Type>* p;
    
        if(i == 0)
        {
            p = anchor;
            anchor = anchor->getNext();
            delete p;
            return;
        }
        
        Node<Type>* q = anchor;
        p = anchor->getNext();
        int m = 1;
        
        while(p != NULL && m < i)
        {
            q = p;
            p = p->getNext();
            m++;
        }
        
        if(m == i)
        {
            q->setNext(p->getNext());
            delete p;
        }
        else
            return;
    }
    
    Type* List<class Type> :: disconnect(int i)
    {
        if(anchor == NULL || i < 0)
            return NULL;
            
        Node<Type>* p;
        Type* result;
    
        if(i == 0)
        {
            p = anchor;
            anchor = anchor->getNext();
            result =  p->getData();
            p->setData(NULL);
            delete p;
            return result;
        }
        
        Node<Type>* q = anchor;
        p = anchor->getNext();
        int m = 1;
        
        while(p != NULL && m < i)
        {
            q = p;
            p = p->getNext();
            m++;
        }
        
        if(m == i)
        {
            q->setNext(p->getNext());
            result = p->getData();
            p->setData(NULL);
            delete p;
            return result;
        }
        else
            return NULL;
    }
    
    int List<class Type> :: size()
    {
        int i = 0;
        Node<Type>* p = anchor;
        while(p != NULL)
        {
            p = p->getNext();
            i++;
        }
        return i;
    }

  2. #2
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    Your template definitions are messed up. They should be in the form:
    Code:
    template <class Type>
    void List<Type> :: clear()
    {
    //...
    }
    Also, why are you dynamically allocating the instance of your list class? I don't see any reason in the example you have given for not doing:
    Code:
    List<int> l1;
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    32
    JaWiB,
    You have helped me ALOT!!!!
    Thanks man!
    I was thinking of writing new list classes for each type of class I need to link... been there, done that, believe me... but you saved me. You see, I never learned about templates anywhere... I studied alone from books - and yeah, nothing works like practice!
    Thank you.
    And about why I dynamically allocate the list?
    This prog is just a testing/debugging project for a 2D strategy game I'm building... I just needed a generic linked list so that not to do what I just mentioned. In the game I will need to have many, dynamically allocated lists like that... to store for example... waypoints for each unit and the like...

    Thankx

  4. #4
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    Code:
    delete l1;
    Remember to NULL assign a deleted pointer. Helps prevent memory leaks

    Code:
    l1 = NULL
    Double Helix STL

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Remember to NULL assign a deleted pointer. Helps prevent memory leaks
    How? I don't see how that would help at all. If the pointer isn't going out of scope immediately, then assigning 0 to it can prevent deleting an already deleted pointer, but if it is the end of a function or the destructor of a class then it really doesn't matter.

  6. #6
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    You violated the Big Three. Your destructor is correct but you need a copy constructor and assignment operator.

    Consider if I did this:

    Code:
    List<int> list1;
    // Add stuff to list1 here;
    
    if (condition) {
        List<int> list2 = list1;  // By default this shallow copies the pointers
        // Do stuff here
    }
    
    // At this point in the code, list2 is destroyed and it took all of list1's data with it.
    // Using list1 now will be accessing already-deleted data.
    At the bare minimum you can make a private copy constructor/assignment operator which makes the class uncopyable.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  7. #7
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    you do know that you're totally wasting your time, right? implementing your own linked list in C++ is the most pointless exercise in computing. There's a perfectly good implementation in the standard library (std::list)

    I guess there's some justification if you're just doing it as a learning exercise, but you should never use your own linked list in production code.
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  8. #8
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Why not? never is too strong a word to be used in just about any context. The STL is designed for fairly good coverage of a programmer's basic needs. If one writes a Lisp implementation, the lists could be XOR-linked to save space, for example. Or one needs advanced control over the lists (shared tails, reference counting etc.) not provided by the standard library. std::list isn't "perfect"; nothing is.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  9. #9
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by jafet
    Why not? never is too strong a word to be used in just about any context. The STL is designed for fairly good coverage of a programmer's basic needs. If one writes a Lisp implementation, the lists could be XOR-linked to save space, for example. Or one needs advanced control over the lists (shared tails, reference counting etc.) not provided by the standard library. std::list isn't "perfect"; nothing is.
    True, 'never' is probably a bit strong, but I think some common sense can be applied here. When people say "never use macros" or "never derive from a class with a non-virtual destructor", what they really mean is

    don't do this unless you're really REALLY sure about what you're doing and you have no other option. Be prepared for some side-effects and code defensively around them
    but that's a bit long-winded so 'never. is a good substitute.

    Besides, I didn't say 'prefect', I said 'perfectly good', as in 'sufficient for almost all needs'. Even in an extreme corner case such as you're describing, there would have to be a very pressing optimisation case before I'd go to the effort of writing a new list (with all the documentation, testing, debugging and optimisation that entails).
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

  10. #10
    Registered User
    Join Date
    May 2006
    Posts
    30
    Quote Originally Posted by jafet
    Why not? never is too strong a word to be used in just about any context. The STL is designed for fairly good coverage of a programmer's basic needs. If one writes a Lisp implementation, the lists could be XOR-linked to save space, for example. Or one needs advanced control over the lists (shared tails, reference counting etc.) not provided by the standard library. std::list isn't "perfect"; nothing is.
    yes but creating a totally new one? why not just derive from the existing STL class and add your own methods? or you could just build a wrapper class around the STL list class with some extra functionality. its way safer dan defining your own one and the speed wont be that big of a los... it could even be a win if you ask me, never looked into the source of the stl linked list but i know that most classes and functions from the C or C++ runtime library are way faster then when you define your own one unless you really feel like reinventing the weel with some quite nasty hours of work?
    Well, if you do persist on going on with your own class, you might want to look at some optimatisations. for example, the methods of class Node arent that efficient, the call exually takes longer then the function itself, might want to define them inline.

    Good luck anyway

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> why not just derive from the existing STL class and add your own methods?
    If you want to extend a standard library container, publicly deriving from it isn't the way to go. Adding non-member functions that work generically on iterators is better. Or if you must then use composition or private inheritance.

    Although I think if you are in the situation described above where you feel you really do need to roll your own list, re-using the standard one probably won't give the efficiency gains you are looking for.

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    201
    Building your own linked list templates classes is very useful for learning about data structures and templates....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Templates + ref to pointer + linker error.
    By Sparrowhawk in forum C++ Programming
    Replies: 8
    Last Post: 05-18-2009, 04:06 PM
  2. Linker errors with Templates...
    By Petike in forum C++ Programming
    Replies: 2
    Last Post: 09-03-2008, 09:52 AM
  3. Templates from DLL or static library problem
    By mikahell in forum C++ Programming
    Replies: 2
    Last Post: 01-01-2008, 01:49 AM
  4. Linker error with templates
    By anon in forum C++ Programming
    Replies: 7
    Last Post: 09-17-2007, 01:33 PM
  5. Linker Errors with Templates
    By LPP in forum C++ Programming
    Replies: 16
    Last Post: 10-20-2006, 08:45 PM