O redimensionamento de um vetor invalida os iteradores?

Eu achei que este código C ++:

vector a; a.push_back(1); a.push_back(2); vector::iterator it = a.begin(); a.push_back(4); cout << *it; 

imprima algum grande número random; mas se você adicionar a.push_back(3) entre as linhas 3 e 4, ele irá imprimir 1. Você pode me explicar?

Editado com uma redação mais cuidadosa

Sim, resize um vetor pode invalidar todos os iteradores que apontam para o vetor.

O vetor é implementado alocando internamente uma matriz onde os dados são armazenados. Quando o vetor cresce, esse array pode ficar sem espaço, e quando isso ocorre, o vetor aloca um array novo, maior, copia os dados para ele e, em seguida, exclui o array antigo.

Portanto, seus iteradores antigos, que apontam para a memory antiga, não são mais válidos. Se o vetor é redimensionado para baixo (por exemplo, por pop_back() ), no entanto, a mesma matriz é usada. A matriz nunca é reduzida automaticamente.

Uma maneira de evitar essa realocação (e invalidação de ponteiro) é chamar vector::reserve() primeiro, para reservar espaço suficiente para que essa cópia não seja necessária. No seu caso, se você chamou a.reserve(3) antes da primeira operação push_back() , a matriz interna seria grande o suficiente para que o push_back pudesse ser executado sem ter que realocar a matriz e, assim, seus iteradores permaneceriam válido.

Os iteradores vetoriais são invalidados somente quando o vetor executa uma realocação.

A chamada para push_back(4) está fazendo com que o vetor aloque um novo bloco de memory – isso é o que faz com que seu iterador se torne inválido. Quando você também usa push_back(3) , nenhuma realocação é executada para push_back(4) para que o iterador permaneça válido.

Sim, qualquer ação que possa alterar o tamanho do vetor pode invalidar os iteradores.

Edit: Isso inclui operações (por exemplo, erase() , resize() ) que reduzem o tamanho do contêiner. erase() não invalida todos os iteradores, mas invalida todos os iteradores que se referem a algum ponto após o (s) elemento (s) apagado (s). resize() é definido em termos de insert() e erase() , então tem o mesmo potencial.

As regras para invalidação do iterador são específicas de um contêiner.

Agora invalidação pode ter dois significados com um vetor:

  1. Invalidação = ponto fora do intervalo definido por [begin, end]
  2. Invalidação = aponta para um object diferente do original

Como você pode ver, o segundo é muito mais estrito:

 std::vector myVector; myVector.push_back(0); myVector.push_back(1); std::vector::iterator it = myVector.begin(); // it points to 0 myVector.erase(it); // it points to 1 myVector.erase(it); // it == myVector.end() 

Neste caso, é ‘válido’, pois está sempre no intervalo inclusivo [begin, end] e, portanto, pode ser usado com segurança para qualquer operação no myVector. Por outro lado a expressão (* it) continua mudando: primeiro retorna 0, depois 1, então tem comportamento indefinido …

Em geral, as pessoas preferem falar sobre o segundo requisito, e invalidar um iterador significa simplesmente que (* ele) pode não produzir o mesmo resultado de antes.


Agora que isso é dito, há várias maneiras de invalidar um iterador em um Vetor (na verdade, é a estrutura menos estável do STL).

Durante adições de elementos:

  • Isso pode desencadear uma realocação (1) se myVector.size () == myVector.capacity (), uma vez que a verificação é propensa a erros, geralmente consideramos que qualquer adição invalida os iteradores
  • Se você quer ser “exigente” e sabe que a realocação não é acionada, então você ainda precisa se preocupar em insert . Inserir um elemento invalida os iteradores que apontam para esta posição atual e todos os subsequentes, uma vez que os elementos são deslocados um passo para o final do vetor.

Durante a remoção de elementos:

  • Não há realocação, mesmo que o buffer seja agora muito maior do que o necessário. É possível forçar isso, usando o termo de contração para se adaptar à linguagem (2).
  • Todos os iteradores que apontam para o elemento removido são invalidados. Especialmente, o iterador ‘end’ anterior está agora além do intervalo [begin, end] e não pode ser usado com segurança nos algoritmos STL, por exemplo.

(1) A estrutura interna de um std :: vector é uma matriz de T, isto é devido à compatibilidade com os programas-C (usando & myVector.front () como o endereço da matriz) e porque garante contiguidade e um mínimo sobrecarga de espaço (ou seja, a quantidade de espaço ocupada pelos dados do próprio vetor versus a quantidade de espaço ocupada por um object)

A qualquer momento, você pode saber quantos objects um vetor pode conter usando o método .capacity ().

Quando você deseja inserir um object e o vetor não possui a capacidade necessária, uma chamada para o método .reserve (size_t) é acionada. Esse método, se o número de itens necessários for superior à capacidade atual, acionará uma realocação .

O vetor então aloca uma nova matriz de elementos (seu tamanho é geralmente 2 * n + 1 onde n é a capacidade atual), copia os elementos da matriz atual para a nova matriz, descarta a matriz atual.

Como ele descarta a matriz atual, seus iteradores são invalidados, pois os iteradores vetoriais geralmente são pointers simples (para eficiência).

Observe que, se os iteradores foram implementados como: uma referência ao vetor + uma contagem, e a desreferência era, na verdade, * (& m_vector.front () + n), a realocação não os invalidaria … mas eles seriam menos eficientes.

(2) Encolher para caber: Aviso, isso aciona uma cópia dos elementos e invalida iteradores.

 // myVector has 10 elements, but myVector.capacity() == 1000 myVector.swap(std::vector(myVector)); 

Primeiro, ele cria um vetor temporário, que aloca apenas a quantidade de memory necessária (com um mínimo dependendo da biblioteca) e copia os elementos do myVector. Em seguida, a operação de troca troca os buffers do myVector e desta cópia, e assim o myVector agora armazena um buffer com a quantidade mínima de memory necessária. No final da operação, o temporário é destruído e a memory retida é liberada.

Para referência futura, todos os tipos de informações do STL como este estão no site da SGI: http://www.sgi.com/tech/stl/Vector.html

Se você precisar que os iteradores permaneçam válidos depois de adicionar ou excluir uma coleção, dê uma olhada em outro tipo de coleção, como uma lista.

A melhor coisa a fazer, porém, é identificar a matriz de características que você deseja de uma coleção (access random, etc.) e, em seguida, escolher o container correto.

Veja o artigo da Wikipédia sobre Contêineres Standard_Template_Library para um ponto de partida. Se você tiver o dinheiro, eu recomendo o “Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library” de Scott Meyer.

Desculpas por falta de links de apoio, sou novato aqui e não tenho a reputação de publicá-lo com mais de um.