Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

Invalidação de iteradores em C++: o caso de std::vector

Descobre quando uma alteração ao vetor invalida iteradores, referências e ponteiros, incluindo o iterador de fim, e como usar em segurança o resultado de std::find_if.

Versão: ISO C++23; implementation support may vary

Sintaxe

// ISO C++23; implementation support may vary
// For v of type const std::vector<int>& and a unary predicate pred:
auto it = std::find_if(v.begin(), v.end(), pred);
const int* result = (it == v.end()) ? nullptr : &*it;

Um iterador invalidado deixa de poder ser usado para percorrer o seu intervalo ou aceder a um elemento. As regras dependem do contentor e da operação. Não desreferencies, avances nem compares um iterador invalidado, nem sequer com um end() acabado de obter.

std::vector::begin() indica o primeiro elemento, e std::vector::end() indica a posição a seguir ao último. Num vetor vazio, são iguais. As sobrecargas const devolvem const_iterator; as restantes devolvem iterator. std::find_if, de <algorithm>, pesquisa no intervalo semiaberto [v.begin(), v.end()) e devolve o iterador da primeira correspondência ou o end() recebido. Verifica o resultado antes de o desreferenciares. Para const std::vector<int>&, &*it dá um ponteiro não proprietário const int*; se não houver correspondência, devolve nullptr. Não uses este padrão para obter o endereço de um elemento de std::vector<bool>. Como first_even recebe o vetor por referência const, aceita também um vetor temporário. Se lhe passares um vetor temporário diretamente, qualquer ponteiro não nulo devolvido fica pendente no fim da expressão completa que contém a chamada.

Uma realocação invalida todos os iteradores, referências e ponteiros para elementos, bem como o antigo end(). Quando reserve(n) termina com sucesso, há realocação se e só se n > capacity(), sem alteração de size(). Uma inserção sem realocação preserva os iteradores, referências e ponteiros estritamente anteriores ao ponto de inserção e invalida os que estão nesse ponto ou depois, incluindo o antigo end(). Assim, push_back sem realocação preserva o acesso aos elementos existentes, mas não o antigo end().

erase invalida os iteradores e referências a partir do ponto de remoção, incluindo o antigo end(). Não uses um ponteiro para o elemento removido para aceder à correspondência original. Para continuares a percorrer o vetor, usa o iterador devolvido por erase, que indica o elemento seguinte ou o novo end(). clear() destrói todos os elementos e invalida todos os iteradores, referências e ponteiros para esses elementos. Volta a obter end() após a chamada. Um const int* não prolonga o tempo de vida do elemento nem o protege de alterações ao vetor. Após uma operação que invalide o resultado, pesquisa novamente ou copia primeiro o valor, se só precisares dele.

Exemplos

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

const int* first_even(const std::vector<int>& v) {
    const auto it = std::find_if(v.begin(), v.end(),
                                 [](int x) { return x % 2 == 0; });
    return it == v.end() ? nullptr : &*it;
}

int main() {
    std::vector<int> v{1, 4, 7};
    v.reserve(4);

    {
        const int* p = first_even(v);
        if (!p) return 1;
        std::cout << *p << '\n';
        v.push_back(6);
        std::cout << *p << '\n';
    }

    v.erase(v.begin() + 1);
    if (const int* p = first_even(v)) {
        std::cout << *p << '\n';
    }

    v.clear();
    if (!first_even(v)) {
        std::cout << "no match\n";
    }
}

Resultado

4
4
6
no match

`reserve(4)` deixa espaço para acrescentar `6`: o ponteiro para `4` continua válido, mas o antigo `end()` não. Depois de remover `4`, uma nova pesquisa encontra `6`; depois de `clear()`, não há correspondência.

Lições relacionadas

  • C++ · Lição 10 · Avançado · Versão: 3

Fontes