c++ linking error for template, using only header files, why?

Question

I know there are a lot of similar questions out there - believe me, I've read them - but I can't get this to work. Which is peculiar, because I resolved a similar struggle with a related program just the other day. I realize that the answer to my question quite likely is out there somewhere, but I've spent a good hour or two looking, without much success.

I am trying to build a linked list. The program consists of four files - header files for the linked list and the node, as well as an interace to the list, and the .cpp file containing the main method.

ListTester.cpp

#include "StdAfx.h"
#include "LinkedList.h"
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void main() {

    LinkedList<int> a;
    a.addFirst(22);
    a.addFirst(24);
    a.addFirst(28);
    LinkedList<int> b;
    b = a;
    b = b + a;
    b += a;

    cout<<b;
}

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include "List.h"
#include <ostream>

template <typename T>

class LinkedList : public List {

private:

    int n;
    Node<T> *first;
    Node<T> *last;

public:

    LinkedList();
    LinkedList(const LinkedList & ll);
    ~LinkedList();
    int size();
    void clear();
    void addFirst(T data);
    void addLast(T data);
    T removeFirst();
    T removeLast(); 
    T getFirst();
    T getLast();
    Node<T>* getFirstNode() const;
    void addAt(int pos, T data);
    T removeAt(int pos);
    T getAt(int pos);   
    LinkedList& operator=(const LinkedList<T> &right);
    T operator[](int i);
    LinkedList& operator+(const LinkedList<T> &right);
    LinkedList& operator+=(const LinkedList<T> &right);
    friend std::ostream& operator<<(std::ostream &os, const LinkedList<T> & ll);

};

template <typename T>
LinkedList<T>::LinkedList() {
        this->n = 0;
        this->first = 0;
        this->last = 0;
    }

template <typename T>
LinkedList<T>::LinkedList(const LinkedList & ll) {
    this-> n = 0;
    this-> first = 0;
    this-> last = 0;

    Node *temp = ll.first;

    while(temp) {
        addLast(temp->getData());
        temp = temp->getNext();
    }

}

template <typename T>
void LinkedList<T>::addFirst(T data) {
    Node *p = new Node(data, first);
    first = p;
    if(!n)
        last = p;
    n++;
}

template <typename T>
void LinkedList<T>::addLast(T data) {
    Node *p = new Node(data, 0);
    if(!n)
        first = last = p;
    else {
        last->next = p;
        last = p;
    }
    n++;
}

template <typename T>
T LinkedList<T>::removeFirst() {
    T a = 0;
    if(!n)
        throw "Can't retrieve element from empty list!";
    a = first->getData();
    Node *p = first->next;
    delete first;
    first = p;
    n--;
    return a;
}

template <typename T>
T LinkedList<T>::removeLast() {
    T a = 0;
    if(!n)
        throw "Can't retrieve element from empty list!";
    if(n == 1) {
        a = last->getData();
        delete first;
        first = last = 0;
    }
    else {
        a = last->getData();
        Node *p = first;
        while(p->next->next != 0)
            p = p->next;
        delete p->next;
        p->next = 0;
        last = p;
    }
    n--;
    return a;
}

template <typename T>
T LinkedList<T>::getFirst() {
    if(n < 1)
        throw "Can't retrieve element from empty list!";
    return first->getData();
}

template <typename T>
T LinkedList<T>::getLast() {
    if(n < 1)
        throw "Can't retrieve element from empty list!";
    return last->getData();
}

template <typename T>
Node<T>* LinkedList<T>::getFirstNode() const {
    return first;
}

template <typename T>
int LinkedList<T>::size() {
    return n;
}

template <typename T>
T LinkedList<T>::getAt(int pos) {
    if(pos >= n)
        throw "Element index out of bounds!";       
    Node *temp = first;
    while(pos > 0) {
        temp = temp->next;
        pos--;
    }
    return temp->getData();     
}

template <typename T>
void LinkedList<T>::clear() {
    Node *current = first;
    while(current) {
        Node *next = current->next;
        delete current;
        if(next)
            current = next;
        else
            current = 0;
    }
}

