Interestingly array is randomly accessible by the index. And removing randomly an element may impact the indexes of other elements as well.
int remove_element(int*from, int total, int index) {
if((total - index - 1) > 0) {
memmove(from+i, from+i+1, sizeof(int)*(total-index-1));
}
return total-1; // return the new array size
}
Note that memcpy will not work in this case because of the overlapping memory.
One of the efficient way (better than memory move) to remove one random element is swapping with the last element.
int remove_element(int*from, int total, int index) {
if(index != (total-1))
from[index] = from[total-1];
return total; // **DO NOT DECREASE** the total here
}
But the order is changed after the removal.
Again if the removal is done in loop operation then the reordering may impact processing. Memory move is one expensive alternative to keep the order while removing an array element. Another of the way to keep the order while in a loop is to defer the removal. It can be done by validity array of the same size.
int remove_element(int*from, int total, int*is_valid, int index) {
is_valid[index] = 0;
return total-1; // return the number of elements
}
It will create a sparse array. Finally, the sparse array can be made compact(that contains no two valid elements that contain invalid element between them) by doing some reordering.
int sparse_to_compact(int*arr, int total, int*is_valid) {
int i = 0;
int last = total - 1;
// trim the last invalid elements
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last
// now we keep swapping the invalid with last valid element
for(i=0; i < last; i++) {
if(is_valid[i])
continue;
arr[i] = arr[last]; // swap invalid with the last valid
last--;
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements
}
return last+1; // return the compact length of the array
}