Linker error: Undefined reference to member function for class with template parameter

[itnovice]

Hi everyone,

I have a small implementation for a doubly linked list. The linked list class takes a template parameter. I'm hitting the following linker error when building my programs:

/tmp/cc1tFbiv.o: In function `main':
main.cpp:(.text+0x42): undefined reference to `DoublyLinkedList<int>::addToDLLTail(int const&)'
collect2: ld returned 1 exit status

Could someone let me know what did I go wrong and how to fix the error? Thanks a lot!



Here's my implementation:

[dList.h]

#ifndef __DOUBLY_LINKED_LIST__
#define __DOUBLY_LINKED_LIST__

#include <iostream>
using namespace std;

template<class T>
class ListNode {
public:
  ListNode() : prev(0), next(0) {}
  ListNode(const T& el, ListNode *p = 0, ListNode *n = 0) : 
          info(el), prev(p), next(n)  {}
  ~ListNode();
  T info; 
  ListNode *prev, *next;
};

template<class T>
class DoublyLinkedList {
public:
  DoublyLinkedList() : head(0), tail(0) , nodeCount(0) {}
  ~DoublyLinkedList(); 

  bool isEmpty() const { return nodeCount == 0; }
  void addToDLLTail (const T&);
  void addToDLLHead (const T&);
  T deleteFromDLLTail();
//  T deleteFromDLLHead();
protected:
  ListNode<T> *head, *tail;
  long nodeCount;
  friend ostream& operator<< (ostream& os, const DoublyLinkedList<T>& dll) {
    for (ListNode<T> *tmp = dll.head; tmp != 0; tmp = tmp->next)
      os << tmp->info << ' ';
    return os; 
  } 
};

#endif

[dList.cpp]

#include "dList.h"

template<class T>
DoublyLinkedList<T>::~DoublyLinkedList() {
  ListNode<T> *tmp;
  while (nodeCount--) {
    tmp = head->next;
    tmp->prev = 0;
    delete head;
    head = tmp;
  }
  head = tail = 0;
}

template<class T>
void DoublyLinkedList<T>::addToDLLTail(const T& el) {
  ListNode<T> *tmp; 
  
  tmp = new ListNode<T>(el, tail, 0);
  if (nodeCount > 0) {
    tail->next = tmp;
    tail = tmp;
  }  
  else { 
    head = tail = tmp; 
    head->prev = 0;
    head->next = 0;
    tail->prev = 0;
    tail->next = 0;
  }
  nodeCount++;
}

template<class T>
void DoublyLinkedList<T>::addToDLLHead(const T& el) {
  ListNode<T> *tmp;
  tmp = new ListNode<T>(el, 0, head);

  if (nodeCount >0) {
    head->prev = tmp;
    head = tmp;
  }
  else {
    head = tail = tmp;
    head->prev = 0;
    head->next = 0;
    tail->prev = 0;
    tail->next = 0;
  }
  nodeCount++;
}

template<class T>
T DoublyLinkedList<T>::deleteFromDLLTail() {
  ListNode<T> *tmp;
  
  T el = tail->info; 
  tmp = tail->prev;
  delete tail;
  if (nodeCount == 1) {
    head = tail = 0;
  }
  else { 
    tmp->next = 0;
    tail = tmp; 
  } 
  nodeCount--;
  return el;
}

[main.cpp]

#include <iostream>
using namespace std;
#include "dList.h"

#define LISTSIZE 100

int main(int argc, char *argv[]) {
  DoublyLinkedList<int> *dll;

  dll = new DoublyLinkedList<int>;

  for (int i = 1; i <= LISTSIZE; i++) 
    dll->addToDLLTail(i);
  cout << &dll; 

  return 0;
}

[compiler]
gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5)

[command]
g++ main.cpp dList.cpp

[helios]

Template function declarations and implementations must appear in the same file.

[melan]

Or add #include "dList.cpp" in main cpp, it may be work.

[johnnystarr]

Why would you need to implement your own doubly linked list? Is this for testing / learning?

[itnovice]

Thanks all. Your solutions fix my issue. I tried helios's suggestion by putting the class template declaration and implementation in the same file. The linker error is resolved. I also tried melan's suggestion by including dList.cpp in the main file. The linker error no longer exists. Thanks for your expert suggestion.

I found the following description on the template on this website:

From the point of view of the compiler, templates are not normal functions or classes. They are compiled on demand, meaning that the code of a template function is not compiled until an instantiation with specific template arguments is required... Because templates are compiled when required, this forces a restriction for multi-file projects: the implementation (definition) of a template class or function must be in the same file as its declaration. That means that we cannot separate the interface in a separate header file, and that we must include both interface and implementation in any file that uses the templates.