Undefined Reference Woes

[Volatile Pulse]

I've been helping a friend out with their class on C++ and the most recent program has us stumped. The .h/.cpp files were given to us in a "do not touch" manner and we're to assume they're right. I started the program last week with my friend and the first thing we ran into was every function definition in the .cpp file was giving an undefined reference. All files are properly linked and are giving the same errors across VC++, C::B w/ g++, and even in shell. I know that this should throw up a flag stating that the .h/.cpp files provided are at fault, but reading over them, everything looks perfectly fine.

I manually edited the files so that we could actually get started on writing the program, but it can't be turned in until we figure out what's wrong. So I'm turning to you guys for help. I edited the files so that the .cpp file was #include'd at the bottom of the .h file and his alleviated all issues. Again, this points to a linker error, but I am linking properly and have even tried different computers and projects in the off chance that something got modified on my system.

Sorry for the brevity of this post, but there is some issues going on with some people in the class cheating and I would prefer my friend doesn't come under suspicion for just trying to help them out.

If you need better clarification, please PM me and I'll send you what I have and can explain in better detail.

[zb0S216C]

We have absolutely no idea how those functions are declared. You'll have to show us the code before we can determine why you're getting undefined references. Any suggestions are more or less assumptions and may not be entirely accurate, or even right.

Though, I do point my finger at in-line functions. Because an in-line function definition must be within the same file as the corresponding function declaration, this leads me to believe the separation of function declaration and definition across multiple files is to blame. I'm guessing here, so I'm probably wrong.

_Wazzak

[Volatile Pulse]

I understand, and it makes it hard to post code since it's pretty unique. But what I can say is that it's a linked list class named Queue. There are no inline functions and the definitions look correct from what I can see. I have even cross compared them with other linked list files. Here are the ctor/dtor though:

queue.h

        Queue();
        virtual ~Queue();

queue.cpp

template<class T>
Queue<T>::Queue() : front(NULL), back(NULL) {}
template<class T>
Queue<T>::~Queue()
{
    T next;
    while (!empty())
       next = pop_back();
}

Something I just caught, however, was the declaration of a virtual dtor. Would this affect anything? I get no compiler errors when compiling either the queue files or the main program, but the errors come from specifically the linking process.

[hamsterman]

It sounds like you didn't add the .cpp to your project (or include in the command line). All .cpp files need to be compiled, not just main.cpp. For example, your g++ call should be g++ main.cpp given.cpp.

[Volatile Pulse]

I've had my share of undefined references before and about 99% of the time it's linking issues, the correct file is missing, not added, etc. But this one is different. Every single function definition is unrecognized. I get the same results regardless of having queue.cpp in the linking process or not. Like I said, I can't share the entire files to the public, but I'm able to share them in a PM if you'd prefer.

[Volatile Pulse]

@hamsterman
Yes, I'm fully aware of that, and that is exactly what I would have thought when I first saw this, but compiling in both VC++ and C::B the queue.cpp file are part of the project as is main.cpp. I get the same results regardless of whether or not queue.cpp is part of the linking process leading me to think that there is something wrong with the code, but like I said, everything seems fine. We've also both tried command line compiling and get the same errors that way.

[ne555]

You don't simply separate template definitions.
Either they should be included (but you shouldn't call them *.cpp), or you should use explicit instantiation.

As a side note `a linked list class named Queue'
¿why is it teach like that? Using an array would be more efficient.

[Volatile Pulse]

Because a Queue can be increased in size. Think of a queue of orders. You might have 5 orders in your queue, then you get 5 more, they get added to the end. Using an array, you'd have to allocate for every addition. I believe it was just named this for the actual program though.

Edit: And what did you mean by this?

You don't simply separate template definitions.
Either they should be included (but you shouldn't call them *.cpp), or you should use explicit instantiation.

[hamsterman]

Oh, I see it's a template class? Template classes have to be in headers (implementation too). There is a way to specify what instances are needed and have it work from the cpp, but apparently that isn't done (by adding template class Queue<SomeType>; in the cpp, I think). If you can't modify the .h, you can start your main.cpp with

#include "given.h"
#include "given.cpp" 

Don't include given.cpp in the list of files for g++ (I don't know if there is any harm in including it though).

[zb0S216C]

A template is not a complete type. When you explicitly instantiate a template, you're giving the compiler all the information it needs to generate a new type. See here: http://www.cplusplus.com/forum/beginner/73413/#msg392321

_Wazzak

[Volatile Pulse]

Template classes have issues with linking? I never knew that. So template classes are best left with the definitions in the header file? Where was I during this lesson? -.-

That did fix it though. Thanks for the help. I feel kinda dumb because that's what I tried to get it to work, but I modified the files directly. What's the reason behind this?

[Volatile Pulse]

Many thanks framework. Glad to finally understand that. I always wondered why template class header files typically included the definitions in it.

Marked, Solved.

[ne555]

> Using an array, you'd have to allocate for every addition
Or you could allocate more than you need, so don't have to reallocate so often.
By instance, duplicating the capacity you would reach an amortized O(n lg n) time.

[Volatile Pulse]

@ne555
Don't want to get too far off topic, but isn't that the point of a linked list anyways, to prevent having to allocate each time?

Granted creating an array with a 2x capacity of what's needed is smart, but you may also get to a point where you need one more entry but just allocated another 300 entries, just in case. This doesn't cause issues on smaller programs, but if you have several arrays allocating more than what's required, you program would eventually run out of memory where a linked list only uses what it requires, correct?

I do agree though that the indexing of arrays is brilliant and that aside from iterators, linked lists fail miserably at searching for a specific value, especially in this program where iterators were none existent.

I guess everything has it's pros and cons and there is no "super" container that's perfect in every situation, but that's why you have to weigh the pros against the cons. I used to prefer vectors, but now I'm fond of linked lists. Each has their place, but I tend to lean more towards the linked lists since they have a minimum tradeoff using iterators.

[ne555]

I think that linked list are more useful when you need to insert/delete from any position (there's the problem of finding that position, though)


> but I tend to lean more towards the linked lists since they have a minimum tradeoff using iterators.
Because of the `principle of locality', that trade-off is not minimum. Arrays traversal are a lot faster.

[Volatile Pulse]

Alas, the benefits of sequential memory locations of arrays but the speed of allocating new items for a list. I also wanted to add an indexing ability to lists, but then this wouldn't be as fast as an array but would be simpler.

I guess it just boils down to how often you're adding/removing items from each. If you only care about the top/bottom and are only adding in those places, a list is better. But constantly searching would be better to use an array. The woes of a coder.