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

Оптимальность зависит от требования к сохранению порядка элементов. Рассмотрим два основных подхода для массива типа int.

1. Удаление без сохранения порядка (O(1)): Если порядок не важен, самый эффективный способ — заменить удаляемый элемент последним элементом массива и уменьшить его логический размер.

// arr - указатель на массив, size - ссылка на его текущий размер, index - индекс удаляемого элемента
void removeElementFast(int* arr, int& size, int index) {
    if (index < 0 || index >= size) return; // Проверка валидности индекса
    // Копируем последний элемент на место удаляемого
    arr[index] = arr[size - 1];
    size--; // "Удаляем" последний элемент, уменьшая размер
}

2. Удаление с сохранением порядка (O(n)): Если порядок элементов должен остаться неизменным, необходимо сдвинуть все элементы, следующие за удаляемым, на одну позицию влево.

void removeElementOrdered(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(1)), когда структура данных представляет собой множество, и порядок не имеет значения.
• Использую метод с сохранением порядка (O(n)), когда массив представляет собой упорядоченную последовательность (например, историю операций), и этот порядок критичен для логики приложения. В реальных проектах на C++ для таких задач обычно используется std::vector и его метод erase, который внутри выполняет подобный сдвиг.