Templates & Queues

[Cross213]

What's wrong with this code, I'm getting LNK errors

#include "Queue.h"

int main()
{
	Queue <int> q;	// q is an object

	q.showQ();
	q.insert(72);
	q.insert(36);
	q.insert(43);
	q.showQ();
	q.remove();
	q.showQ();

	return 0;
}

[Fbody]

Is "Queue.h" a custom header that you wrote or are you attempting to use the queue that is part of the STL? It looks custom.

What O/S and IDE are you using?

If you are getting a linker error, it means that the linker can't find the implementation of your function(s). It knows they should exist and that they've been called, but it can't find the actual function to incorporate it into the finished executable file.

[Cross213]

It is a custom header, here's the full code:

#ifndef QUEUE_H
#define QUEUE_H

template <class Type>
struct node
{
	Type info;
	node<Type> *next;
};

template <class Type>
class Queue
{
	private:
		node<Type> *front;
	public:
		Queue();
		~Queue();
		bool isEmptyQ();
		bool isFullQ();
		void insert(Type info);
		void remove();
		void showQ();
};

#endif

[Narue]

If that's the full code then you're missing definitions for all of the member functions.

[Fbody]

OK. That looks like a well-designed/written header. But, all that I see are declarations/prototypes for the member functions. Where are your implementations for

Queue::Queue();
Queue<Type>::~Queue();
bool Queue<Type>::isEmptyQ();
bool Queue<Type>::isFullQ();
void Queue<Type>::insert(Type info);
void Queue<Type>::remove();
void Queue<Type>::showQ();

Do you have another *.cpp file out there somewhere?

EDIT:
Oops, Narue snuck in there...

[Cross213]

Oh yes here it is:

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

template <class Type>
Queue<Type>::Queue()
{
	front = NULL;
}

template <class Type>
Queue<Type>::~Queue()
{
	node<Type> *tmp;
	while (front != NULL)
	{
		tmp = front->next;
		delete front;
		front = tmp;
	}
}

template <class Type>
bool Queue<Type>::isEmptyQ()
{
	return (front == NULL);
}

template <class Type>
bool Queue<Type>::isFullQ()
{
	// Please correct
	return false;
}

template <class Type>
void Queue<Type>::insert(Type info)
{
	if (isEmptyQ())
	{
		node<Type> *tmp = new node<Type>;
		tmp->info = info;
		tmp->next = NULL;
		front = tmp;
	}
	else
	{
		node<Type> *tmp = new node<Type>;
		tmp->info = info;
		tmp->next = NULL;
		node<Tyep> *last = front;
		while (last->next != NULL)
			last = last->next;
		last->next = tmp;
	}
	
}

template <class Type>
void Queue<Type>::remove()
{
	if(isEmptyQ())
		cout << "Cannot remove. Queue is empty" << endl;
	else if(front->next == NULL)
	{
		delete front;
		front = NULL;
	}
	else
	{
		node<Type> *tmp = front;
		front = front->next;
		delete tmp;
	}
}

template <class Type>
void Queue<Type>::showQ()
{
	node<Type> *current = front;
	
	if(isEmptyQ())
		cout << "List is empty, cannot display" << endl;

	while(current!= NULL)
	{
		cout << current->info << endl;
		current = current->next;
	}
}

[Fbody]

OK. I don't really see anything in this file that screams "ERROR!!!" (didn't look all that close though).

Do you know that this file (presumably called "Queue.cpp") is getting compiled?

[Cross213]

I know I also don't see errors but I'm getting them though. I'm rather new to class templates so I'm assuming something is wrong with the way I implemented it

[vijayan121]

See: http://www.parashift.com/c++-faq-lite/templates.html#faq-35.12

[Cross213]

See: http://www.parashift.com/c++-faq-lite/templates.html#faq-35.12

Thanks for that link, was very helpful but I have done all that to the letter, but for the life of me I still can't understand why it's not working, it's infuriating, any other help will be much appreciated.

[Fbody]

The errors you are getting are LINKER errors, not COMPILER errors. Which means that, as long as your function identifiers match (which they seem to), your syntax is correct.

Again I ask, What Operating System and IDE are you using? I'm betting that your implementation file (*.cpp file) either isn't getting compiled because you haven't added it to your project, or make file as the case may be, or you haven't specified the resulting object file as part of the linking process.

[Cross213]

OS: Windows 7 IDE: VS 2008

[vijayan121]

It's not an OS or IDE issue.

#include "Queue.h"
#include "Queue.cpp"

int main()
{
	Queue <int> q;	// q is an object

	q.showQ();
	q.insert(72);
   
        // ...
}

[Fbody]

It's not an OS or IDE issue.

#include "Queue.h"
#include "Queue.cpp"

int main()
{
	Queue <int> q;	// q is an object

	q.showQ();
	q.insert(72);
   
        // ...
}

Yeah, I was just coming to that conclusion as well. This situation is one of the rare ones where you have to #include a *.cpp file in another *.cpp file instead of relying on a make file and/or the linker to handle it for you. I don't fully understand why, it's something about the way templates work "under the hood", it's just one of those things you have to do.

[mike_2000_17]

>>I don't fully understand why, it's something about the way templates work "under the hood", it's just one of those things you have to do.

This is a fundamental aspect of templates, and it is important to understand it:

A function or class template is NOT a function or class, it is a set of instructions (template) for the compiler that tells it how to _generate_ an actual function or class once the template arguments (like T) are specified (e.g. at the point where Queue<int> is used, this point is called the "instantiation").

Once you understand that, then it becomes clear that the _compiler_ (not linker) has to see the implementation (definition) of the function / class templates in order to be able to generate the actual code upon instantiation. So, you cannot put the definition of function templates in a separately compiled cpp file. The options are to either:

1) define the function templates at their declaration-site (in header);
2) define the function templates anywhere in the header file;
3) define the function templates in a cpp file which you #include at the end of the header-file (within the guard);
4) define the function templates in a cpp file which has a set of explicit template instantiations for all the possible or useful instantiations of those function / class templates.

This was the main point in the earlier link given by vijayan121.

[Fbody]

A function or class template is NOT a function or class, it is a set of instructions (template) for the compiler that tells it how to _generate_ an actual function or class once the template arguments (like T) are specified (e.g. at the point where Queue<int> is used, this point is called the "instantiation").

I understand this part, and I know how to correct it, it was the rest that I couldn't connect. I knew it had something to do with the contents of a single translation unit. Hence, the use of the qualifier "fully". Thanks.

[Cross213]

Okay so here's what I have now:

#include "Queue.h"
#include "Queue.cpp"

template <class Type>
int main()
{
	Queue <int> q;	// q is an object

	q.showQ();
	q.insert(72);
	q.insert(36);
	q.insert(43);
	q.showQ();
	q.remove();
	q.showQ();

	return 0;
}

I had 6 errors before now I have 2 after #including "Queue.cpp". It says fatal error LNK1120: 1 unresolved externals and error LNK2019: unresolved external symbol _main referenced in function ___tmainCRTStartup

[Fbody]

main() can't be a template function. Get rid of Line 4.

[Cross213]

Great success! It works, thanks for the help gents, really appreciate it.