Simple Queue Question

Hi,

I'm trying to create a simple queue structure and am running into problems when I try to empty the queue. Here's the relevant pieces of code:

Code:

typedef struct queue_item {
   void *item;
   struct queue_item *next;
} q_item;

...
...

void GenericQueue::empty(q_item *i)
{
    if (i != NULL) {
        empty(i->next);
        free(i);
    }
}

It's all very simple but with Visual C++ I get an undefined heap error on the "free(i)" line. I thought I understood the basics of memory management but obviously not...can anyone point out my mistake?

Thanks,
Rob

> ...can anyone point out my mistake?

Yes. You're writing a queue in C++.

You've forgotten to set the pointer that you've just free'd (BTW, use new/delete) to NULL, so the function deletes it, then tries to delete it again.

As pointed out, you should be using new and delete.

In addition, you are not deallocating memory for member variable item. If you're not supposed to be doing that here, that's fine, but I can't imagine why you would not be doing it now.

Originally Posted by UMR_Student

You've forgotten to set the pointer that you've just free'd (BTW, use new/delete) to NULL, so the function deletes it, then tries to delete it again.

No double-free()ing is occurring unless I'm missing something. It's calling empty() on the next item in the list, and then free()ing it. It appears to be proper C code.

Thanks for the replies

In addition, you are not deallocating memory for member variable item. If you're not supposed to be doing that here, that's fine, but I can't imagine why you would not be doing it now.

This is only a queue of pointers to other data structures, so given that these structures may be needed elsewhere I'm requiring explicit deallocation.

Yes. You're writing a queue in C++.

Thanks for the cryptic comment! Being fairly new to C++ and considering its relationship to C I figured I'd have to create a queue class myself. After reading this I had a search and discovered the existing C++ queue class, which I presume is where you're coming from.

Can I safely assume that the standard C++ queue is going to be more efficient than anything I can cobble together? If so then I'll gladly use this existing one instead of creating my own, it's just going to be used as a utility function anyway. The one constraint I do have is performance; this queue is being used as part of a distributive intelligence simulator and so I need it to be as bare-bones and efficient as possible. I'm just wondering how much extra functionality is attached to the C++ queue that I won't need and that will slow it down significantly.

Essentially what I'm asking is this: Is the standard C++ queue about as efficient as it gets? Or could I acheive better performance by creating my own?

Thanks again,
Rob

I guess you can safely use the standard queue. I think it is based on a more efficient container (std::deque by default - if I'm not mistaken) than a linked list.

If you want to write your own, you should adopt some C++ practices: templates versus void*.

The empty function also has some problems: something like that shouldn't be done by recursion, and I think the function shouldn't take the starting pointer from the caller (unless you want to empty from this point forward) - GenericQueue should know where the data begins (and ends).

Originally Posted by anon

The empty function also has some problems: something like that shouldn't be done by recursion, and I think the function shouldn't take the starting pointer from the caller (unless you want to empty from this point forward) - GenericQueue should know where the data begins (and ends).

I figured a good method would be to follow pointers to the end of the queue and then deallocate backwards, but my experience with C++ is severely lacking. I also forgot to mention that the "empty (q_item*)" function defined above is private, and a public method "empty(void)" exists that simply calls it with the first element in the list. Again, the best way I could think of doing it.

Originally Posted by anon

I guess you can safely use the standard queue. I think it is based on a more efficient container (std::deque by default - if I'm not mistaken) than a linked list.

I guess I'll use the library function then, thanks for the information. The implementation method is of no real significance as long as it works quickly and I guess the C++ designers have more than my two weeks experience with the language...!

Cheers all
Rob