compilation error: undefined reference (g++ on Linux)

From:

"rkalyankumar77@gmail.com" <rkalyankumar77@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Sun, 10 Feb 2008 06:41:12 -0800 (PST)

Message-ID:

<6b032306-6508-4aaa-829e-448166153c98@d21g2000prf.googlegroups.com>

Hi,

I am getting undefined reference error for the code below:

list.h:
-------------
#ifndef _LIST_H
#define _LIST_H

template <class T>
struct ListNode
{
    T data;
    ListNode<T> *prev,*next;

    ListNode(T d=0):data(d)
    {
        prev = 0;
        next = 0;
    }

    ~ListNode()
    {
    }
};

template <class T>
class List
{
private:
    ListNode<T> *head, *tail;
    unsigned int size;
public:
    List();
    ~List();
    bool insert_head(ListNode<T>* node);
    bool insert_tail(ListNode<T>* node);
    bool insert_next(ListNode<T>* node,ListNode<T>* next);
    bool insert_prev(ListNode<T>* node,ListNode<T>* prev);
    bool remove_head(ListNode<T>* &node);
    bool remove_tail(ListNode<T>* &node);
    bool remove_next(ListNode<T>* next,ListNode<T>* &node);
    bool remove_prev(ListNode<T>* prev,ListNode<T>* &node);
    bool find_node(const T& data,ListNode<T>* &node);
    bool destroy_list();
    inline ListNode<T>* get_head() { return this->head; }
    inline ListNode<T>* get_tail() { return this->tail; }
    void print();
};
#endif

list.cc
-----------
#include "list.h"
#include <iostream>
using std::cout;
using std::endl;

template <class T>
List<T>::List()
{
    this->head = new ListNode<T>();
    this->head->data = 0;
    this->tail = new ListNode<T>();
    this->tail->data = 0;
    this->head->prev = this->tail;
    this->tail->next = this->head;
    this->head->next = 0;
    this->tail->prev = 0;
    this->size = 0;
}

template <class T>
List<T>::~List()
{
    this->destroy_list();
}

template <class T>
bool
List<T>::insert_head(ListNode<T>* node)
{
    if(node == 0 || node == NULL)
        return false;
    if(size == 0) {
        this->head->next = node;
        this->tail->prev = node;
        node->next = this->tail;
        node->prev = this->head;
    } else {
        node->next = this->head->next;
        node->prev = this->head;
        this->head->next->prev = node;
        this->head->next = node;
    }
    ++this->size;
    return true;
}

template <class T>
bool
List<T>::insert_tail(ListNode<T>* node)
{
    if(node == 0 || node == NULL)
        return false;
    if(size == 0) {
        this->head->next = node;
        this->tail->prev = node;
        node->next = this->tail;
        node->prev = this->head;
    } else {
        node->prev = this->tail->prev;
        node->next = this->tail;
        this->tail->prev->next = node;
        this->tail->prev = node;
    }
    ++this->size;
    return true;
}

template <class T>
bool
List<T>::insert_next(ListNode<T>* node,ListNode<T>* next)
{
    if(node == 0 || node == NULL)
        return false;
    if(next == 0 || next == NULL
        && this->size == 0) {
        return this->insert_head(node);
    }

    if(next == 0 || next == NULL) {
        return this->insert_head(node);
    } else if(next == this->tail) {
        return this->insert_tail(node);
    } else if(next == this->head) {
        return this->insert_head(node);
    } else {
        node->next = next->next;
        node->prev = next;
        if(next->next == this->tail) {
            this->tail->prev = node;
        } else {
            next->next->prev = node;
        }
        next->next = node;
    }
    ++this->size;
    return true;
}

template <class T>
bool
List<T>::insert_prev(ListNode<T>* node,ListNode<T>* prev)
{
    if(node == 0 || node == NULL)
        return false;
    if(prev == 0 || prev == NULL
        && this->size == 0) {
        return this->insert_tail(node);
    }

    if(prev == 0 || prev == NULL) {
        return this->insert_tail(node);
    } else if(prev == this->tail) {
        return this->insert_tail(node);
    } else if(prev == this->head) {
        return this->insert_head(node);
    } else {
        node->prev = prev->prev;
        node->next = prev;
        if(prev->prev == this->head) {
            this->head->next = node;
        } else {
            prev->prev->next = node;
        }
        prev->prev = node;
    }
    ++this->size;
    return true;
}

template<class T>
bool
List<T>::remove_head(ListNode<T>* &node)
{
    bool result = false;
    if(this->size == 0) return true;
    node = this->head->next;
    this->head->next = node->next;
    node->next->prev = this->head;
    --this->size;
    result = true;
    return result;
}

