Removing elements from array in C-CodePudding

What I am trying to achieve is to loop through an array ONCE and while doing so, also remove elements that my function returns false for. However the code I've written does not work. Any idea would be greatly appreciated because I am truly stuck and I don't understand what I am doing wrong

#include <stdio.h>

bool isitright(int i) {
    if (i/2 == 0) {
        return false;
    } else {
        return true;
    }
}

int main() {
    int arr[4] = {0, 1, 2, 3};
    int i = 0;
    while (i < 4) {
        if(!isitright(i)) {
            arr[i] = arr[i 1];
        }
        i  ;
    }
}

CodePudding user response：

How to "remove an element" from an array in C. You might also call this "filtering an array" in C.

You can't resize statically-allocated arrays in C. Instead, you just keep track of a size variable and adjust it accordingly and only print what you need to.

Download my full, runnable examples for both approaches below in my eRCaGuy_hello_world repo here: array_filter_and_remove_element.c

1. Approach 1 [better approach]: filter an array into another array

For n elements in the array:
Time complexity: O(n)
Space complexity: O(2n) = O(n)

The easiest approach if you're trying to filter certain values from an array, however, is to just copy to a new array. So, here is a demo of that. In this demo, I begin with an array containing [-3, -2, -1, 0, 1, 2, 3], and I filter out all -1, 0, and 1 values with your little is_it_right() algorithm, to end up with [-3, -2, 2, 3] in the new array when I'm done.

To do that in-place in the same array would require a more-advanced algorithm that would almost certainly have the tradeoff of running slower, but, while not doubling the array space. The below approach will run very fast but I double the array space since I'm copying from one array into another rather than filtering the array in-place.

Anyway, study this carefully:

Run it online on OnlineGDB here.

#include <stdbool.h>
#include <stdio.h>

/// Get the number of elements in an array
#define ARRAY_LEN(array) (sizeof(array)/sizeof(array[0]))

/// Return false for -1, 0, or  1, and return true otherwise.
bool is_it_right(int i)
{
    if (i/2 == 0)
    {
        return false;
    }
    
    return true;
}

void print_array(int arr[], size_t len)
{
    printf("[");
    for (size_t i = 0; i < len; i  )
    {
        printf("%i", arr[i]);
        if (i < len - 1)
        {
            printf(", ");
        }
    }
    printf("]\n");
}

int main()
{
    int arr[] = {-3, -2, -1, 0, 1, 2, 3};
    int arr_filtered[ARRAY_LEN(arr)];
    size_t arr_filtered_len; 
    
    // Remove values -1, 0, and  1 from the array
    int j = 0;
    for (size_t i = 0; i < ARRAY_LEN(arr); i  ) 
    {
        if (is_it_right(arr[i]))
        {
            arr_filtered[j] = arr[i];
            j  ;
        }
    }
    arr_filtered_len = j;
    
    print_array(arr, ARRAY_LEN(arr));
    print_array(arr_filtered, arr_filtered_len);
    
    return 0;
}

Output:

[-3, -2, -1, 0, 1, 2, 3]
[-3, -2, 2, 3]

2. Approach 2: [way more complicated and processor-intensive and copy-intensive] filter an array in-place

For n elements in the array:
Time complexity: best-case (nothing to filter out): O(n); worst-case (all elements must be filtered out 1-at-a-time): O(n^2)
Space complexity: O(n)

This approach is way more complicated, more processor-intensive, and more copy-intensive. I recommend the approach above instead.

printf("\n====================================\n"
       "APPROACH 2: FILTER AN ARRAY IN-PLACE\n"
       "====================================\n");

// Remove values -1, 0, and  1 from the array **in place**
size_t arr_len = ARRAY_LEN(arr);
printf("Starting array:\n");
print_array(arr, arr_len);
size_t i = 0;
while (i < arr_len)
{
    if (is_it_right(arr[i]) == false)
    {
        // We don't want to keep this value at `arr[i]`, so overwrite it
        // by shifting all values from `i   1` to the end of the array to
        // the left by 1 place.
        printf("Removing value `%i` from the array\n", arr[i]);
        size_t i_write = i;
        for (size_t i_read = i_write   1; i_read < arr_len; i_read  )
        {
            arr[i_write] = arr[i_read];
            i_write  ;
            print_array(arr, arr_len);
        }
        arr_len--;
        printf("One element has just been removed. Here is the new array:\n");
        print_array(arr, arr_len);
    }
    else // is_it_right(arr[i]) == true
    {
        // only increment `i` if we did NOT just left-shift a bunch of
        // elements by one index place
        i  ;
    }
}
printf("Here is the final, filtered-in-place array:\n");
print_array(arr, arr_len);

Sample output:

====================================
APPROACH 2: FILTER AN ARRAY IN-PLACE
====================================
Starting array:
[-3, -2, -1, 0, 1, 2, 3]
Removing value `-1` from the array
[-3, -2, 0, 0, 1, 2, 3]
[-3, -2, 0, 1, 1, 2, 3]
[-3, -2, 0, 1, 2, 2, 3]
[-3, -2, 0, 1, 2, 3, 3]
One element has just been removed. Here is the new array:
[-3, -2, 0, 1, 2, 3]
Removing value `0` from the array
[-3, -2, 1, 1, 2, 3]
[-3, -2, 1, 2, 2, 3]
[-3, -2, 1, 2, 3, 3]
One element has just been removed. Here is the new array:
[-3, -2, 1, 2, 3]
Removing value `1` from the array
[-3, -2, 2, 2, 3]
[-3, -2, 2, 3, 3]
One element has just been removed. Here is the new array:
[-3, -2, 2, 3]
Here is the final, filtered-in-place array:
[-3, -2, 2, 3]

Again, the full, runnable examples for both approaches above are in my eRCaGuy_hello_world repo here: array_filter_and_remove_element.c