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.)}

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...

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.

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.

É 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.

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 ".

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

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.