Quais algoritmos são utilizados na remoção de um elemento de std::vector e qual a complexidade temporal que isso implica?

Ao remover um elemento de std::vector, é utilizado um algoritmo que desloca todos os elementos seguintes ao elemento removido uma posição para a esquerda para preencher o espaço vazio. Isto deve-se ao fato de que std::vector armazena os elementos num bloco de memória contíguo.

A complexidade temporal de remover um elemento depende da sua posição:

• Se o último elemento for removido, a operação é realizada em O(1), pois o tamanho do vetor é simplesmente reduzido.
• Se um elemento no meio ou no início for removido, todos os elementos seguintes são deslocados, o que dá um pior caso de O(n), onde n é a quantidade de elementos após o removido.

Exemplo de remoção de um elemento por índice:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    int index_to_remove = 2; // remover o elemento com valor 3

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

    for (int x : v) {
        std::cout << x << ' ';
    }
    // Saída: 1 2 4 5
}