Regras de invalidação do iterador

543

Quais são as regras de invalidação do iterador para contêineres C ++?

De preferência em um formato de lista resumida.

(Observação: isso deve ser uma entrada para as Perguntas frequentes sobre C ++ do Stack Overflow . Se você quiser criticar a idéia de fornecer uma FAQ neste formulário, a postagem na meta que iniciou tudo isso seria o lugar para isso. essa pergunta é monitorada na sala de bate-papo do C ++ , onde a ideia das Perguntas frequentes começou em primeiro lugar; portanto, é muito provável que sua resposta seja lida por quem a teve.)

Raças de leveza em órbita
fonte
As respostas devem estar no mesmo formato que a sua resposta?
PW
@PW IMO que seria preferido por simetria, mas não posso aplicá-la: P
Lightness Races in Orbit
e quanto a c ++ 20?
Walter
1
@Walter Ainda não existe;)
Lightness Races in Orbit
Esta questão é, para citar Leela de Futurama, de épocas estúpidas, e na minha modesta opinião deveria ser deixada em aberto.
Roman Luštrik

Respostas:

112

C ++ 17 (Todas as referências são do rascunho final do trabalho da CPP17 - n4659 )


Inserção

Contêineres de sequência

  • vector: As funções insert, emplace_back, emplace, push_backcausa realocação se o novo tamanho é maior do que a capacidade de idade. A realocação invalida todas as referências, ponteiros e iteradores que se referem aos elementos na sequência. Se nenhuma realocação acontecer, todos os iteradores e referências antes do ponto de inserção permanecerão válidos. [26.3.11.5/1]
    Com relação à reservefunção, a realocação invalida todas as referências, ponteiros e iteradores que se referem aos elementos na sequência. Nenhuma realocação deve ocorrer durante as inserções que ocorrem após uma chamada reserve()até o momento em que uma inserção tornaria o tamanho do vetor maior que o valor de capacity(). [26.3.11.3/6]

  • deque: Uma inserção no meio do deque invalida todos os iteradores e referências a elementos do deque. Uma inserção em cada extremidade do deque invalida todos os iteradores para o deque, mas não afeta a validade das referências a elementos do deque. [26.3.8.4/1]

  • list: Não afeta a validade dos iteradores e referências. Se uma exceção for lançada, não haverá efeitos. [26.3.10.4/1].
    A insert, emplace_front, emplace_back, emplace, push_front, push_backfunções são cobertos por esta regra.

  • forward_list: Nenhuma das sobrecargas de insert_afterdeve afetar a validade dos iteradores e referências [26.3.9.5/1]

  • array: Como regra , os iteradores para uma matriz nunca são invalidados durante toda a vida útil da matriz. Deve-se observar, no entanto, que durante a troca, o iterador continuará apontando para o mesmo elemento da matriz e, portanto, alterará seu valor.

Contentores Associativos

  • All Associative Containers: Os membros inserte emplacenão devem afetar a validade dos iteradores e referências ao contêiner [26.2.6 / 9]

Contêineres associativos não ordenados

  • All Unordered Associative Containers: Rehashing invalida os iteradores, altera a ordem entre os elementos e as alterações nas quais elementos de buckets aparecem, mas não invalida ponteiros ou referências a elementos. [26.2.7 / 9]
    Os membros inserte emplacenão devem afetar a validade das referências aos elementos do contêiner, mas podem invalidar todos os iteradores do contêiner. [26.2.7 / 14]
    O inserte emplacemembros não afecta a validade da iterators se (N+n) <= z * B, onde Né o número de elementos no recipiente, antes da operação de inserção, né o número de elementos inseridos, Bé contagem balde do recipiente, e zé a fator de carga máxima do contêiner. [26.2.7 / 15]

  • All Unordered Associative Containers: No caso de uma operação de mesclagem (por exemplo, a.merge(a2)), os iteradores referentes aos elementos transferidos e todos os iteradores referentes aserão invalidados, mas os iteradores dos elementos restantes a2permanecerão válidos. (Tabela 91 - Requisitos de contêiner associativo não ordenado)

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Erasure

