Removing elements from an array of pointers - C++

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.