What is this error? (And why doesn't it occur in other classes?)

Question

Hi there,

I'm trying to write a some container classes for implementing primary data structures in C++. The header file is here:

#ifndef LINKEDLIST1_H_
#define LINKEDLIST1_H_

#include <iostream>
using namespace std;

template<class T> class LinkedList1;
template<class T> class Node;

template<class T>
class Node
{
    friend class LinkedList1<T> ;
public:
    Node<T> (const T& value)
    {
        this->Data = value;
        this->Next = NULL;
    }
    Node<T> ()
    {
        this->Data = NULL;
        this->Next = NULL;
    }
    T Data;
    Node* Next;
};

template<class T>
class LinkedList1
{
    friend class Node<T> ;
public:
    LinkedList1();
//    LinkedList1<T>();
    ~LinkedList1();
    // Operations on LinkedList
    Node<T>* First();

    int Size();
    int Count();
    bool IsEmpty();
    void Prepend(Node<T>* value); //O(1)
    void Append(Node<T>* value);
    void Append(const T& value);
    void Insert(Node<T>* location, Node<T>* value); //O(n)
    Node<T>* Pop();
    Node<T>* PopF();
    Node<T>* Remove(const Node<T>* location);
    void Inverse();
    void OInsert(Node<T>* value);
    // TODO Ordered insertion. implement this: foreach i,j in this; if i=vale: i+=vale, break; else if i<=value<=j: this.insert(j,value),break
    void print();
private:
    Node<T>* first;
    int size;
};

#endif /* LINKEDLIST1_H_ */

When I try to use it in another class, for example like this:

void IDS::craete_list()
{
    LinkedList1<int> lst1 = LinkedList1<int>::LinkedList1<int>();
}

this error occurs:

undefined reference to 'LinkedList1<int>::LinkedList1<int>()'

The constructor of the class is public and its header file is included. I also tried to include the .cpp file of the class, but that didn't help. I wrote other classes such SparseMatrix and DynamicArray in exactly the same way and there was no error!...

Answer 1

See FAQ item 35.12 "Why can't I separate the definition of my templates class from its declaration and put it inside a .cpp file?".

Most probably that's what you're running into.

Cheers & hth.,

Answer 2

To create the object, do like this :

void IDS::craete_list()
{
    LinkedList1<int> lst1;
}

As for linker problems, if you define your template class in the source (cpp) file, you need to include it, instead of the header file.

Answer 3

there are many remarks that can (should) be made on your code. I also assume that there is no reason to manually implement linked list instead of using STL other than homework, so an appropriate tag would be nice.

• it is not recommended to use using namespace in include files
• there is no reason for the forward declaration of the class Node as it immediately follows
• there is no need to use Node<T> inside the class, the regular Node is enough
• you don't need to use this-> for data members
• it is better & shorter to use constructor initialization list
• bug: using this->Data = NULL; you implicitly require that T is a pointer. Just let Data be default constructed
• why Node declares LinkedList1 as friend, I don't see any use of it in the code you provide?

Your code may look like this:

#ifndef LINKEDLIST1_H_
#define LINKEDLIST1_H_

template<class T> class LinkedList1;

template<class T>
class Node
{
    friend class LinkedList1<T> ;
public:
    Node (const T& value): Data(value), Next(NULL) {}
    Node (): Next(NULL) {}
    T Data;
    Node* Next;
};