CODEWITHSUNDEEP
c++pointersmemory-leaksnested
Kirill Korolev
Kirill Korolev

Reputation: 1006

Deallocate pointer to a struct preserving memory addresses of nested variables

template<typename T>
T& List<T>::popFront()
{
    if (head == NULL)
        throw std::underflow_error("List error: no head node available\n");
    if (tail == head)
        tail = NULL;
    T item = head->item;
    head = head->next;
    return item;
}

I have a recursive struct ListNode with the following fields:

template <typename T>
struct ListNode {
    T item;
    ListNode* next;
    ...
}

The problem is that I want to deallocate a head node after popFront procedure, but as all the nested nodes are indirectly pointing to the same address, their addresses also vanish from the heap. So for now as you can see above I just alter the pointer address of a head node to the next one, which I believe leads to a memory leak.

I do not exclude that I'm absolutely wrong with this approach and my assumption. Please, consider the most efficient way to perform such task, if this deallocation is really necessary.

Upvotes: 0

Views: 129

Answers (2)

Ramon
Ramon

Reputation: 1299

There are a couple of problems here.

template<typename T>
T& List<T>::popFront()
{
    if (head == NULL)
        throw std::underflow_error("List error: no head node available\n");
    if (tail == head)
        tail = NULL;
    T item = head->item;
    head = head->next; //Memory leak, you just lost your only pointer to the head item
    return item; //Returning reference to stack variable, undefined behavior
}

I would suggest that you change the signature to return by value, so that you can return a local and deallocate the element in the heap. 

template<typename T>
T List<T>::popFront()
{
    if (head == NULL)
        throw std::underflow_error("List error: no head node available\n");
    if (tail == head)
        tail = NULL;
    T item = head->item;
    ListNode* old_head = head; //keep this for deallocation
    head = head->next;
    delete old_head; //Deallocate the old head
    return item; //Return by value
}

You could, of course, adopt the behavior of std::list and have different methods for access and popping, front() and pop_front() respectively.

As per the signature, front() returns a reference, which is far more efficient if T is a heavy object.

This is all assuming you're doing it for academic purposes, of course. Otherwise, well, use std::list or a similar standard library container.

Upvotes: 2

patatahooligan
patatahooligan

Reputation: 3321

When you pop the head, before deleting it, grab the next pointer and make it head.

template<typename T>
T List<T>::popFront()
{
    if (head == NULL)
        throw std::underflow_error("List error: no head node available");
    if (tail == head)
        tail = NULL;
    T item = head->item;
    ListNode *next = head->next;    // Grab next
    delete head;                    // Now it is safe to delete head
    head = next;                    // Head now points to next
    return item;
}

Is the tail needed here? Why not just have next of head equal to NULL when there is only one node?

EDIT: Just noticed. You're not supposed to return a reference to Item because we're destroying the ListNode that was holding it. Return by value. Alternatively you can return ListNode* rather than deleting it, but this is probably not how you want List's interface to work.

Upvotes: 1

Related Questions