Contêineres de sequência

  • vector: As funções erasee pop_backinvalidam iteradores e referências no ponto ou após o apagamento. [26.3.11.5/3]

  • deque: Uma operação de exclusão que apaga o último elemento de um dequeinvalida apenas o iterador passado e todos os iteradores e referências aos elementos apagados. Uma operação de exclusão que apaga o primeiro elemento de um, dequemas não o último, invalida apenas iteradores e referências aos elementos apagados. Uma operação de exclusão que apaga nem o primeiro elemento nem o último elemento de a dequeinvalida o iterador passado-final e todos os iteradores e referências a todos os elementos do deque. [Nota: pop_fronte pop_backsão operações de apagamento. - nota final] [26.3.8.4/4]

  • list: Invalida apenas os iteradores e referências aos elementos apagados. [26.3.10.4/3]. Isto aplica-se erase, pop_front, pop_back, clearfunções.
    removee remove_iffunções-membro: Apaga todos os elementos da lista referidos por um iterador de lista ipara os quais as seguintes condições são válidas: *i == value, pred(*i) != false. Invalida apenas os iteradores e referências aos elementos apagados [26.3.10.5/15].
    uniquefunção de membro - Apaga tudo, exceto o primeiro elemento de cada grupo consecutivo de elementos iguais referido pelo iterador ino intervalo (para a versão de unique com um argumento predicado). Invalida apenas os iteradores e referências aos elementos apagados. [26.3.10.5/19][first + 1, last) para o qual *i == *(i-1)(para a versão de exclusivo sem argumentos) oupred(*i, *(i - 1))

  • forward_list: erase_afterinvalidará apenas iteradores e referências aos elementos apagados. [26.3.9.5/1].
    removee remove_iffunções-membro - Apaga todos os elementos na lista referidos por um iterador de lista i, para o qual as seguintes condições são válidas: *i == value(for remove()), pred(*i)é verdadeiro (for remove_if()). Invalida apenas os iteradores e referências aos elementos apagados. [26.3.9.6/12].
    uniquefunção membro - Apaga tudo, exceto o primeiro elemento, de cada grupo consecutivo de elementos iguais referido pelo iterador i no intervalo [primeiro + 1, último) para o qual *i == *(i-1)(para a versão sem argumentos) ou pred(*i, *(i - 1))(para a versão com predicado) argumento) é válido. Invalida apenas os iteradores e referências aos elementos apagados. [26.3.9.6/16]

  • All Sequence Containers: clearinvalida todas as referências, ponteiros e iteradores que se referem aos elementos de a e pode invalidar o iterador passado-final (Tabela 87 - Requisitos do contêiner de sequência). Mas para forward_list, clearnão invalida os iteradores do passado. [26.3.9.5/32]

  • All Sequence Containers: assigninvalida todas as referências, ponteiros e iteradores referentes aos elementos do contêiner. Para vectore deque, também invalida o iterador passado. (Tabela 87 - Requisitos do contêiner de sequência)

Contentores Associativos

  • All Associative Containers: Os erasemembros invalidarão apenas iteradores e referências aos elementos apagados [26.2.6 / 9]

  • All Associative Containers: Os extractmembros invalidam apenas iteradores para o elemento removido; ponteiros e referências ao elemento removido permanecem válidos [26.2.6 / 10]

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Requisitos gerais de contêiner relacionados à invalidação do iterador:

  • A menos que seja especificado de outra forma (explicitamente ou definindo uma função em termos de outras funções), invocar uma função de membro de contêiner ou passar um contêiner como argumento para uma função de biblioteca não invalidará os iteradores para, ou alterará os valores de, objetos dentro desse contêiner . [26.2.1 / 12]

  • nenhuma swap()função invalida quaisquer referências, ponteiros ou iteradores referentes aos elementos dos contêineres que estão sendo trocados. [Nota: O iterador end () não se refere a nenhum elemento, portanto pode ser invalidado. - nota final] [26.2.1 / (11.6)]

Como exemplos dos requisitos acima:

  • transformalgoritmo: As funções ope binary_opnão devem invalidar iteradores ou subintervalos, nem modificar elementos nos intervalos [28.6.4 / 1]

  • accumulatealgoritmo: no intervalo [primeiro, último], binary_opnão deve modificar elementos nem invalidar iteradores ou subintervalos [29.8.2 / 1]

  • reducealgoritmo: binary_op não invalida iteradores ou subintervalos, nem modifica elementos no intervalo [primeiro, último]. [29.8.3 / 5]

e assim por diante...

