При удалении элемента из std::vector используется алгоритм сдвига всех элементов, следующих за удаляемым, на одну позицию влево, чтобы заполнить образовавшийся пробел. Это связано с тем, что std::vector хранит элементы в непрерывном блоке памяти.

Временная сложность удаления элемента зависит от позиции:

Если удаляется последний элемент, операция выполняется за O(1), так как просто уменьшается размер вектора.
Если удаляется элемент в середине или начале, все последующие элементы сдвигаются, что даёт O(n) в худшем случае, где n — количество элементов после удаляемого.

Пример удаления элемента по индексу:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int index_to_remove = 2; // удаляем элемент со значением 3

    v.erase(v.begin() + index_to_remove);

    for (int x : v) {
        std::cout << x << ' ';
    }
    // Вывод: 1 2 4 5
}

Какие алгоритмы применяются при удалении элемента из std::vector, и какую временную сложность это влечёт за собой?