C++ Template Linked List Linker Error

Question

I think I'm improperly using my template but I can't figure out what I'm doing wrong. It's like the template linked list can't figure out that it needs to use my Term class.

theList->insert(tempPolynomial); is the line of code, located at the end of function.cpp, that causes the linker error!

Here are the exact errors from Visual Studio 2012:

error LNK2019: unresolved external symbol "bool __cdecl operator<(class Term,class LinkedList)" (??M@YA_NVTerm@@V?$LinkedList@VTerm@@@@@Z) referenced in function "public: void __thiscall LinkedList::insert(class Term)" (?insert@?$LinkedList@VTerm@@@@QAEXVTerm@@@Z) C:\Users\Michael\Documents\Magic Briefcase\champlain\courseWork\dataStructures\pa2\pa2\functions.obj
error LNK1120: 1 unresolved externals C:\Users\Michael\Documents\Magic Briefcase\champlain\courseWork\dataStructures\pa2\Debug\pa2.exe

header.h

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

#include "linkedList.h"
#include "term.h"

void loadPolynomial(string expression, LinkedList<Term> *theList);

functions.cpp

#include "header.h"


void loadPolynomial(string expression, LinkedList<Term> *theList)
{
    Term tempPolynomial;

    string varDelimiter = "x";
    string posDelimiter = "+";
    string negDelimiter = "-";
    string token = "";

    double coefficient;
    double exponent;

    bool isNeg;

    while(expression.length() > 0)
    {
        isNeg = false;

        if(expression.substr(0, 1) == "+")
        {
            expression.erase(0, 1);
        }

        else if(expression.substr(0, 1) == "-")
        {
            isNeg = true;
            expression.erase(0, 1);
        }

        //Get the coefficient
        token = expression.substr(0, expression.find(varDelimiter));
        //Remove the coefficient and variable from the string leaving only the exponent
        expression.erase(0, expression.find(varDelimiter) + varDelimiter.length());
        //Convert and put token's coeficient into a double
        coefficient = atof(token.c_str());

        if(isNeg = true)
        {
            coefficient = coefficient * -1;
        }

        //Put the coefficient value into the tempPolynomial
        tempPolynomial.setCoefficient(coefficient);

        //If posDelimiter has a smaller length then it is the beginning of the next expression
        if(expression.find(posDelimiter) < expression.find(negDelimiter))
        {
            //Get the exponent
            token = expression.substr(0, expression.find(posDelimiter));
            //Remove the exponent but leave the + 
            expression.erase(0, expression.find(varDelimiter));
            //Convert and put token's coeficient into a double
            exponent = atof(token.c_str());
        }

        else
        {
            //Get the exponent
            token = expression.substr(0, expression.find(posDelimiter));
            //Remove the exponent but leave the +
            expression.erase(0, expression.find(varDelimiter));
            //Convert and put token's coeficient into a double
            exponent = atof(token.c_str());
        }

        //Put the exponent value into the tempPolynomial
        tempPolynomial.setExponent(exponent);

        //Intert the first term into the linked list
        theList->insert(tempPolynomial);
    }
}

linkedList.h

#ifndef LINKED_LIST_H
#define LINKED_LIST_H

#include <iostream>
#include <fstream>
using namespace std;

template <class T>
class LinkedList
{
private:
    T mData;
    LinkedList<T> *mNext;

public:
    LinkedList();
    LinkedList(T data);
    ~LinkedList();

    T getData();
    LinkedList<T> *getNext();

    void setData(T data);

    void display();
    void insert(T data);
    bool isExist(T data);
    void remove(T data);

    friend ostream& operator<<(ostream &output, LinkedList<T> obj);

    bool operator==(T right);
    friend bool operator==(T left, LinkedList<T> right);

    bool operator!=(T right);
    friend bool operator!=(T left, LinkedList<T> right);

    bool operator>(T right);
    friend bool operator>(T left, LinkedList<T> right);

    bool operator<(T right);
    friend bool operator<(T left, LinkedList<T> right);
};



template <class T>
LinkedList<T>::LinkedList()
{
    mNext = NULL;
    mData = T();
}



template <class T>
LinkedList<T>::LinkedList(T data)
{
    mNext = NULL;
    mData = data;
}



template <class T>
LinkedList<T>::~LinkedList()
{
    LinkedList<T> *tempNode;

    tempNode = mNext;

    while(tempNode != NULL)
    {
        mNext = tempNode->mNext;
        tempNode->mNext = NULL;

        delete tempNode;

        tempNode = mNext;
    }
}



template <class T>
T LinkedList<T>::getData()
{
    return mData;
}



template <class T>
LinkedList<T> *LinkedList<T>::getNext()
{
    return mNext;
}



template <class T>
void LinkedList<T>::setData(T data)
{
    mData = data;
}



template <class T>
void LinkedList<T>::display()
{
    LinkedList<T> *tempNode;

    tempNode = mNext;

    while(tempNode != NULL)
    {
        cout << tempNode->mData << endl;

        tempNode = tempNode->mNext;
    }
}



