Removing elements from dynamic arrays

Question

So, I have this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    int* temp = malloc((sizeOfArray - 1) * sizeof(int*)); // allocate an array with a size 1 less than the current one
    memcpy(temp, array, indexToRemove - 1); // copy everything BEFORE the index
    memcpy(temp+(indexToRemove * sizeof(int*)), temp+((indexToRemove+1) * sizeof(int*)), sizeOfArray - indexToRemove); // copy everything AFTER the index
    free (array);
    array = temp;
}

int main()
{
    int howMany = 20;
    int* test = malloc(howMany * sizeof(int*));


    for (int i = 0; i < howMany; ++i)
        (test[i]) = i;



    printf("%d\n", test[16]);
    remove_element(test, howMany, 16);
    --howMany;
    printf("%d\n", test[16]);
    return 0;
}

It's reasonably self-explanatory, remove_element removes a given element of a dynamic array.

As you can see, each element of test is initialised to an incrementing integer (that is, test[n] == n). However, the program outputs

16
16

. Having removed an element of test, one would expect a call to to test[n] where n >= the removed element would result in what test[n+1] would have been before the removal. So I would expect the output

16
17

. What's going wrong?

EDIT: The problem has now been solved. Here's the fixed code (with crude debug printfs), should anyone else find it useful:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int remove_element(int** array, int sizeOfArray, int indexToRemove)
{
    printf("Beginning processing. Array is currently: ");
    for (int i = 0; i < sizeOfArray; ++i)
        printf("%d ", (*array)[i]);
    printf("\n");

    int* temp = malloc((sizeOfArray - 1) * sizeof(int)); // allocate an array with a size 1 less than the current one

    memmove(
            temp,
            *array,
            (indexToRemove+1)*sizeof(int)); // copy everything BEFORE the index

    memmove(
            temp+indexToRemove,
            (*array)+(indexToRemove+1),
            (sizeOfArray - indexToRemove)*sizeof(int)); // copy everything AFTER the index


    printf("Processing done. Array is currently: ");
    for (int i = 0; i < sizeOfArray - 1; ++i)
        printf("%d ", (temp)[i]);
    printf("\n");

    free (*array);
    *array = temp;
    return 0;

}

int main()
{
    int howMany = 20;
    int* test = malloc(howMany * sizeof(int*));


    for (int i = 0; i < howMany; ++i)
        (test[i]) = i;



    printf("%d\n", test[16]);
    remove_element(&test, howMany, 14);
    --howMany;
    printf("%d\n", test[16]);
    return 0;
}

Answer 1

You don't actually change the passed pointer. You're only changing your copy of array.

void remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    int* temp = malloc((sizeOfArray - 1) * sizeof(int*));

    free (array); /* Destroys the array the caller gave you. */
    array = temp; /* Temp is lost. This has **no effect** for the caller. */
}

So after the function the array still points to where it used to point BUT, you've also freed it, which adds insult to injury.

Try something like this:

void remove_element(int **array, int sizeOfArray, int indexToRemove)
                        ^^
{
    int *temp = malloc((sizeOfArray - 1) * sizeof(int*));
    /* More stuff. */

    free(*array);
    *array = temp;
}

There is also a C FAQ: Change passed pointer.

Answer 2

@cnicutar is right (+1), but also, you write:

memcpy(temp+(indexToRemove * sizeof(int*)), temp+((indexToRemove+1) * sizeof(int*)), sizeOfArray - indexToRemove); // copy everything AFTER the index

while it should be:

memmove(temp+(indexToRemove), temp+(indexToRemove+1), sizeOfArray - indexToRemove); // copy everything AFTER the index

Since the multiplication by the size of int* is done by the compiler (that's pointer arithmetic)

Also, when moving overlaying memory areas, use memmove and not memcpy.

Answer 3

Further: the second argument to your second memcpy call should be based on array, not on temp, right? And shouldn't you be mallocing and copying based on sizeof int and not based on sizeof int*, since your arrays store integers and not pointers? And don't you need to multiply the number of bytes you're copying (the last argument to memcpy) by sizeof int as well?

Also, watch the case where indexToRemove == 0.

Answer 4

There are a few problems with that code :

(a) When allocating memory, you need to make sure to use the correct type with sizeof. For an array of int eg., you allocate a memory block with a size that is a multiple of sizeof(int). So :

int* test = malloc(howMany * sizeof(int*));

should be :

int* test = malloc(howMany * sizeof(int));

(b) You don't free the memory for the array at the end of main.

(c) memcpy takes the amount of bytes to copy as the third parameter. So, you need to again make sure to pass a multiple of sizeof(int). So :

memcpy(temp, array, cnt);

should be :

memcpy(temp, array, cnt * sizeof(int));

(d) when copying items from the old array to the new array, make sure to copy the correct data. For example, there are indexToRemove items before the item at index indexToRemove, not one less. Similarly, you'll need to make sure that you copy the correct amount of items after the item that needs to be removed.

(e) When incrementing a pointer, you don't need to multiply with sizeof(int) - that's done implicitly for you. So :

temp + (cnt * sizeof(int))

should really be :

temp + cnt

(f) In your remove_element function, you assign a value to the local variable array. Any changes to local variables are not visible outside of the function. So, after the call to remove_element ends, you won't see the change in main. One way to solve this, is to return the new pointer from the function, and assign it in main :

test = remove_element(test, howMany, 16);

Answer 5

All the other answers make good points about the various problems/bugs in the code.

But, why reallocate at all (not that the bugs are all related to reallocation)? The 'smaller' array will fit fine in the existing block of memory:

// Note: untested (not even compiled) code; it also doesn't do any
//   checks for overflow, parameter validation, etc.
int remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    // assuming that sizeOfArray is the count of valid elements in the array
    int elements_to_move = sizeOfArray - indexToRemove - 1;

    memmove( &array[indexToRemove], &array[indexToRemove+1], elements_to_move * sizeof(array[0]));

    // let the caller know how many elements remain in the array
    //  of course, they could figure this out themselves...
    return sizeOfArray - 1;
}