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
- N4950 — Working Draft, Standard for Programming Language C++
- Container requirements [container.reqmts]
- Find [alg.find]
- Iterator requirements, general [iterator.requirements.general]
- Vector capacity [vector.capacity]
- Vector modifiers [vector.modifiers]
- Sequence container requirements [sequence.reqmts]
- Partial class template specialization vector<bool, Allocator> [vector.bool.pspc]