Removing items 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; } 

This is reasonably clear, remove_element removes the given element of the dynamic array.

As you can see, each element of the test is initialized with an incrementing integer (ie test [n] == n). However, the program displays

 16 16 

. By removing the test item, one would expect a call to check [n], where n> = the removed item would lead to what test [n + 1] would be before the removal. So I would expect a way out

 16 17 

. What's wrong?

EDIT: The problem is resolved. Here's the fixed code (with rude debugged printfs), if anyone else finds 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

I see several problems in the published code, each of which can cause problems:

returns a new array

Your function accepts an int* array , but then you try to swap it with your temp variable at the end before returning a new array. This will not work, as you are simply replacing the local copy of int* array , which will disappear after returning from the function.

You need to pass the pointer to the array as int** , which will allow you to set the actual pointer to the array in the function, or I would suggest just returning the int * value for your function and returning a new array.

Also, as mentioned in this answer , you really don't need to redistribute when you remove an element from the array, as the original array is large enough to hold everything.

size and offset calculations

• You use sizeof(int*) to calculate the size of an array element. This may work for some types, but, for example, for the array short sizeof(short*) does not work. You do not need the size of the pointer to the array, you want the size of the elements, which for your example should be sizeof(int) , although this may not cause problems in this case.

• Calculating the length for offsets in arrays looks fine, but you forget to multiply the number of elements by the element size for the memcpy size parameter. e.g. memcpy(temp, array, (indexToRemove - 1) * sizeof(int)); .

• The second memcpy call uses temp plus the offset as the source array, but it should be array plus the offset.

• The second memcpy call uses sizeOfArray - indexToRemove for the number of elements to copy, but you should only copy the SizeOfArray - indexToRemove - 1 (or (sizeOfArray - indexToRemove - 1) * sizeof(int) bytes tags

• Wherever you calculate offsets in temp arrays and arrays, you do not need to multiply sizeof (int), since pointer arithmetic already takes into account the size of the elements. (I missed this first, thanks: this answer .)

view the wrong item

You print test[16] (the 17th element) for testing, but you delete the 16th element, which will be test[15] .

corner cabinets

Also (thanks to this answer ) you should handle cases where indexToRemove == 0 and indexToRemove == (sizeOfArray - 1) , where you can do all the deletion in one memcpy.

In addition, you need to worry about the case when sizeOfArray == 1 . In this case, it is possible either to select a size 0 block of size or return zero. In my updated code, I chose to allocate a block of size 0, just to split the array with 0 elements compared to an unallocated array.

The return of an array of size 0 also means that the code does not require additional changes, since the conditions that must be met before each memcpy to handle the first two cases mentioned will prevent memcpy from being executed.

And just note that there is no error handling in the code, so there are implicit assumptions that indexToRemove is within the bounds, that the array not null and that the array has the size passed as sizeOfArray .

updated code example

 int* 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 if (indexToRemove != 0) memcpy(temp, array, (indexToRemove - 1) * sizeof(int)); // copy everything BEFORE the index if (indexToRemove != (sizeOfArray - 1)) memcpy(temp+indexToRemove, array+indexToRemove+1, (sizeOfArray - indexToRemove - 1) * sizeof(int)); // copy everything AFTER the index free (array); return 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; } 

a few words about memory management / abstract data types

Finally, something to consider: there may be problems using malloc to return memory to a user, which should be a free d user, and with free memory, that a malloc user Ed. In general, it is less likely that memory management will be confusing and difficult to process if you design your code modules in such a way that the memory allocation is processed within a single block of logical code.

For example, you can create a module of an abstract data type that would allow you to create an integer array using a structure containing a pointer and a length, and then all manipulations with this data go through functions that take the structure as the first parameter.This also allows you, with the exception of of this module, avoid the need to perform calculations such as elemNumber * sizeof(elemType) . Something like that:

 struct MyIntArray { int* ArrHead; int ElementSize; // if you wanted support for resizing without reallocating you might also // have your Create function take an initialBufferSize, and: // int BufferSize; }; void MyIntArray_Create(struct MyIntArray* This, int numElems /*, int initBuffSize */); void MyIntArray_Destroy(struct MyIntArray* This); bool MyIntArray_RemoveElement(struct MyIntArray* This, int index); bool MyIntArray_InsertElement(string MyIntArray* THis, int index, int Value); 

etc..

It basically implements some C ++ -like functions in C, and this IMO is a very good idea, especially if you are starting from scratch and want to create something more than a simple application. I know some C developers who really don't like this idiom, but it worked well for me.

The good thing about this way of implementing things is that anything in your code that uses a function to remove an element will never touch the pointer directly. This would allow several parts of your code to store a pointer to your abstract array structure, and when the pointer to the actual data of the array was redistributed after the element was deleted, all variables pointing to your abstract array would be automatically updated.

In general, memory management can be very confusing, and this is one of the strategies that can make it less. Just a thought.

Answer 2

In fact, you are not changing the passed pointer. You change 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 indicates where it used the BUT point, you also freed it, which adds an insult to the 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 the passed pointer .

Answer 3

@cnicutar is correct (+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 multiplication by size int* is done by the compiler (this pointer arithmetic)

Also, when moving overlapping memory areas, use memmove , not memcpy .

Answer 4

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

Also pay attention to the case when indexToRemove == 0 .

Answer 5

There are several problems with this code:

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

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

it should be:

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

(b) You do not free memory for the array at the end of main .

(c) memcpy takes the number of bytes to copy as the third parameter. So you need to do a short sizeof(int) again. So:

 memcpy(temp, array, cnt); 

it should be:

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

(d) when copying elements from the old array to the new array, be sure to copy the correct data. For example, there are indexToRemove elements before an element in the indexToRemove index, and not one less. Similarly, you will need to make sure that you copy the correct number of items after the item you want to delete.

(e) When increasing the pointer, you do not need to multiply with sizeof(int) - this is implicit for you. So:

 temp + (cnt * sizeof(int)) 

must be valid:

 temp + cnt 

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

 test = remove_element(test, howMany, 16); 

Answer 6

All other answers give good advice about various problems / errors in the code.

But why redistribute at all (not all errors are related to redistribution)? An array of "smaller" will fit perfectly into an existing memory block:

 // 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; }