template <typename T>
void LinkedList<T>::addAt(int pos, T data) {
    if(pos >= n)
        throw "Element index out of bounds!";       
    if(pos == 0)
        addFirst(data);
    else {
        Node *temp = first;
        while(pos > 1) {
            temp = temp->next;
            pos--;
        }
        Node *p = new Node(data, temp->next);
        temp-> next = p;
        n++;
    }
}

template <typename T>
T LinkedList<T>::removeAt(int pos) {
    if(pos >= n)
        throw "Element index out of bounds!";       
    if(pos == 0)
        return removeFirst();
    if(pos == n - 1)
        return removeLast();
    else {
        Node *p = first;
        while(pos > 1) {
            p = p->next;
            pos--;
        }
        T a = p->next->getData();
        Node *temp = p->next;
        p->next = p->next->next;
        delete temp;
        n--;
        return a;
    }       
}

template <typename T>
LinkedList<T>::~LinkedList() {
    clear();
}

template <typename T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T> &right) {
    if(this != &right) {

        n = 0;
        first = 0;
        last = 0;

        Node *temp = right.first;
        while(temp) {
            addLast(temp->getData());
            temp = temp->getNext();
        }           
    }
    return *this;
}

template <typename T>
T LinkedList<T>::operator[](int i) {
    return getAt(i);
}

template <typename T>
LinkedList<T>& LinkedList<T>::operator+(const LinkedList<T> &right) {
    Node *temp = right.first;
    while(temp) {
        addLast(temp->getData());
        temp = temp->getNext();
    }
    return *this;
}

template <typename T>
LinkedList<T>& LinkedList<T>::operator+=(const LinkedList<T> &right) {
    Node *temp = right.first;
    while(temp) {
        addLast(temp->getData());
        temp = temp->getNext();
    }
    return *this;
}

template <typename T>
std::ostream& operator<<(std::ostream &os, const LinkedList<T> &ll) {
    Node *temp = ll.getFirstNode();
    while(temp) {
        os<<temp->getData()<<std::endl;
        temp = temp->getNext();
    }
    return os;
}

#endif

Node.h

#ifndef NODE_H
#define NODE_H

template <typename T>
class Node {

private:

    T data;

public:

    Node<T>* next;
    T getData();
    Node<T>* getNext();
    Node(T data, Node<T>* next);
    Node(const Node & n);

};

template <typename T>
T Node<T>::getData() {
        return data;
    }

template <typename T>
Node<T>* Node<T>::getNext() {
    return next;
}

template <typename T>
Node<T>::Node(T data, Node<T>* next) {
    this->data = data;
    this->next = next;
    }

template <typename T>
Node<T>::Node(const Node & n) {
    data = n.data;
    next = n.next;
}   

#endif

List.h

#ifndef LIST_H
#define LIST_H

class List
  {

public:

    virtual void addFirst(int data) = 0;
    virtual void addAt(int pos, int data) = 0;
    virtual void addLast(int data) = 0;
    virtual int getFirst()= 0;
    virtual int getAt(int pos) = 0;
    virtual int getLast()= 0;
    virtual int removeFirst()= 0;
    virtual int removeAt(int pos) = 0;
    virtual int removeLast()= 0;
    virtual int size() = 0;
    virtual void clear() = 0;
    virtual ~List() {};     

  };

#endif

For this, I get LNK2019 and LNK1120 linking errors. I know I used to get this when implementing a Queue in separated .h and .cpp files. But worked around it by doing everything in the header. I also know that this can happen when not implementing a named method, but I can't find any of those here. So what's causing this? I wish the compiler / IDE could point me to the possible cause of the error. But then again, if it was an easy task to find the faulty line, I assume it would already do this. VS 2012 btw.

