Considere a seguinte implementação de lista vinculada única:
struct node {
std::unique_ptr<node> next;
ComplicatedDestructorClass data;
}
Agora, suponha que eu pare de usar alguma std::unique_ptr<node> head
instância que fica fora do escopo, fazendo com que seu destruidor seja chamado.
Isso vai explodir minha pilha para listas suficientemente grandes? É justo supor que o compilador faça uma otimização bastante complicada ( unique_ptr
o destruidor do inline para o node
's' e depois use a recursão da cauda), o que fica muito mais difícil se eu fizer o seguinte (já que o data
destruidor ofuscaria next
o do, tornando difícil para o compilador perceber as possíveis oportunidades de reordenação e chamada final):
struct node {
std::shared_ptr<node> next;
ComplicatedDestructorClass data;
}
Se de data
alguma forma tem um ponteiro para node
isso, pode até ser impossível a recursão da cauda (embora, é claro, devamos nos esforçar para evitar tais violações do encapsulamento).
Em geral, como alguém deveria destruir essa lista, então? Não podemos percorrer a lista e excluir o nó "atual" porque o ponteiro compartilhado não possui um release
! A única maneira é com um deleter personalizado, que é realmente fedorento para mim.
fonte
gcc -O3
não foi possível otimizar uma recursão de cauda (em um exemplo complicado).Respostas:
Sim, isso acabará com sua pilha, a menos que o compilador aplique uma otimização de chamada de cauda ao
node
destruidor eshared_ptr
destruidor. O último é extremamente dependente da implementação da biblioteca padrão. O STL da Microsoft, por exemplo, nunca fará isso, porqueshared_ptr
primeiro diminui a contagem de referência de seu pontapé (possivelmente destruindo o objeto) e depois diminui a contagem de referência de seu bloco de controle (a contagem fraca de referência). Portanto, o destruidor interno não é um chamado final. Também é uma chamada virtual , o que torna ainda menos provável que ela seja otimizada.As listas típicas resolvem esse problema por não ter um nó próprio no próximo, mas por um contêiner que possui todos os nós e usa um loop para excluir tudo no destruidor.
fonte
shared_ptr
s no final. Não consigo me livrar completamente dos ponteiros, pois precisava da segurança do thread.std::atomic_*
sobrecargas para eles, não?std::atomic<node*>
, e mais barato.Resposta tardia, mas como ninguém a forneceu ... Encontrei o mesmo problema e o resolvi usando um destruidor personalizado:
Se você realmente tem uma lista , ou seja, todo nó é precedido por um nó e tem no máximo um seguidor, e você
list
é um ponteiro para o primeironode
, o que precede deve funcionar.Se você possui alguma estrutura difusa (por exemplo, gráfico acíclico), pode usar o seguinte:
A ideia é que quando você faz:
O ponteiro compartilhado antigo
next
é destruído (porqueuse_count
agora é0
) e você aponta para o seguinte. Isso faz exatamente o mesmo que o destruidor padrão, exceto o iterativamente, em vez de recursivamente, evitando assim o estouro da pilha.fonte
next = std::move(next->next)
chamadasnext->~node()
recursivas.next->next
é invalidado (pelo operador de atribuição de movimentação) antes que o valor apontado pornext
seja destruído, "interrompendo" a recursão. Eu realmente usar este código e este trabalho (testado comg++
,clang
emsvc
), mas agora que você diz isso, não estou certo de que esta é definida pelo padrão (o fato de que o ponteiro movido é invalidada antes da destruição do antigo objeto pontiagudo pelo ponteiro de destino).operator=(std::shared_ptr&& r)
é equivalente astd::shared_ptr(std::move(r)).swap(*this)
. Ainda a partir do padrão, o construtor movimento destd::shared_ptr(std::shared_ptr&& r)
marcasr
esvaziar, assimr
está vazio (r.get() == nullptr
) antes da chamada paraswap
. No meu caso, esse meionext->next
está vazio antes que o objeto antigo apontado pornext
seja destruído (pelaswap
chamada).f
está ativadanext
, nãonext->next
e, comonext->next
é nula, para imediatamente.Para ser sincero, não estou familiarizado com o algoritmo de desalocação de ponteiros inteligentes de qualquer compilador C ++, mas posso imaginar um algoritmo simples e não recursivo que faz isso. Considere isto:
Portanto, não haveria chance da pilha transbordar, e é muito mais simples otimizar um algoritmo recursivo.
Não tenho certeza se isso se encaixa na filosofia "quase zero custo de ponteiros inteligentes".
Eu acho que o que você descreveu não causaria estouro de pilha, mas você poderia tentar construir um experimento inteligente para provar que estava errado.
ATUALIZAR
Bem, isso prova errado o que escrevi anteriormente:
Esse programa cria eternamente e desconstrói uma cadeia de nós. Isso causa excesso de pilha.
fonte