PW
fonte
7
Oh PW seu herói!
Lightness Races em órbita
2
@LightnessRacesinOrbit: tentei fazê-lo de acordo com o formato de resposta original. :)
PW
1
podemos também ter uma lista para std::string? Eu acho que é diferente std::vectordevido à SSO
sp2danny
1
@ sp2danny: devido ao SSO, stringfalha no segundo requisito geral listado acima. Então eu não o incluí. Também tentei seguir o mesmo padrão das entradas anteriores da FAQ.
PW
@LightnessRaceswithMonica Obrigado a vocês pelo trabalho duro. Eu tenho uma pergunta me confundindo por dias. O que "invalidado" significa exatamente nesses contextos? Significa "invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element"como @Marshall Clow descrito nesta resposta ? Ou apenas indica apenas uma das duas condições?
Rick
410

C ++ 03 (fonte: regras de invalidação do iterador (C ++ 03) )


Inserção

Recipientes de sequência

  • vector: todos os iteradores e referências antes do ponto de inserção não são afetados, a menos que o novo tamanho do contêiner seja maior que a capacidade anterior (nesse caso, todos os iteradores e referências são invalidados) [23.2.4.3/1]
  • deque: todos os iteradores e referências são invalidados, a menos que o membro inserido esteja no final (frente ou verso) do deque (nesse caso, todos os iteradores são invalidados, mas as referências aos elementos não são afetadas) [23.2.1.3/1]
  • list: todos os iteradores e referências não afetados [23.2.2.3/1]

Contêineres associativos

  • [multi]{set,map}: todos os iteradores e referências não afetados [23.1.2 / 8]

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Erasure

Recipientes de sequência

  • vector: todos os iteradores e referências após o ponto de exclusão são invalidados [23.2.4.3/3]
  • deque: todos os iteradores e referências são invalidados, a menos que os membros apagados estejam no final (frente ou verso) do deque (nesse caso, apenas iteradores e referências aos membros apagados são invalidados) [23.2.1.3/4]
  • list: apenas os iteradores e referências ao elemento apagado são invalidados [23.2.2.3/3]

Contêineres associativos

  • [multi]{set,map}: apenas iteradores e referências aos elementos apagados são invalidados [23.1.2 / 8]

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Redimensionando

  • vector: conforme inserir / apagar [23.2.4.2/6]
  • deque: conforme inserir / apagar [23.2.1.2/1]
  • list: conforme inserir / apagar [23.2.2.2/1]

Nota 1

A menos que especificado de outra forma (explicitamente ou definindo uma função em termos de outras funções), invocar uma função de membro de contêiner ou transmitir um contêiner como argumento para uma função de biblioteca não invalidará os iteradores para, ou alterará os valores de, objetos dentro desse contêiner . [23.1 / 11]

Nota 2

Não está claro no C ++ 2003 se os iteradores "finais" estão sujeitos às regras acima ; de qualquer maneira, você deve assumir que eles são (como é o caso na prática).

Nota 3

As regras para invalidação de ponteiros são os mesmos que as regras para invalidação de referências.

Raças de leveza em órbita
fonte
5
Boa ideia, apenas para comentar: acho que os contêineres associativos podem ser dobrados juntos em uma única linha, e pode valer a pena acrescentar outra linha dos associativos não ordenados ... embora não tenha certeza de como a parte rehash mapeado ao inserir / apagar, você conhece uma maneira de verificar se uma repetição será acionada ou não?
precisa
1
IIRC, em algum lugar a especificação diz que o iterador final não é um iterador "para objetos dentro desse contêiner". Gostaria de saber como essas garantias procuram o iterador final em cada caso?
Johannes Schaub - litb 22/06
1
@MuhammadAnnaqeeb: Essa resposta, sem dúvida, não deixa claro, pois tomei um atalho, mas a intenção é dizer que o redimensionamento é inserção / apagamento, como se fosse necessária uma realocação, você pode considerar que é o mesmo que apagar depois reinsira todos os elementos afetados. Essa seção da resposta certamente poderia ser melhorada.
Lightness Races in Orbit
1
@Yakk: Mas não; veja o texto padrão citado. Parece que isso foi corrigido no C ++ 11. :)
Lightness Races in Orbit
1
@metamorphosis: o deque armazena dados em blocos não contíguos. A inserção no início ou no final pode alocar um novo bloco, mas nunca se move pelos elementos anteriores, portanto, os ponteiros permanecem válidos. Mas as regras para ir para o elemento próximo / anterior mudam se um novo bloco for alocado, portanto, os iteradores são invalidados.
Nick Matteo
357

C ++ 11 (fonte: regras de invalidação do iterador (C ++ 0x) )


Inserção

