Desafio C++

Invalidação de iteradores e remoção segura

Enunciado

Escreva uma função que receba um std::vector<int> e remova todos os números pares usando iteradores. Como a remoção pode invalidar iteradores, utilize a técnica de erase-remove idiom com std::remove_if e erase. Depois, imprima o vetor resultante. Em seguida, mostre um exemplo de invalidação: crie um iterador para o primeiro elemento, faça push_back e explique por que o iterador pode ter sido invalidado (comente no código).

Requisitos

  • Usar std::remove_if com uma lambda que retorna true para números pares.
  • Chamar erase com o iterador retornado e end() para remover os elementos.
  • Imprimir o vetor após a remoção, separado por espaço.
  • Incluir um comentário explicando que push_back pode invalidar iteradores.

Código inicial

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // Seu código aqui
    return 0;
}

Saída esperada

1 3 5 7 9
Ver dica

O erase-remove idiom consiste em v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()). A lambda deve retornar true para números pares.

Mostrar solução 
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Remove todos os números pares usando erase-remove idiom
    v.erase(
        std::remove_if(v.begin(), v.end(), [](int n) { return n % 2 == 0; }),
        v.end()
    );

    // Imprime o vetor resultante
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    // Exemplo de invalidação de iterador
    auto it = v.begin();  // iterador para o primeiro elemento
    v.push_back(11);      // pode realocar o vetor e invalidar 'it'
    // Após push_back, 'it' pode estar inválido. Não use *it aqui!
    // Para continuar, obtenha um novo iterador: v.begin()

    return 0;
}

Passo a passo

  1. Criamos um std::vector<int> com valores de 1 a 10.
  2. Chamamos std::remove_if passando v.begin(), v.end() e uma lambda que retorna true para números pares (n % 2 == 0).
  3. std::remove_if reorganiza os elementos, movendo os ímpares para o início e retornando um iterador para a nova posição "lógica" do fim.
  4. Em seguida, v.erase remove fisicamente os elementos desde esse iterador até v.end(), ajustando o tamanho do vetor.
  5. Imprimimos o vetor resultante com um laço que usa iteradores.
  6. Depois, criamos um iterador it para o primeiro elemento e chamamos v.push_back(11). Comentamos que essa operação pode realocar o vetor e invalidar it.

Por que funciona

O erase-remove idiom é a maneira correta de remover elementos de um contêiner sequencial sem invalidar iteradores durante a remoção. std::remove_if apenas move os elementos que não satisfazem o predicado para o início, sem alterar o tamanho. O erase então remove a parte indesejada. Já o exemplo de invalidação mostra que operações que modificam o tamanho podem realocar a memória, tornando iteradores antigos inválidos — um conceito crucial para evitar bugs.

Erros comuns

  • Tentar remover elementos com erase dentro de um laço: por exemplo, for (auto it = v.begin(); it != v.end(); ++it) { if (*it % 2 == 0) v.erase(it); } invalida it e causa comportamento indefinido. Use o erase-remove idiom.
  • Usar std::remove_if e esquecer o erase: o vetor mantém o mesmo tamanho, com elementos duplicados no final. O erase é essencial.
  • Desreferenciar iterador após push_back: como mostrado, *it após push_back pode acessar memória liberada. Sempre obtenha um novo iterador após operações que podem realocar.

Outra forma de resolver

Se precisar remover elementos enquanto percorre e a ordem não importa, pode-se usar std::remove_if com um contêiner como std::list, que não invalida iteradores para elementos não removidos, permitindo remoção direta com erase. Porém, para std::vector, o erase-remove idiom é a solução padrão.

Saída esperada

1 3 5 7 9