template <class T>
void LinkedList<T>::insert(T data)
{
    LinkedList<T> *previousNode;
    LinkedList<T> *tempNode;
    LinkedList<T> *newNode;

    newNode = new LinkedList(data);

    if(mNext == NULL)
    {
        mNext = newNode;
    }

    else
    {
        previousNode = mNext;
        tempNode = mNext;

        while(tempNode != NULL && tempNode->mData < data)
        {
            previousNode = tempNode;
            tempNode = tempNode->mNext;
        }

        if(tempNode == mNext)
        {
            newNode->mNext = mNext;
            mNext = newNode;
        }

        else
        {
            previousNode->mNext = newNode;
            newNode->mNext = tempNode;
        }
    }
}



template <class T>
bool LinkedList<T>::isExist(T data)
{
    LinkedList<T> *tempNode;
    bool exist = false;

    tempNode = mNext;

    while(tempNode != NULL)
    {
        if(tempNode->mData == data)
        {
            exist = true;

            break;
        }

        tempNode = tempNode->mNext;
    }

    return exist;
}



template <class T>
void LinkedList<T>::remove(T data)
{
    LinkedList<T> *tempNode;
    LinkedList<T> *previousNode;

    if(isExist(data) == false)
    {
        return;
    }

    tempNode = mNext;
    previousNode = mNext;

    while(tempNode->mData != data)
    {
        previousNode = tempNode;
        tempNode = tempNode->mNext;
    }

    if(tempNode == mNext)
    {
        mNext = tempNode->mNext;
        tempNode->mNext = NULL;
    }

    else
    {
        if(tempNode->mNext == NULL)
        {
            previousNode->mNext = NULL;
        }

        else
        {
            previousNode->mNext = tempNode->mNext;
            tempNode->mNext = NULL;
        }
    }

    delete tempNode;
}



template <class T>
ostream& operator<<(ostream &output, LinkedList<T> obj)
{
    output << obj.mData;

    return output;
}



template <class T>
bool LinkedList<T>::operator==(T right)
{
    return mData == right;
}



template <class T>
bool operator==(T left, LinkedList<T> right)
{
    return left == right.mData;
}



template <class T>
bool LinkedList<T>::operator!=(T right)
{
    return mData != right;
}



template <class T>
bool operator!=(T left, LinkedList<T> right)
{
    return left != right.mData;
}



template <class T>
bool LinkedList<T>::operator>(T right)
{
    return mData > right;
}



template <class T>
bool operator>(T left, LinkedList<T> right)
{
    return left > right.mData;
}



template <class T>
bool LinkedList<T>::operator<(T right)
{
    return mData < right;
}



template <class T>
bool operator<(T left, LinkedList<T> right)
{
    return left < right.mData;
}

#endif

term.h

#ifndef TERM_H
#define TERM_H

class Term
{
private:
    double mCoefficient;
    double mExponent; 

public:
    Term();
    Term(double coefficient, double exponent);
    ~Term();

    double getCoefficient();
    double getExponent();
    void setCoefficient(double coefficient);
    void setExponent(double exponent);
};

#endif

You declare your friended operators but you don't define them anyway. So... define them? — WhozCraig
I'm not sure what you mean as all functions in the linkedList class are implemented. The linker error occurs due to this line of code: theList->insert(tempPolynomial); — Angel
The linker claims this:bool __cdecl operator<(class Term,class LinkedList) is not found. insert() is the caller. I can see the decl at the bottom of the header file, so I'm now not sure why your template isn't being expanded. In insert() this: tempNode->mData < data is where it is pulled in. — WhozCraig
In my main function the LinkedList is initialized as a type Term, which would make data have a type of Term too. So shouldn't it be successfully pulled in? — Angel
Are you saying they have to be overloaded to work specifically with the Term class? Is this something I'd overload/do in the Term class? Also thanks for your help so far. — Angel

WhozCraig WhozCraig · Accepted Answer · 2013-09-14T06:10:43

Your Term class needs an lesser comparator. Either of these will do:

In the term class as a member:

bool operator <(const Term&) const;

Or a free operator function:

bool operator <(const Term& left, const Term& right);

Why? Because LinkedList<T>::insert(T val) invokes the following:

while(tempNode != NULL && tempNode->mData < data)

Both tempNode->mData and data are of type Term with your template expansion. But there is no operator < (either member function or free function) that compares two Term objects for "lesser".

I'm not sure how you want to sort them (I'd likely sort them on exponent first, then coefficient of the exponents are the same). I leave that up to you, but you need the operator regardless.

Example (in the Term class as a member)

bool operator <(const Term& rhs) const
{
    return (mCoefficient < rhs.mCoefficient ||
           (!(rhs.mCoefficient < mCoefficient) == && mExponent < rhs.mExponent));
}

Example II (free operator; NOT a member of Term)

bool operator <(const Term& lhs, const Term& rhs)
{
    return (lhs.getCoefficient() < rhs.getCoefficient() ||
           (!(rhs.getCoefficient() < lhs.getCoefficient()) == && 
             lhs.getExponent() < rhs.getExponent()));
}

Note: if this is friended to Term you can access the members directly rather than going through their getter functions (which, by the way, should be declared const as they make no modifications to the Term object on which they're being called).

C++ Template Linked List Linker Error

1 Answers