Removing elements from an array of pointers - C++

Question

So I had an array of structure pointers. It looked something like this:

index                 [0   1   2   3   4]
value of structure     21  7   42  30  NULL

I was trying to remove the value stored at index 2 (42). I thought that since each element of this array was a pointer to a structure, then in order to delete 42, I would have to first call delete on arr[2], then I would say arr[2] = arr[3] and then delete on arr[3], then arr[3] = arr[4]. That wasn't working so I just decided to try it without the delete keyword and just do arr[2] = arr[3] and arr[3] = arr[4], and it worked. So my question is, why did I not have to use the delete keyword in order to do this. I was thinking that if I just set arr[2] to arr[3], then the structure being pointed to by arr[2] would be lost, and I would get a memory leak. Is that not the case?

Answer 1

I thought that since each element of this array was a pointer to a structure, then in order to delete 42, I would have to first call delete on arr[2]

Yes, you would use delete on arr[2] in order to free the memory to which arr[2] is pointing.

then I would say arr[2] = arr[3]

So far so good.

and then delete on arr[3]

This is the problem right here. Suppose you have code like this:

int arr_cnt = 5;
int *arr[arr_cnt];
for(int i = 0; i < arr_cnt; ++i)
    arr[i] = new int(i+arr_cnt);  // using ints for simplicity, but concept is the same

Your array arr now looks like this:

idx   *arr[]     values in heap, due to using 'new' operator
    +-----+
0   | a---|----> 5
    +-----+
1   | b---|----> 6
    +-----+
2   | c---|----> 7
    +-----+
3   | d---|----> 8
    +-----+
4   | e---|----> 9
    +-----+

Where the letters represent different memory addresses returned by new.

This means that, to properly remove element at index 2, you need to:

1. use delete on arr[2] to avoid a memory leak,
2. overwrite arr[2] with some other address that's still valid (using arr[2] before this step would trigger a seg-fault)
3. nullify array position copied into arr[2] (see below)
4. decrement the length of your array (e.g. arr_cnt--;)

In other words:

delete arr[2];      // step 1, address 'c' no longer valid
arr[2] = arr[4];    // step 2, arr[2] is now 'e', which points to 9 just like arr[4]
arr[4] = NULL;      // step 3, arr[4] is now invalid
--arr_cnt;          // step 4

The diagram would now look like this:

idx   *arr[]     values in heap, due to using 'new' operator
    +-----+
0   | a---|----> 5
    +-----+
1   | b---|----> 6
    +-----+
2   | e---|-----------+   // address 'e' used to be in arr[4]
    +-----+           |
3   | d---|----> 8    |
    +-----+           |
4   | nil |      9 <--+
    +-----+

then arr[3] = arr[4]. That wasn't working

If you follow the diagram, you've probably noticed by now that using delete on both meant that you were invalidating two entries. In other words, if we skip the 2nd diagram and try your delete arr[2]; arr[2] = arr[3]; delete arr[3] logic, you end up with:

delete arr[2];
    +-----+
0   | a---|----> 5
    +-----+
1   | b---|----> 6
    +-----+
2   | c---|----> ?  // invalidated
    +-----+
3   | d---|----> 8
    +-----+
4   | e---|----> 9
    +-----+

arr[2] = arr[3];
    +-----+
0   | a---|----> 5
    +-----+
1   | b---|----> 6
    +-----+
2   | d---|-+
    +-----+ |
3   | d---|-+--> 8  // both have the same address, so point to the same place
    +-----+
4   | e---|----> 9
    +-----+

delete arr[3];
    +-----+
0   | a---|----> 5
    +-----+
1   | b---|----> 6
    +-----+
2   | d---|-+
    +-----+ |
3   | d---|-+--> ?  // both invalid now, but not set to null
    +-----+
4   | e---|----> 9
    +-----+

so I just decided to try it without the delete keyword and just do arr[2] = arr[3] and arr[3] = arr[4], and it worked.

But now you have a memory leak. You always have to delete every new in C++, just like you always have to free every malloc in C.

So my question is, why did I not have to use the delete keyword in order to do this.

You do have to use it. The problem is that you were invalidating more than you thought you were and ended up trying to work with memory that had been deallocated. When a program tries to access memory like this, it causes a segmentation fault. I don't remember the exact message Windows would display, but it's probably an unhandled exception message of some kind. (Segmentation fault tends to be GNU/Linux terminology.)

I was thinking that if I just set arr[2] to arr[3], then the structure being pointed to by arr[2] would be lost, and I would get a memory leak. Is that not the case?

You're correct here. The problem is not your understanding of the new/delete relationship, only the fact that the assignment you described is a shallow copy and you ended up deleting more than expected.

Answer 2

Check to make sure you truly have an array of structure pointers. Also if you do have an array of structure pointers after you delete element at index 2 do not call delete on 3 or the indexes after. Just arr[2] = arr[3]; arr[3] = arr[4]; It's not a memory leak because you are just copying a pointer to the structure not the actual structure.

struct A
    {
    };


//This is an array of A structures
A * array1;

//This is an array of pointers to A structures
A** array2;

Answer 3

I would have to first call delete on arr[2], then I would say arr[2] = arr[3] and then delete on arr[3], then arr[3] = arr[4].

You need to simply delete arr[2] and shift all items to the left, without deleting them. If you apply delete to all consequent objects, then you will loose them all.

Of course, you can simply shift an array without deleting arr[2], but this will cause a memory leak. The object will not be disposed.

Answer 4

The problem you have is that you delete pointers you should not delete.

After you deleted the old pointer at index 2, and assign the at index 3 to index 2, you have two pointers pointing to the same object: At index 2 and 3. Deleting the object pointed to by index 3 delete the object that both pointers point to, making the pointer in index 2 invalid.

The solution to your problem (except switching to std::vector which is what I recommend) is to delete the first object in index 2, move down the values from the higher indexes (e.g. array[2] = array[3]) and set the last pointer to nullptr. No more deleting needed.

Answer 5

The best way is to use Link List.

Follow the below link.

http://www.c4learn.com/data-structure/delete-node-from-first-postion-in-singly-linked-list/