Как оптимально удалить элемент из массива, не используя STL?

Оптимальное удаление элемента из массива без STL

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

Подход 1: Сдвиг элементов (Shift)

После нахождения удаляемого элемента, сдвигаем все последующие элементы на одну позицию влево:

void removeElement(int arr[], int& size, int index) {
    if (index < 0 || index >= size) return;
    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i + 1];
    }
    --size;
}

Сложность: O(n) в худшем случае (удаление первого элемента)

Плюсы:

• Простота реализации
• Минимум памяти
• Элементы остаются отсортированы

Минусы:

• O(n) операций в худшем случае
• Дорого для больших объемов

Подход 2: Swap с последним элементом

Меняем местами удаляемый элемент с последним, затем уменьшаем размер:

void removeElementOptimal(int arr[], int& size, int index) {
    if (index < 0 || index >= size) return;
    arr[index] = arr[size - 1];
    --size;
}

Сложность: O(1)

Плюсы:

• Константное время
• Очень быстро
• Отлично для больших массивов

Минусы:

• Нарушается порядок элементов
• Не подходит, если порядок критичен

Подход 3: Ленивое удаление (Mark as deleted)

Помечаем элемент как удаленный, но не сдвигаем:

bool deleted[100];

void removeElementLazy(int index) {
    deleted[index] = true;
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        if (!deleted[i]) {
            std::cout << arr[i] << " ";
        }
    }
}

Плюсы:

• O(1) удаление
• Легко реализовать undo
• Batch-обработка

Минусы:

• Требует доп. памяти
• Вывод медленнее
• Не уменьшает реальный размер

Подход 4: Удаление с сохранением порядка (оптимизированное)

Для удаления нескольких элементов, удаляем с конца на начало:

int removeMultipleElements(int arr[], int size, int* toRemove, int removeCount) {
    int newSize = size;
    for (int i = removeCount - 1; i >= 0; --i) {
        int idx = toRemove[i];
        for (int j = idx; j < newSize - 1; ++j) {
            arr[j] = arr[j + 1];
        }
        --newSize;
    }
    return newSize;
}

Подход 5: Два указателя (Partition-like)

Для удаления по условию:

int removeIf(int arr[], int size, bool (*predicate)(int)) {
    int write = 0;
    for (int read = 0; read < size; ++read) {
        if (!predicate(arr[read])) {
            arr[write++] = arr[read];
        }
    }
    return write;
}

Сложность: O(n), одиночный проход

Рекомендации

Используйте Shift когда:

• Порядок критичен
• Удаляется редко
• Массив малый

Используйте Swap когда:

• Порядок не важен
• Производительность критична
• Удаляется часто

Используйте Mark as deleted когда:

• Нужна функция undo
• Удаления и вставки часты
• Есть доп. память

Используйте Two-pointer когда:

• Нужно удалить несколько элементов
• Удаляется по условию
• Производительность и порядок оба важны

Практический пример для production code

template <typename T>
class SimpleArray {
private:
    T* data;
    int size;
    int capacity;
    
public:
    void remove(int index) {
        if (index < 0 || index >= size) return;
        data[index] = data[size - 1];
        --size;
    }
};

Выбор правильного подхода зависит от конкретной задачи и требований к производительности.