Удаление элементов из динамических массивов

Итак, у меня есть это:

#include  #include  #include  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; } 

Это разумно понятно, remove_element удаляет данный элемент динамического массива.

Как вы можете видеть, каждый элемент теста инициализируется инкрементным целым числом (т. Е. Test [n] == n). Однако результаты программы

 16 16 

, Удалив элемент теста, можно было бы ожидать вызова для проверки [n], где n> = удаленный элемент приведет к тому, какой тест [n + 1] был бы до удаления. Поэтому я ожидал бы выход

 16 17 

, Что случилось?

EDIT: Проблема решена. Вот фиксированный код (с грубыми отлаженными printfs), если кто-нибудь еще найдет это полезным:

 #include  #include  #include  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; } 

    Я вижу несколько проблем в опубликованном коде, каждый из которых может вызвать проблемы:

    возврат нового массива

    Ваша функция принимает int* array но затем вы пытаетесь поменять ее с помощью переменной temp в конце перед возвратом нового массива. Это не будет работать, поскольку вы просто заменяете локальную копию int* array которая исчезнет после возврата из функции.

    Вам нужно либо передать указатель массива в виде int** , что позволит вам установить фактический указатель на массив в функции, или я бы предложил просто вернуть значение int * для вашей функции и вернуть новый массив.

    Кроме того, как упоминалось в этом ответе , вам действительно не нужно перераспределять при удалении элемента из массива, поскольку исходный массив достаточно велик, чтобы держать все.

    расчеты размера и смещения

    1. Вы используете sizeof(int*) для вычисления размера элемента массива. Это может работать для некоторых типов, но, например, для short массива sizeof(short*) не работает. Вам не нужен размер указателя на массив, вы хотите размер элементов, который для вашего примера должен быть sizeof(int) хотя в этом случае это может не вызвать проблем.

    2. Расчет длины для смещений в массивах выглядит нормально, но вы забываете умножать количество элементов по размеру элемента для параметра размера memcpy. например memcpy(temp, array, indexToRemove * sizeof(int)); ,

    3. Второй вызов memcpy использует temp plus offset как исходный массив, но он должен быть array плюс смещение.

    4. Второй вызов memcpy использует sizeOfArray - indexToRemove для количества копируемых элементов, но вы должны копировать только SizeOfArray - indexToRemove - 1 элемент (или (sizeOfArray - indexToRemove - 1) * sizeof(int) байты

    5. Везде, где вы вычисляете смещения в массивах temp и массивов, вам не нужно умножать sizeof (int), так как арифметика указателя уже учитывает размер элементов. (Я пропустил это сначала, благодаря: этому ответу .)

    глядя на неправильный элемент

    Вы test[16] печать test[16] (17-й элемент) для тестирования, но вы удаляете 16-й элемент, который будет test[15] .

    угловые шкафы

    Также (благодаря этому ответу ) вы должны обрабатывать случаи, когда indexToRemove == 0 и indexToRemove == (sizeOfArray - 1) , где вы можете сделать все удаление в одной memcpy.

    Кроме того, вам нужно беспокоиться о случае, когда sizeOfArray == 1 . В этом случае, возможно, либо выделите блок размера 0 размера, либо верните нуль. В моем обновленном коде я выбрал выделение блока размером 0, просто чтобы разделить массив с 0 элементами по сравнению с нераспределенным массивом.

    Возrotation массива 0-го размера также означает, что для кода не требуется никаких дополнительных изменений, поскольку условия перед каждой memcpy для обработки первых двух упомянутых случаев будут препятствовать проведению memcpy.

    И просто отметим, что в коде нет обработки ошибок, поэтому существуют неявные предпосылки, что indexToRemove находится в границах, этот array не является нулевым, и этот array имеет размер, передаваемый как sizeOfArray .

    пример обновленного кода

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

    несколько слов об управлении памятью / абстрактных типах данных

    Наконец, что-то для рассмотрения: возможны проблемы с использованием malloc для возврата памяти пользователю, который, как ожидается, будет free пользователем, и с free памятью, которую пользователь malloc . В целом, менее вероятно, что управление памятью будет запутанным и трудно справиться, если вы создадите свои кодовые единицы таким образом, чтобы распределение памяти обрабатывалось в одном логическом блоке кода.

    Например, вы можете создать абстрактный модуль типа данных, который позволил бы создать целочисленный массив, используя структуру, содержащую указатель и длину, а затем все манипуляции с этими данными проходят через функции, принимающие структуру в качестве первого параметра. Это также позволяет вам, кроме этого модуля, избегать выполнения вычислений, таких как elemNumber * sizeof(elemType) . Что-то вроде этого:

     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); 

    и т.п.

    Это в основном реализует некоторые C ++-подобные функции на C, и это IMO - очень хорошая идея, особенно если вы начинаете с нуля, и хотите создать что-то большее, чем простое приложение. Я знаю некоторых разработчиков C, которые действительно не любят эту идиому, но это сработало хорошо для меня.

    Хорошая вещь об этом способе реализации вещей заключается в том, что что-либо в вашем коде, использующем функцию для удаления элемента, никогда не коснется указателя напрямую. Это позволило бы нескольким частям вашего кода хранить указатель на вашу абстрактную структуру массива, и когда указатель на фактические данные массива был перераспределен после удаления элемента, все переменные, указывающие на ваш абстрактный массив, будут автоматически обновляться.

    В общем, управление памятью может быть очень запутанным, и это одна страtagsя, которая может сделать ее менее эффективной. Просто мысль.

    Фактически вы не изменяете переданный указатель. Вы меняете только свою копию 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. */ } 

    Поэтому после функции массив все еще указывает на то, где он использовал точку BUT, вы также освободили его, что добавляет оскорбление к травме.

    Попробуйте что-то вроде этого:

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

    Существует также C FAQ: изменение пройденного указателя .

    @cnicutar прав (+1), но также вы пишете:

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

    в то время как это должно быть:

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

    Поскольку умножение на размер int* выполняется компилятором (это арифметика указателя)

    Кроме того, при перемещении memmove областей памяти используйте memmove а не memcpy .

    Далее: второй аргумент второго вызова memcpy должен основываться на array , а не на temp , правильно? И разве вы не должны mallocing и копирование на основе sizeof int а не на основе sizeof int* , так как ваши массивы хранят целые числа, а не указатели? И вам не нужно умножать количество байтов, которые вы копируете (последний аргумент memcpy ) на sizeof int ?

    Также indexToRemove == 0 на случай, когда indexToRemove == 0 .

    Есть несколько проблем с этим кодом:

    (a) При распределении памяти вы должны убедиться, что используете правильный тип с sizeof . Для массива int например, вы выделяете блок памяти с размером, кратным sizeof(int) . Так :

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

    должно быть :

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

    (b) Вы не освобождаете память для массива в конце main .

    (c) memcpy берет количество байтов для копирования в качестве третьего параметра. Таким образом, вам нужно снова удостовериться, что нужно передать кратность sizeof(int) . Так :

     memcpy(temp, array, cnt); 

    должно быть :

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

    (d) при копировании элементов из старого массива в новый массив обязательно скопируйте правильные данные. Например, есть элементы indexToRemove перед элементом в index indexToRemove , а не один меньше. Аналогичным образом, вам необходимо убедиться, что вы скопируете правильное количество предметов после элемента, который необходимо удалить.

    (e) При увеличении указателя вам не нужно умножаться с sizeof(int) – это делается неявно для вас. Так :

     temp + (cnt * sizeof(int)) 

    должно быть действительно:

     temp + cnt 

    (f) В вашей функции remove_element вы присваиваете значение локальному array переменных. Любые изменения локальных переменных не видны вне функции. Итак, после завершения вызова remove_element вы не увидите изменения в main . Один из способов решения этой проблемы – вернуть новый указатель из функции и назначить ее в main :

     test = remove_element(test, howMany, 16); 

    Все остальные ответы дают хорошие советы о различных проблемах / ошибках в коде.

    Но зачем вообще перераспределять (не то, что ошибки связаны с перераспределением)? Массив «меньшего» будет прекрасно вписываться в существующий блок памяти:

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