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

1️⃣ Как кратко ответить

Для оптимального удаления элемента из массива без использования STL необходимо вручную сдвинуть все элементы, находящиеся справа от удаляемого, на одну позицию влево. Это позволяет избежать создания нового массива и минимизировать количество операций. Время выполнения операции — O(n), где n — количество элементов после удаляемого.

2️⃣ Подробное объяснение темы

Удаление элемента из массива в C++ без использования стандартной библиотеки (STL) требует понимания того, как массивы работают на низком уровне. Массивы в C++ — это последовательные блоки памяти, и их размер фиксирован после создания. Это значит, что мы не можем просто "удалить" элемент, как в динамических структурах данных, таких как векторы. Вместо этого мы должны сдвинуть элементы, чтобы заполнить "пустое" место.

Пример

Рассмотрим массив целых чисел и задачу удаления элемента по индексу.

#include <iostream>
​
void removeElement(int arr[], int& size, int index) {
    // Проверка на корректность индекса
    if (index < 0 || index >= size) {
        std::cerr << "Invalid index" << std::endl;
        return;
    }
​
    // Сдвиг элементов влево, начиная с индекса
    for (int i = index; i < size - 1; ++i) {
        arr[i] = arr[i + 1];
    }
​
    // Уменьшение размера массива
    --size;
}
​
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = 5;
​
    int indexToRemove = 2; // Удаляем элемент с индексом 2 (значение 3)
​
    removeElement(arr, size, indexToRemove);
​
    // Вывод массива после удаления
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
​
    return 0;
}

Объяснение кода

1. Функция removeElement:

   • Принимает массив arr, его текущий размер size и индекс index элемента, который нужно удалить.
   • Проверяет, находится ли индекс в допустимом диапазоне. Если нет, выводит сообщение об ошибке и завершает выполнение функции.

2. Сдвиг элементов:

   • Цикл for начинается с удаляемого индекса и продолжается до предпоследнего элемента массива.
   • Каждый элемент массива сдвигается на одну позицию влево, заменяя собой предыдущий элемент.

3. Уменьшение размера:

   • После сдвига уменьшается переменная size, чтобы отразить новый размер массива.

4. Функция main:

   • Создает массив arr и задает его начальный размер size.
   • Вызывает removeElement, чтобы удалить элемент с заданным индексом.
   • Выводит обновленный массив.

Зачем это нужно

Удаление элемента из массива без использования STL может быть полезно в системах с ограниченными ресурсами, где использование динамических структур данных нежелательно. Это также помогает лучше понять, как работают массивы на низком уровне и как управлять памятью вручную.