Thread: Simple Queue Question

  1. #1
    Registered User RobJ's Avatar
    Join Date
    Apr 2006
    Location
    Bath, England
    Posts
    16

    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

  2. #2
    Registered User
    Join Date
    May 2007
    Posts
    88
    > ...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.

  3. #3
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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.

    Quote Originally Posted by UMR_Student View Post
    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.

  4. #4
    Registered User RobJ's Avatar
    Join Date
    Apr 2006
    Location
    Bath, England
    Posts
    16
    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

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User RobJ's Avatar
    Join Date
    Apr 2006
    Location
    Bath, England
    Posts
    16
    Quote Originally Posted by anon View Post
    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.

    Quote Originally Posted by anon View Post
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked-list queue
    By the_winky_files in forum C Programming
    Replies: 17
    Last Post: 11-21-2005, 03:57 PM
  2. Simple class question
    By 99atlantic in forum C++ Programming
    Replies: 6
    Last Post: 04-20-2005, 11:41 PM
  3. Simple question about pausing program
    By Noid in forum C Programming
    Replies: 14
    Last Post: 04-02-2005, 09:46 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM