Duração do Iterator C ++ e detecção de invalidação

8

Com base no que é considerado idiomático no C ++ 11:

  • deve um iterador em um contêiner personalizado sobreviver ao próprio contêiner sendo destruído?
  • deve ser possível detectar quando um iterador é invalidado?
  • as condições acima estão condicionadas a "compilações de depuração" na prática?

Detalhes : Recentemente, estive atualizando meu C ++ e aprendendo a usar o C ++ 11. Como parte disso, escrevi um invólucro idiomático em torno da biblioteca do uriparser . Parte disso é agrupar a representação da lista vinculada dos componentes do caminho analisado. Estou procurando conselhos sobre o que é idiomático para contêineres.

Uma coisa que me preocupa, vindo mais recentemente de linguagens coletadas de lixo, é garantir que objetos aleatórios não desapareçam apenas nos usuários se cometerem um erro em relação à vida útil. Para explicar isso, o PathListcontêiner e seus iteradores mantêm um shared_ptrobjeto de estado interno real. Isso garante que, desde que exista algo que aponte para esses dados, o mesmo ocorre com os dados.

No entanto, olhando para o STL (e muita pesquisa), não parece que os contêineres C ++ garantam isso. Eu tenho essa horrível suspeita de que a expectativa é apenas permitir que os contêineres sejam destruídos, invalidando quaisquer iteradores junto com ele. std::vectorcertamente parece permitir que os iteradores sejam invalidados e ainda (incorretamente) funcionem.

O que eu quero saber é: o que é esperado do código C ++ 11 "bom" / idiomático? Dadas as novas dicas inteligentes e brilhantes, parece meio estranho que o STL permita que você desanime facilmente ao vazar acidentalmente um iterador. Está usando shared_ptrpara os dados de backup uma ineficiência desnecessária, uma boa idéia para depuração ou algo esperado que o STL simplesmente não faz?

(Espero que o aterramento em "C ++ 11 idiomático" evite cobranças de subjetividade ...)

DK.
fonte

Respostas:

10

Está usando shared_ptrpara os dados de backup uma ineficiência desnecessária

Sim - força um indireção extra e uma alocação extra por elemento, e em programas multithread, cada incremento / decréscimo da contagem de referência é muito caro, mesmo que um determinado contêiner seja usado apenas dentro de um único encadeamento.

Tudo isso pode ser bom e até desejável em algumas situações, mas a regra geral é não impor sobrecargas desnecessárias que o usuário não pode evitar , mesmo quando são inúteis.

Como nenhuma dessas sobrecargas é necessária, mas é um pouco de depuração (e lembre-se, a vida útil incorreta do iterador é um bug de lógica estática, não um comportamento estranho de tempo de execução), ninguém agradeceria por diminuir o código correto para detectar seus erros.


Então, para a pergunta original:

deve um iterador em um contêiner personalizado sobreviver ao próprio contêiner sendo destruído?

a verdadeira questão é: o custo de rastrear todos os iteradores ativos em um contêiner e invalidá-los quando o contêiner é destruído deve ser aplicado a pessoas cujo código está correto?

Acho que provavelmente não, embora, se houver algum caso em que seja realmente difícil gerenciar a vida útil do iterador corretamente e você esteja disposto a receber a ocorrência, um contêiner dedicado (ou adaptador de contêiner) que fornece esse serviço pode ser adicionado como uma opção .

Como alternativa, alternar para uma implementação de depuração baseada em um sinalizador de compilador pode ser razoável, mas é uma alteração muito maior e mais cara do que a maioria controlada por DEBUG / NDEBUG. É certamente uma mudança maior do que remover instruções assert ou usar um alocador de depuração.


Eu esqueci de mencionar, mas sua solução de usar em shared_ptrtodos os lugares não necessariamente corrige seu bug de qualquer maneira: ele pode simplesmente trocá-lo por um bug diferente , ou seja, um vazamento de memória.

Sem utilidade
fonte
"o custo de rastrear todos os iteradores ativos em um contêiner e invalidá-los quando o contêiner é destruído deve ser imputado a pessoas cujo código está correto?" Parreira não . Como sua postagem indica, um dos lemas de fato do C ++ é "você não paga pelo que não usa". É por uma razão muito boa: isso prejudicaria muitos projetos bem programados se eles tivessem que fazer verificações dos sentidos contra todas as coisas idiotas que um mau programador poderia fazer. Mas, é claro, como você indicou, se alguém realmente quer isso ... eles têm as ferramentas para implementá-lo (e manter). Melhor dos dois mundos!
Underscore_d
7

