views:

348

answers:

4

[[UPDATE]] -> If I #include "Queue.cpp" in my program.cpp, it works just fine. This shouldn't be necessary, right?

Hey all -- I'm using Visual Studio 2010 and having trouble linking a quick-and-dirty Queue implementation. I started with an empty Win32 Console Application, and all files are present in the project. For verbosity, here's the complete code to duplicate my error. I realize some of the code may, in fact, be wrong. I haven't had a chance to test it yet because I haven't yet been able to link it.

Queue.hpp

#ifndef ERROR_CODE
#define ERROR_CODE
enum Error_Code
{
    Success,
    Underflow,
    Overflow
};
#endif // ERROR_CODE

#ifndef QUEUE
#define QUEUE
template<class T>
struct Queue_Node
{
    T data;
    Queue_Node *next;

    Queue_Node()
    {
        next = NULL;
    }
    Queue_Node(T pData)
    {
        data = pData;
        next = NULL;
    }
    Queue_Node(T pData, Queue_Node *pNext)
    {
        data = pData;
        next = pNext;
    }
};

template<class T>
class Queue
{
public:
    Queue();
    Error_Code Serve();
    Error_Code Append(T item);
    T Front();
    ~Queue();

private:
    void Rescursive_Destroy(Queue_Node<T> *entry);
    Queue_Node<T> *front, *rear;
};
#endif // QUEUE

Queue.cpp

#include "Queue.hpp"

template <class T>
Queue<T>::Queue()
{
    this->front = this->rear = NULL;
}

template<class T>
Error_Code Queue<T>::Serve()
{
    if(front == NULL)
        return Underflow;

    Queue_Node *temp = this->front;
    this->front = this->front->next;
    delete temp;
}

template<class T>
Error_Code Queue<T>::Append(T item)
{
    Queue_Node *temp = new Queue_Node(item);
    if(!temp)
        return Overflow;

    if(this->rear != NULL)
        this->rear->next = temp;
    this->rear = temp;

    return Success;
}

template<class T>
T Queue<T>::Front()
{
    if(this->front == NULL)
        return Underflow;
    return this->front->data;
}

template<class T>
Queue<T>::~Queue()
{
    this->Rescursive_Destroy(this->front);
}

template<class T>
void Queue<T>::Rescursive_Destroy(Queue_Node<T> *entry)
{
    if(entry != NULL)
    {
        this->Recursive_Destroy(entry->next);
        delete entry;
    }
}

program.cpp

#include "Queue.hpp"

int main()
{
    Queue<int> steve;
    return 0;
}

And the errors...

Error   1   error LNK2019: unresolved external symbol "public: __thiscall Queue<int>::~Queue<int>(void)" (??1?$Queue@H@@QAE@XZ) referenced in function _main    C:\[omitted]\Project2_2\Project2_2\program.obj  Project2_2
Error   2   error LNK2019: unresolved external symbol "public: __thiscall Queue<int>::Queue<int>(void)" (??0?$Queue@H@@QAE@XZ) referenced in function _main C:\[omitted]\Project2_2\Project2_2\program.obj  Project2_2
+2  A: 

The linker errors are because it sees the header files for Queue.hpp, but doesn't see the definitions of the functions. This is because it is a template class, and for C++, the definitions of templates must be in the header file (there are a few other options, but that is the easiest solution). Move the defintions of the functions from Queue.cpp to Queue.hpp and it should compile.

Todd Gardner
Yes, all files are included. If I, for example, omit a semicolon in Queue.cpp, the project doesn't get to the linking process because it suddenly fails to compile.
Legatou
I didn't notice it was a template during my first pass; that explains the error.
Todd Gardner
Why do templates cause this error? Also... [[UPDATE]] -> If I #include "Queue.cpp" in my program.cpp, it works just fine. This shouldn't be necessary, right?
Legatou
See answers like this one: http://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file
Todd Gardner
A: 

All template code need to be accessible during compilation. Move the Queue.cpp implementation details into the header so that they are available.

skimobear
+4  A: 

Why don't you follow the "Inclusion Model"? I'd recommend you follow that model. The compiler needs to have access to the entire template definition (not just the signature) in order to generate code for each instantiation of the template, so you need to move the definitions of the functions to your header.

Note: In general most C++ compilers do not easily support the separate compilation model for templates.

Furthermore you need to read this.

Prasoon Saurav
+2  A: 

If you have:

template <typename T>
void foo();

And you do:

foo<int>();

The compiler needs to generate (instantiate) that function. But it can't do that unless the function definition is visible at the point of instantiation.

This means template definitions needs to be included, in some way, in the header. (You can include the .cpp at the end of the header, or just provide the definitions inline.)

GMan