Recipientes de sequência

  • vector: todos os iteradores e referências antes do ponto de inserção não são afetados, a menos que o novo tamanho do contêiner seja maior que a capacidade anterior (nesse caso, todos os iteradores e referências são invalidados) [23.3.6.5/1]
  • deque: todos os iteradores e referências são invalidados, a menos que o membro inserido esteja no final (frente ou verso) do deque (nesse caso, todos os iteradores são invalidados, mas as referências aos elementos não são afetadas) [23.3.3.4/1]
  • list: todos os iteradores e referências não afetados [23.3.5.4/1]
  • forward_list: todos os iteradores e referências não afetados (se aplica a insert_after) [23.3.4.5/1]
  • array: (n / a)

Contêineres associativos

  • [multi]{set,map}: todos os iteradores e referências não afetados [23.2.4 / 9]

Contêineres associativos não classificados

  • unordered_[multi]{set,map}: todos os iteradores são invalidados quando ocorre a repetição, mas as referências não são afetadas [23.2.5 / 8]. A rehashing não ocorre se a inserção não fizer com que o tamanho do contêiner exceda z * Bonde zestá o fator de carga máximo e Bo número atual de caçambas. [23.2.5 / 14]

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Erasure

Recipientes de sequência

  • vector: todo iterador e referência no ou após o ponto de exclusão são invalidados [23.3.6.5/3]
  • deque: apagar o último elemento invalida apenas os iteradores e as referências aos elementos apagados e ao iterador passado-final; apagar o primeiro elemento invalida apenas iteradores e referências aos elementos apagados; apagar qualquer outro elemento invalida todos os iteradores e referências (incluindo o iterador passado) [23.3.3.4/4]
  • list: apenas os iteradores e referências ao elemento apagado são invalidados [23.3.5.4/3]
  • forward_list: apenas os iteradores e referências ao elemento apagado são invalidados (aplica-se a erase_after) [23.3.4.5/1]
  • array: (n / a)

Contêineres associativos

  • [multi]{set,map}: apenas iteradores e referências aos elementos apagados são invalidados [23.2.4 / 9]

Contêineres associativos não ordenados

  • unordered_[multi]{set,map}: apenas iteradores e referências aos elementos apagados são invalidados [23.2.5 / 13]

Adaptadores de contêiner

  • stack: herdado do contêiner subjacente
  • queue: herdado do contêiner subjacente
  • priority_queue: herdado do contêiner subjacente

Redimensionando

  • vector: conforme inserir / apagar [23.3.6.5/12]
  • deque: conforme inserir / apagar [23.3.3.3/3]
  • list: conforme inserir / apagar [23.3.5.3/1]
  • forward_list: conforme inserir / apagar [23.3.4.5/25]
  • array: (n / D)

Nota 1

A menos que seja especificado de outra forma (explicitamente ou definindo uma função em termos de outras funções), invocar uma função de membro de contêiner ou passar um contêiner como argumento para uma função de biblioteca não invalidará os iteradores para, ou alterará os valores de, objetos dentro desse contêiner . [23.2.1 / 11]

Nota 2