No C ++, se você deixar o contêiner ser destruído, os iteradores se tornarão inválidos. No mínimo, isso significa que o iterador é inútil e, se você tentar desreferê-lo, muitas coisas ruins podem acontecer (exatamente o quão ruim depende da implementação, mas geralmente é muito ruim).

Em uma linguagem como C ++, é responsabilidade do programador manter essas coisas em ordem. Esse é um dos pontos fortes da linguagem, porque você pode depender bastante de quando as coisas acontecem (você excluiu um objeto? Isso significa que, no momento da exclusão, o destruidor será chamado e a memória será liberada, e você poderá depender ), mas também significa que você não pode manter os iteradores em contêineres em todo o lugar e excluí-lo.

Agora, você poderia escrever um contêiner que mantém os dados por perto até que os iteradores acabem? Claro, você claramente conseguiu. Essa não é a maneira usual de C ++, mas não há nada de errado com ela, desde que seja devidamente documentada (e, é claro, depurada). Não é apenas como os contêineres da STL funcionam.

Michael Kohne
fonte
1
nota que mal pode ir de retornar um sentinal de comportamento indefinido
aberração catraca
@ratchetfreak - sim, é verdade. No caso em questão (iteradores em um contêiner), geralmente não há uma boa maneira de definir o valor sentinal; portanto, a maneira C ++ usual (e o comportamento do STL) tende a 'comportamento indefinido'.
Michael Kohne
5

Uma das diferenças (geralmente não ditas) entre as linguagens C ++ e GC é que o idioma C ++ convencional assume que todas as classes são classes de valor.

Existem ponteiros e referências, mas eles são relegados principalmente para permitir o despacho polimórfico (via indirection da função virtual) ou gerenciar objetos cuja vida útil deve sobreviver àquela do bloco que os criou.

Neste último caso, é responsabilidade do programador definir a política e a política sobre quem cria e quem e quando deve destruir. Ponteiros inteligentes (como shared_ptrou unique_ptr) são apenas ferramentas para ajudar nessa tarefa nos casos muito particulares (e frequentes) em que um objeto é "compartilhado" por diferentes proprietários (e você deseja que o último o destrua) ou precisa ser movido entre contextos tendo sempre um único contexto.

Os interadores, por design, fazem sentido apenas durante ... uma iteração e, portanto, eles não devem ser "armazenados para uso posterior", pois o que eles se referem não é concedido para permanecer o mesmo ou permanecer lá (um contêiner pode realocar sua localização). conteúdo ao crescer ou encolher ... invalidando tudo). Contêineres baseados em link (como lists) são uma exceção a esta regra geral, não a regra em si.

No C ++ idiomático, se A "precisar" de B, B deve pertencer a um local que vive mais do que o local que possui A, portanto, não é necessário "rastreamento de vida" de B de A.

shared_ptre weak_ptrajude quando esse idioma for muito restritivo, permitindo respectivamente as políticas "não desapareça até que todos permitam" ou as políticas "se você desapareça, deixe uma mensagem para nós". Mas eles têm um custo, já que, para isso, precisam alocar alguns dados auxiliares.

O próximo passo é o gc_ptr-s (que a biblioteca padrão não oferece, mas que você pode implementar, se desejar, usando algoritmos de marca e varredura de exemplo) em que as estruturas de rastreamento serão ainda mais complexas e mais intensivas no processador. sua manutenção.

Emilio Garavaglia
fonte
4

Em C ++, é idiomático fazer qualquer coisa que

  • pode ser evitada através de cuidadosa codificação e
  • incorreria em custos de tempo de execução para se proteger contra

um comportamento indefinido .

No caso particular de iteradores, a documentação de cada contêiner informa quais operações invalidam os iteradores (a destruição do contêiner está sempre entre eles) e o acesso ao iterador inválido é Comportamento indefinido. Na prática, isso significa que o tempo de execução acessará cegamente o ponteiro não válido. Geralmente ele trava, mas pode corromper a memória e causar resultados completamente imprevisíveis.

Fornecer verificações opcionais que podem ser ativadas no modo de depuração (com #defineo padrão ativado se _DEBUGestiver definido e desativado se NDEBUGestiver) é uma boa prática.

No entanto, lembre-se de que o C ++ foi projetado para lidar com casos em que é necessário todo o desempenho e as verificações às vezes podem ser bastante caras, já que os iteradores são frequentemente usados ​​em loops apertados, portanto, não os habilite por padrão.

Em nosso projeto de trabalho, tive que desativar a verificação do iterador na biblioteca padrão da Microsoft, mesmo no modo de depuração, porque alguns contêineres usam outros contêineres e iteradores internamente e apenas destruir um enorme estava demorando meia hora por causa das verificações!

Jan Hudec
fonte