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

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

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

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

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

Однако, если порядок элементов в векторе не важен, можно удалить элемент за константное время O(1). Это достигается путем замены удаляемого элемента последним элементом вектора и уменьшения размера вектора на единицу. Такой подход позволяет избежать сдвига элементов.

Рассмотрим пример:

#include <iostream>
#include <vector>
​
int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50}; // Инициализация вектора с элементами
​
    int indexToRemove = 2; // Индекс элемента, который нужно удалить (в данном случае элемент '30')
​
    // Замена элемента, который нужно удалить, последним элементом вектора
    vec[indexToRemove] = vec.back();
    // Уменьшение размера вектора на единицу
    vec.pop_back();
​
    // Вывод элементов вектора после удаления
    for (int num : vec) {
        std::cout << num << " ";
    }
    // Ожидаемый вывод: 10 20 50 40
​
    return 0;
}

1. #include <iostream> и #include <vector>: Подключение необходимых заголовочных файлов для работы с потоками ввода-вывода и вектором.

2. std::vector<int> vec = {10, 20, 30, 40, 50};: Создание и инициализация вектора vec с пятью элементами.

3. int indexToRemove = 2;: Указание индекса элемента, который нужно удалить. В данном случае это элемент с индексом 2, то есть число 30.

4. vec[indexToRemove] = vec.back();: Замена элемента, который нужно удалить, последним элементом вектора. Метод back() возвращает ссылку на последний элемент вектора.

5. vec.pop_back();: Удаление последнего элемента вектора, что уменьшает его размер на единицу.

6. Цикл for (int num : vec): Перебор всех элементов вектора и вывод их на экран. После удаления элемент 30 заменяется на 50, и вектор становится {10, 20, 50, 40}.

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