nenhuma função swap () invalida quaisquer referências, ponteiros ou iteradores referentes aos elementos dos contêineres que estão sendo trocados. [Nota: O iterador end () não se refere a nenhum elemento, portanto pode ser invalidado . - nota final [23.2.1 / 10]

Nota 3

Além da ressalva acima swap(), não está claro se os iteradores "finais" estão sujeitos às regras por contêiner listadas acima ; você deve assumir, de qualquer maneira, que são.

Nota 4

vectore todos os contêineres associativos não ordenados suportam, reserve(n)garantindo que nenhum redimensionamento automático ocorra pelo menos até que o tamanho do contêiner aumente n. Deve-se tomar cuidado com contêineres associativos não ordenados, porque uma proposta futura permitirá a especificação de um fator de carga mínimo, o que permitiria a repetição de tarefas insertapós eraseoperações suficientes reduzir o tamanho do contêiner abaixo do mínimo; a garantia deve ser considerada potencialmente nula após um erase.

Raças de leveza em órbita
fonte
Além disso swap(), quais são as regras para a validade do iterador na atribuição de copiar / mover?
21814
@LightnessRacesinOrbit: como inserção, apagamento, redimensionamento e troca, atribuição de copiar / mover também são funções-membro do std :: vector, então acho que você também poderia fornecer as regras de validade do iterador.
21814
@ goodbyeera: Você quer dizer copiar / mover atribuir um elemento? Isso não afetará nenhum iterador. Por quê? Você está atingindo a nota 1 acima.
Lightness Races em órbita
1
Acho que cometi um erro, porque std::basic_stringnão parece ser contado como um contêiner e, certamente, não é um contêiner na seção do padrão a que a nota se aplica. Ainda assim, onde diz que o SSO não é permitido (eu sei que o COW é)?
Deduplicator
2
Essas regras são iguais no C ++ 14? C ++ 17 (tanto quanto se sabe agora)?
einpoklum
40

É provavelmente vale a pena acrescentar que um iterador inserção de qualquer tipo ( std::back_insert_iterator, std::front_insert_iterator,std::insert_iterator ) é garantido para permanecer válido, desde que todas as inserções são realizadas através deste iterador e nenhum outro evento de invalidação iterador independente ocorre.

Por exemplo, quando você está executando uma série de operações de inserção em um std::vectorusandostd::insert_iterator , é bem possível que essas inserções acionem a realocação de vetores, o que invalidará todos os iteradores que "apontam" para esse vetor. No entanto, o iterador de inserção em questão é garantido para permanecer válido, ou seja, você pode continuar com segurança a sequência de inserções. Não há necessidade de se preocupar em acionar a realocação de vetores.

Isso, novamente, se aplica apenas às inserções executadas pelo próprio iterador de inserção. Se o evento de invalidação do iterador for acionado por alguma ação independente no contêiner, o iterador de inserção também será invalidado de acordo com as regras gerais.

Por exemplo, este código

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

é garantido para executar uma sequência válida de inserções no vetor, mesmo se o vetor "decidir" realocar em algum lugar no meio desse processo. O iterador itobviamente ficará inválido, mas it_inscontinuará válido.

Formiga
fonte
22

Como essa pergunta atrai tantos votos e se torna um FAQ, acho que seria melhor escrever uma resposta separada para mencionar uma diferença significativa entre C ++ 03 e C ++ 11 em relação ao impacto da std::vectoroperação de inserção no validade de iteradores e referências com relação a reserve()e capacity(), que a resposta mais upvoted não aviso.

C ++ 03:

A realocação invalida todas as referências, ponteiros e iteradores que se referem aos elementos na sequência. É garantido que nenhuma realocação ocorre durante inserções que ocorrem após uma chamada para reserve () até o momento em que uma inserção tornaria o tamanho do vetor maior que o tamanho especificado na chamada mais recente para reserva () .

C ++ 11:

A realocação invalida todas as referências, ponteiros e iteradores que se referem aos elementos na sequência. É garantido que nenhuma realocação ocorre durante as inserções que ocorrem após uma chamada para reserve () até o momento em que uma inserção tornaria o tamanho do vetor maior que o valor da capacidade () .

Portanto, no C ++ 03, não é " unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)" como mencionado na outra resposta, mas deve ser " greater than the size specified in the most recent call to reserve()". Isso é uma coisa que o C ++ 03 difere do C ++ 11. No C ++ 03, uma vez insert()que o tamanho do vetor alcance o valor especificado na reserve()chamada anterior (que pode ser menor que a corrente, capacity()já que a reserve()pode resultar maior do capacity()que o solicitado), qualquer subsequente insert()poderá causar realocação e invalidar todos os iteradores e referências. No C ++ 11, isso não acontecerá e você sempre pode confiar capacity()em saber com certeza que a próxima realocação não ocorrerá antes que o tamanho ultrapasse capacity().

Concluindo, se você estiver trabalhando com um vetor C ++ 03 e deseja garantir que uma realocação não aconteça ao executar a inserção, é o valor do argumento que você passou anteriormente para reserve()o qual deve verificar o tamanho, não o valor de retorno de uma chamada para capacity(), caso contrário, você poderá se surpreender com uma realocação " prematura ".

neverhoodboy
fonte
14
No entanto, eu atiraria em qualquer compilador que fizesse isso comigo, e nenhum júri no país me condenaria.
Yakk - Adam Nevraumont 2/14/14
9
Eu não "deixei de notar" isso; foi um erro editorial no C ++ 03 que foi corrigido no C ++ 11. Nenhum compilador convencional tira proveito do erro.
Lightness Races em órbita
1
@Yakk Acho que o gcc já invalida os iteradores nessas situações.
precisa
2

Aqui está uma boa tabela de resumo do cppreference.com :

insira a descrição da imagem aqui

Aqui, inserção refere-se a qualquer método que adiciona um ou mais elementos ao contêiner e apagamento se refere a qualquer método que remove um ou mais elementos do contêiner.

DarioP
fonte