template<class T>
bool
List<T>::remove_tail(ListNode<T>* &node)
{
    bool result = false;
    if(this->size == 0) return true;
    node = this->tail->prev;
    this->tail->prev = node->prev;
    node->prev->next = this->tail;
    --this->size;
    result = true;
    return result;
}

template <class T>
bool
List<T>::remove_next(ListNode<T>* next,ListNode<T>* &node)
{
    bool result = false;
    if(next == 0 || next == NULL
        && this->size == 0) return true;
    if(next == 0 || next == NULL) {
        return remove_head(node);
    } else if(next == this->head) {
        return remove_head(node);
    } else if(next == this->tail) {
        return remove_tail(node);
    } else {
        node = next->next;
        next->next = node->next;
        node->next->prev = next;
    }
    --this->size;
    result = true;
    return result;
}

template <class T>
bool
List<T>::remove_prev(ListNode<T>* prev,ListNode<T>* &node)
{
    bool result = false;
    if(prev == 0 || prev == NULL
        && this->size == 0) return true;
    if(prev == 0 || prev == NULL) {
        return remove_tail(node);
    } else if(prev == this->head) {
        return remove_head(node);
    } else if(prev == this->tail) {
        return remove_tail(node);
    } else {
        node = prev->prev;
        prev->prev = node->prev;
        node->prev->next = prev;
    }
    --this->size;
    result = true;
    return result;
}

template <class T>
bool
List<T>::find_node(const T& data,ListNode<T>* &node)
{
    if(data == 0) {
        node = 0;
        return false;
    }
    node = this->head->next;
    while(node->next != this->head) {
        if(node->data == data) return true;
        node = node->next;
    }
    return false;
}

template <class T>
bool
List<T>::destroy_list()
{
    ListNode<T> *node;
    if(this->size == 0) {
        delete this->head;
        delete this->tail;
        return true;
    }
    node = this->head->next;
    while(node->next != this->head) {
        this->remove_head(node);
        delete node;
        node = this->head->next;
    }
    delete this->head;
    delete this->tail;
    return true;
}

template <class T>
void
List<T>::print()
{
    cout << "List size: " << this->size << endl;
    ListNode<T> *node = this->head->next;
    while(node->next !=this->head) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

stack.h
------------
#ifndef _STACK_H_
#define _STACK_H_

#include "list.h"

template <class T>
class Stack {
private:
    List<T> *stackImpl;
public:
    Stack() {
        stackImpl = new List<T>();
    }
    ~Stack(){
        stackImpl->destroy_list();
        delete stackImpl;
    }
    void push(const T& data);
    const T& top();
    T pop();
};

#endif

stack.cc
-------------
#include "stack.h"

template <class T>
void
Stack<T>::push(const T &data) {
    stackImpl->insert_head(new ListNode<T>(data));
}

template <class T>
const T&
Stack<T>::top() {
    ListNode<T> *top_node;
    stackImpl->remove_head(top_node);
    T data = top_node->data;
    delete top_node;
    return data;
}

template <class T>
T
Stack<T>::pop() {
    ListNode<T> *top_node = stackImpl->get_head()->next;
    return top_node->data;
}

And finally driver program main.cc below:

#include <iostream>
using std::cout;
using std::endl;
#include "stack.h"

int main(void)
{
    Stack<int> stk;
    int i;
    for(i = 0; i < 10; i++) {
        stk.push((i+1));
    }
    for(i = 0; i < 10; i++) {
        cout << stk.top() << endl;
    }
    return 0;
}

And I compiled in two different ways:

First way:

g++ -c -o list.o list.cc
g++ -c -o stack.o stack.cc
g++ -o main main.cc list.o stack.o

Second way:

g++ -o main list.cc stack.cc main.cc

both ways I'm getting following compilation output (error):

/tmp/cctl19MO.o: In function `main':
main.cc:(.text+0xaf): undefined reference to `Stack<int>::push(int
const&)'
main.cc:(.text+0xcd): undefined reference to `Stack<int>::top()'
/tmp/cctl19MO.o: In function `Stack<int>::Stack()':
main.cc:(.text._ZN5StackIiEC1Ev[Stack<int>::Stack()]+0x1d): undefined
reference to `List<int>::List()'
/tmp/cctl19MO.o: In function `Stack<int>::~Stack()':
main.cc:(.text._ZN5StackIiED1Ev[Stack<int>::~Stack()]+0xf): undefined
reference to `List<int>::destroy_list()'
main.cc:(.text._ZN5StackIiED1Ev[Stack<int>::~Stack()]+0x28): undefined
reference to `List<int>::~List()'
collect2: ld returned 1 exit status

Can't understand the cause of the error above. Kindly help. Compiler
version that i use:

g++ (GCC) 4.1.2 20070115 (prerelease) (SUSE Linux)
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There
is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE.

Many thanks.

Kalyan