Pop_back() realmente invalida *todos* os iteradores em um std::vector?

Question

std::vector<int> ints;

// ... fill ints with random values

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}

Este código não está funcionando porque quando pop_back() é chamado, it é invalidado.Mas não encontro nenhum documento falando sobre invalidação de iteradores em std::vector::pop_back().

Você tem alguns links sobre isso?

Answer 1

A chamada para pop_back() remove o último elemento do vetor e, portanto, o iterador desse elemento é invalidado.O pop_back() chamada faz não invalidar iteradores para itens antes do último elemento, somente a realocação fará isso.Da "Referência da Biblioteca Padrão C++" de Josuttis:

A inserção ou remoção de elementos invalida referências, ponteiros e iteradores que se referem ao seguinte elemento.Se uma inserção causar realocação, ela invalida todas as referências, iteradores e ponteiros.

Answer 2

Aqui está sua resposta, diretamente do The Holy Standard:

23.2.4.2 Um vetor satisfaz todos os requisitos de um contêiner e de um contêiner reversível (dados em duas tabelas em 23.1) e de uma sequência, incluindo a maioria dos requisitos opcionais de sequência (23.1.1).

23.1.1.12 Tabela 68 ExpressionA.pop_back () Retorno semântica operacional do Typevoida.apagar(--a.end())vetor de contêiner, lista, deque

Observe que a.pop_back é equivalente a a.erase(--a.end()).Observando as especificidades do vetor ao apagar:

23.2.4.3.3 - apagamento do iterador (posição do iterador) - efeitos - Invalida todos os iteradores e referências após o ponto de apagamento

Portanto, depois de chamar pop_back, quaisquer iteradores para o elemento anteriormente final (que agora não existe mais) serão invalidados.

Olhando para o seu código, o problema é que quando você remove o elemento final e a lista fica vazia, você ainda o incrementa e sai do final da lista.

Answer 3

(Eu uso o esquema de numeração usado no rascunho de trabalho do C++ 0x, disponível aqui

A Tabela 94 na página 732 diz que pop_back (se existir em um contêiner de sequência) tem o seguinte efeito:

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); } 

23.1.1, ponto 12 afirma que:

Salvo indicação em contrário (explicitamente ou definindo uma função em termos de outras funções), invocando uma função de membro do contêiner ou passando um contêiner como um argumento para uma função da biblioteca não deve invalidar iteradores para ou alterar os valores de, objetos dentro desse contêiner .

Tanto acessar end() quanto aplicar prefixo-- não tem esse efeito, mas erase():

23.2.6.4 (relativo a vector.erase() ponto 4):

Efeitos:Invalida iteradores e referências no ponto de apagamento ou após ele.

Então, em conclusão:pop_back() invalidará apenas um iterador para o último elemento, de acordo com o padrão.

Answer 4

Aqui está uma citação da documentação STL da SGI (http://www.sgi.com/tech/stl/Vector.html):

[5] Os iteradores de um vetor são invalidados quando sua memória é realocada.Além disso, inserir ou excluir um elemento no meio de um vetor invalida todos os iteradores que apontam para elementos após o ponto de inserção ou exclusão.Segue-se que você pode evitar que os iteradores de um vetor sejam invalidados se você usar reserve() para pré-alocar tanta memória quanto o vetor usará e se todas as inserções e exclusões estiverem no final do vetor.

Acho que pop_back invalida apenas o iterador apontando para o último elemento e o iterador end().Nós realmente precisamos ver os dados nos quais o código falha, bem como a maneira como ele falha para decidir o que está acontecendo.Pelo que eu sei, o código deve funcionar - o problema usual nesse código é que a remoção do elemento e do ++ no iterador acontece na mesma iteração, como @mikhaild aponta.No entanto, neste código não é o caso:it++ não acontece quando pop_back é chamado.

Algo ruim ainda pode acontecer quando estiver apontando para o último elemento e o último elemento for menor que 10.Estamos agora comparando um invalidado isso e fim().Ainda pode funcionar, mas nenhuma garantia pode ser dada.

Answer 5

Os iteradores só são invalidados na realocação de armazenamento.Google é seu amigo: ver nota de rodapé 5.

Seu código não está funcionando por outros motivos.

Answer 6

pop_back() invalida apenas iteradores que apontam para o último elemento.Da referência da biblioteca padrão C++:

A inserção ou remoção de elementos invalida referências, ponteiros e iteradores que se referem ao seguinte elemento.Se uma inserção causar realocação, ela invalida todas as referências, iteradores e ponteiros.

Então, para responder à sua pergunta, não, isso não invalida todos iteradores.

No entanto, no seu exemplo de código, isso pode invalidar it quando está apontando para o último elemento e o valor está abaixo de 10.Nesse caso, o STL de depuração do Visual Studio marcará o iterador como invalidado e a verificação adicional de que ele não é igual a end() mostrará uma afirmação.

Se os iteradores forem implementados como ponteiros puros (como provavelmente aconteceriam em todos os casos de vetores STL não depurados), seu código deverá funcionar.Se os iteradores forem mais que ponteiros, então seu código não lida com esse caso de remoção correta do último elemento.

Answer 7

O erro é que quando "it" aponta para o último elemento do vetor e se este elemento for menor que 10, este último elemento é removido.E agora "it" aponta para ints.end(), em seguida "it++" move o ponteiro para ints.end()+1, então agora "it" foge de ints.end(), e você tem um loop infinito varrendo todos os seus memória :).

Answer 8

A "especificação oficial" é o padrão C++.Se você não tiver acesso a uma cópia do C++03, poderá obter o rascunho mais recente do C++0x no site do Comitê: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

A seção "Semântica Operacional" dos requisitos do contêiner especifica que pop_back() é equivalente a { iterator i = end();--eu;apagar (eu);}.a seção [vector.modifiers] para apagar diz "Efeitos:Invalida iteradores e referências no ponto de apagamento ou após ele."

Se você quiser o argumento da intuição, pop_back não falha (já que a destruição de value_types em contêineres padrão não tem permissão para lançar exceções), portanto, ele não pode fazer nenhuma cópia ou alocação (já que eles podem lançar), o que significa que você pode adivinhar que o iterador para o elemento apagado e o iterador final são invalidados, mas o restante não.

Answer 9

pop_back() apenas invalidará isto se isto estava apontando para o último item do vetor.Portanto, seu código falhará sempre que o último int do vetor for menor que 10, como segue:

*it = ints.back();// Defina *it com o valor que já possui
ints.pop_back();//Invalida o iterador
continuar;// Faça um loop e acesse o iterador inválido

Answer 10

Você pode querer considerar o uso do valor de retorno de erase em vez de trocar o elemento back para a posição excluída e retornar.Para sequências, apagar retorna um iterador apontando o elemento além do elemento que está sendo excluído.Observe que este método pode causar mais cópias do que o algoritmo original.

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std::remove_if também poderia ser uma solução alternativa.

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std::remove_if é (como meu primeiro algoritmo) estável, portanto pode não ser a maneira mais eficiente de fazer isso, mas é sucinto.

Answer 11

Confira as informações aqui (cplusplus.com):

Excluir último elemento

Remove o último elemento do vetor, reduzindo efetivamente o tamanho do vetor em um e invalidando todos os iteradores e referências a ele.