Удалить элемент из массива c

Question

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

Для управления выделенной памятью и определенными элементами у меня есть две другие переменные:

double *arr = NULL;
int elements = 0;
int allocated = 0;

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

Я сомневаюсь, что этот метод безопасен и эффективен.

Answer 1

Я думаю, что это самая эффективная функция, которую вы можете использовать (memcpy - не вариант) в отношении защищенных - вам нужно будет убедиться, что параметры в порядке, иначе произойдут плохие вещи:)

Answer 2

Использование memmove , безусловно, эффективно и не значительно менее безопасно, чем итерация по массиву. Чтобы узнать, насколько безопасна на самом деле реализация, нам нужно увидеть код, в частности вызов memmove и то, как проверяются возвращаемые результаты из realloc.

Если вы ошиблись в memmove или не проверили возврат realloc , ожидайте сбой.

Answer 3

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

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

Answer 4

Производительность memmove() и realloc() может быть увеличена путем разделения данных. Под разделением данных я подразумеваю использование нескольких массивов, а не одного большого массива.

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

int remove_element(int*from, int total, int index) {
        if(index != (total-1))
                from[index] = from[total-1];
        return total-1; // return the number of elements
}

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

Один из способов исправить это - использовать массив масок is_blank и отложить удаление.

int remove_element(int*from, int total, int*is_valid, int index) {
        is_blank[index] = 1;
        return total; // **DO NOT DECREASE** the total here
}

Может создать разреженный массив. Но его также можно заполнить, когда в пустые позиции добавляются новые элементы.

Опять же, можно сделать массив компактным в следующем эффективном алгоритме подкачки.

int sparse_to_compact(int*arr, int total, int*is_valid) {
        int i = 0;
        int last = total - 1;
        // trim the last blank elements
        for(; last >= 0 && is_blank[last]; last--); // trim blank elements from last

        // now we keep swapping the blank with last valid element
        for(i=0; i < last; i++) {
                if(!is_blank[i])
                        continue;
                arr[i] = arr[last]; // swap blank with the last valid
                last--;
                for(; last >= 0 && is_blank[last]; last--); // trim blank elements
        }
        return last+1; // return the compact length of the array
}

Обратите внимание, что вышеприведенный алгоритм использует swap, и он меняет порядок элементов. Может быть предпочтительным / безопасным для использования вне некоторой операции цикла в массиве. И если индексы элементов где-то сохранены, их также необходимо обновить / перестроить.