Presumably, the linker tells you which symbols are unresolved. That should point you (or us, if you tell us what they are) to the cause of the error. — Mike Seymour, Mar 27 '13 at 13:08
The *real* errors, not just LNK2019 and LNK1120, which also mean nothing to linux user. — Bartek Banachewicz, Mar 27 '13 at 13:08
duplicate of [this](http://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file) — bash.d, Mar 27 '13 at 13:09
@BartekBanachewicz: According to Google (available even to Linux users), "unresolved external symbol" and "unresolved externals". But we still need the full error messages to know what those symbols are. — Mike Seymour, Mar 27 '13 at 13:09
Error 1 error LNK2019: unresolved external symbol _main referenced in function ___tmainCRTStartup C:\Users\Funky MF\cpp\LinkedList\LinkedList\MSVCRTD.lib(crtexe.obj) LinkedList Error 2 error LNK1120: 1 unresolved externals C:\Users\Funky MF\cpp\LinkedList\Debug\LinkedList.exe 1 1 LinkedList — Christofer Ohlsson, Mar 27 '13 at 13:11
Oh god, I just realized I have BUNCHES of mentions to Node in the LinkedList.h that aren't templatized. — Christofer Ohlsson, Mar 27 '13 at 13:15

bstamour · Answer 1 · 2013-03-27T13:21:39.040

2

// template <typename T>
void main() {

    LinkedList<int> a;
    a.addFirst(22);
    a.addFirst(24);
    a.addFirst(28);
    LinkedList<int> b;
    b = a;
    b = b + a;
    b += a;

    cout<<b;
}

You need a main function, not a main function template. That's probably the source of your linker error: no function called "main".

The reason this won't work is primarily because class templates and function templates are never expanded to real code unless they're used. Since main is the entrypoint to your program, you never call main from anywhere and thus no code for main is ever generated.

Furthermore due to the name mangling that C++ compilers do to functions (to handle overloading, templates, namespaces etc) the symbol that will be generated in the resulting assembly for this main template probably won't be the right one. If it's looking for a symbol 'main' and it sees

$__T_float_main_blah_blah_blah

then you won't link anyways. Long story short: main is a function, not a function template.

edited Mar 27 '13 at 13:21

answered Mar 27 '13 at 13:14

bstamour

7,746
1
26
39

Thank you. I must admit I do not fully understand the c++ template syntax yet, even if I understand what a template IS. I have commented the line you suggested, as well as fixing a huge bunch of references to Node in the LinkedList.h file that were without the suffix. And now I get this: – Christofer Ohlsson Mar 27 '13 at 13:20
Error 1 error LNK2019: unresolved external symbol "class std::basic_ostream > & __cdecl operator<<(class std::basic_ostream > &,class LinkedList const &)" (??6@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@std@@AAV01@ABV?$LinkedList@H@@@Z) referenced in function _main C:\Users\Funky MF\cpp\LinkedList\LinkedList\ListTester.obj LinkedList Error 2 error LNK1120: 1 unresolved externals C:\Users\Funky MF\cpp\LinkedList\Debug\LinkedList.exe 1 1 LinkedList – Christofer Ohlsson Mar 27 '13 at 13:20
That probably means you don't have an overload of operator << for your linked list type. – bstamour Mar 27 '13 at 13:22
Well I do, and it was working before I "templatized" the program. But you're right, when I uncomment it (and rather just cout one fetched element, everythin works. So there's something wrong with that overload) Thanks! – Christofer Ohlsson Mar 27 '13 at 13:24
No problem. You'll get used to templates with time and practice. – bstamour Mar 27 '13 at 13:25
Do you have any idea what could be wrong with my << overload? The only think I've changed since the list was designed to use ints specifically, is to add parametrization to the LinkedList argument, as well as the temporary node created within the method. – Christofer Ohlsson Mar 27 '13 at 13:30
Is Node* temp supposed to be Node* temp? The code you shared above doesn't have the . – bstamour Mar 27 '13 at 13:55
Yes, I changed all such instances after posting the question. Sorry for not being clearer on that. This is my current << method: template std::ostream& operator<<(std::ostream &os, const LinkedList &ll) { Node *temp = ll.getFirstNode(); while(temp) { os<getData()<getNext(); } return os; } OOPS, that's not very legible. – Christofer Ohlsson Mar 27 '13 at 14:09
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/27019/discussion-between-bstamour-and-christofer-olsson) – bstamour Mar 27 '13 at 14:38

score 2 · Answer 2 · answered Mar 27 '13 at 13:14

You made main a function template. Not only does this not make sense (there is no mention of the template parameter inside), it's also never instantiated (and even if it was, it probably wouldn't resolve to the correct main that a program needs as a start point).

Furthermore, it should be int main rather than void main.

c++ linking error for template, using only header files, why?

2 Answers2