How to remove elements in static array effectively in C

Question

In C programming, suppose we have an array as: A[8] = {3, 5, 6, 8, 2, 9, 10, 1}, how to modify those items by index range? For instance, to "remove" elements from index 3 to 6, since we have static array, after handling, we expect: A[8] = {3, 5, 6, 1, 0, 0, 0, 0}.

concerning dealing with one element at specified index:

for(i= index; i< size - 1; i++)
{
    A[i] = A[i+ 1];
}
size = size - 1

What's the best solution to this problem, suppose the array size can be very large.

Answer 1

With an array, copy is all you can do. You can copy element by element. Or you can use memmove which permits overlapping memory space (memcpy is not safe for overlapping copies). memmove is more efficient than a loop (though optimizing compilers may solve that). You can use either method to copy to a temporary space, or to copy/move in place. In all cases, you must makes sure your vacated cell is cleared.

        // an example that assumes you have valid index and size
        memmove(&A[index], &A[index+1], size-(index+1));
        A[--size] = 0;

The Big(O) is still N (linear with respect to size). With very large arrays, the cost to delete goes up. If unacceptable, you would need a different data structure.

So, consider all your requirements which include cost of inserting, cost of finding/changing, and cost of deleting elements. Choose your data structure to match your requirements. When the data set is small or there are relatively few transactions, the performance differences may not matter to your requirements.

Answer 2

One way to remove elements from array will be to create another array. And then copy elements from (start, left) and (right, end) in second array. Here (left,right) are indices of subarray which you want to remove.

Another way will be to override elements instead of creating another array. If you need to maintain order then care needs to be taken while overriding. else simple copy (right-left) elements from end of array (you need to set these elements to zero) and put it from left..right.