struct with template object inside an templated class

Question

I am trying to create a Templated class to hold different objects to lern a bit about selfwritten datastructures and ptrs which are new to me. I am stuck at this point:

template <class T> class Linked_List
{

    struct Node
    {
        T data;
        Node* prev;
        Node* next;
        Node(T d, Node* p, Node* n) : data(d),
        prev(p), next(n) {}
    };

public:
    Linked_List();
    ~Linked_List();

    void push_back(T data);
    void push_front(T data);
    void insertAt(T data, int pos);

    T pop_back();
    T pop_front();

    int size();
    bool empty();

private:
    Node* tail;
    Node* head;
};

I get this error: 'Linked_List<T>::Node::data' uses undefined class 'T'. (using VS2013)

What have i done wrong?

Thanks

---

Update:

#include "Linked_List.h"


template<class T> Linked_List<T>::Linked_List()
{
    head = 0;
    tail = 0;
}

template<class T> Linked_List<T>::~Linked_List()
{
    {
        while (head)
        {
            Node* temp(head); //pointer to head
            head = head->next; // go to next
            delete temp; //delete the pointer
        }
    }
}

template <class T>
void Linked_List<T>::push_back(T data)
{
    //create the new Node
    tail = new Node(data, tail, NULL);
    if (tail->prev) //add to tail
        tail->prev->next = tail;
    if (empty()) // if empty its also the head
        head = tail;
}

template <class T>
void Linked_List<T>::push_front(T data)
{
    head = new Node(data, 0, tail);
    if (head->next)
        head->next->prev = head;
    if (empty())
        tail = head;
}

template <class T>
bool Linked_List<T>::empty()
{
    return (!head || !tail);
}

template <class T>
T Linked_List<T>::pop_back()
{
    if (empty())
        throw("Linked_list is empty!");
    //pointer to the element we want to have
    Node* temp(tail);
    //set the tail to prev
    tail = tail->prev;
    //get the data
    T data = temp->data;

    //the prev does not have a next now
    if (tail)
        tail->next = 0;
    else
        head = 0;

    //delete the node which held our data
    delete temp;
    //return the data
    return data;
}

template <class T>
T Linked_List<T>::pop_front()
{
    if (empty())
        throw("Linked_list is empty!");
    //pointer to the element we want to have
    Node* temp(head);
    //set the tail to prev
    head = head->next;
    //get the data
    T data = temp->data;

    //the prev does not have a next now
    if (head)
        head->prev = 0;
    else
        tail = 0;

    //delete the node which held our data
    delete temp;
    //return the data
    return data;
}

new stacktrace if i am trying to use it simply like this

int main(){
    Linked_List<int> list;
    for (int i = 0; i < 20; i++)
    {
        list.push_back(i);
    }

    for (int j = 0; j < 20; j++)
    {
        cout <<  list.pop_back() << endl;
    }
}

Error:

 Error  1   error LNK2019: unresolved external symbol "public: __thiscall Linked_List<int>::Linked_List<int>(void)" (??0?$Linked_List@H@@QAE@XZ) referenced in function _main   C:\Users\...\Documents\Visual Studio 2013\Projects\Double_Linked_List\Double_Linked_List\main.obj   Double_Linked_List
    Error   2   error LNK2019: unresolved external symbol "public: __thiscall Linked_List<int>::~Linked_List<int>(void)" (??1?$Linked_List@H@@QAE@XZ) referenced in function _main  C:\Users\...\Documents\Visual Studio 2013\Projects\Double_Linked_List\Double_Linked_List\main.obj   Double_Linked_List
    Error   3   error LNK2019: unresolved external symbol "public: void __thiscall Linked_List<int>::push_back(int)" (?push_back@?$Linked_List@H@@QAEXH@Z) referenced in function _main C:\Users\...\Documents\Visual Studio 2013\Projects\Double_Linked_List\Double_Linked_List\main.obj   Double_Linked_List
    Error   4   error LNK2019: unresolved external symbol "public: int __thiscall Linked_List<int>::pop_back(void)" (?pop_back@?$Linked_List@H@@QAEHXZ) referenced in function _main    C:\Users\...\Documents\Visual Studio 2013\Projects\Double_Linked_List\Double_Linked_List\main.obj   Double_Linked_List
    Error   5   1   error LNK1120: 4 unresolved externals   C:\Users\...\Documents\Visual Studio 2013\Projects\Double_Linked_List\Debug\Double_Linked_List.exe  1   Double_Linked_List

Answer 1

The linker is very clear : you are missing definition of those methods. The compiler doesn't complain, since it see the declaration of the Linked_List class, but when dealing with templates, that is not enough.

In order for the template instantiation to be successful, all template definitions need to be visible. Since, you implemented methods of the template class in a cpp file (people usually do it in the header, or impl file), you need to include that file where the template is being instantiated. In your specific example, in the main.cpp :

#include <iostream>
#include "Linked_List.cpp"   // !!!


int main(){
    Linked_List<int> list;
    for (int i = 0; i < 20; i++)
    {
        list.push_back(i);
    }

    for (int j = 0; j < 20; j++)
    {
        std::cout <<  list.pop_back() << std::endl;
    }
}

---

Instead of including the implantation file, and have the compiler implicitly instantiate template, you can do it explicitly in the source file. In this case, add this line at the end of Linked_List.cpp :

template class Linked_List<int>;

but in that case, you will not be able to create objects with different template argument (other than int).

---

The third option is a variation of the first. Include the source file at the end of the header.

Header

// header.hpp
#ifndef HEADER_HPP
#define HEADER_HPP

template< typename T >
struct A
{
    void foo();
};

#include "source.impl"

#endif

Source

// source.impl

#include "header.hpp"

template< typename T >
void A::foo()
{
}

Main

// main.cpp

#include "header.hpp"

int main()
{
  A<int> a;
  a.foo();
}

Answer 2

I am guessing you've put the definition of the template class and implementation of its methods in two files, just like what you do for normal non-template classes; and you just include the header file which defines your linked list in your main.cpp.

Please refer to this thread for why you cannot do this

Why can templates only be implemented in the header file?