Considere la siguiente implementación de lista vinculada individualmente:
struct node {
std::unique_ptr<node> next;
ComplicatedDestructorClass data;
}
Ahora, supongamos que dejo de usar alguna std::unique_ptr<node> head
instancia que luego se sale del alcance y hace que se llame a su destructor.
¿Esto volará mi pila de listas lo suficientemente grandes? ¿Es justo suponer que el compilador hará una optimización bastante complicada ( unique_ptr
destructor en línea en node
el, luego usará la recursión de cola), que se vuelve mucho más difícil si hago lo siguiente (ya que el data
destructor ofuscaría next
el de él, lo que lo dificultaría para que el compilador note la posible oportunidad de reordenamiento y llamada de cola):
struct node {
std::shared_ptr<node> next;
ComplicatedDestructorClass data;
}
Si de data
alguna manera tiene un puntero, node
entonces podría ser imposible para la recursión de la cola (aunque, por supuesto, deberíamos esforzarnos por evitar tales brechas de encapsulación).
En general, ¿cómo se supone que se debe destruir esta lista de otra manera, entonces? No podemos atravesar la lista y eliminar el nodo "actual" porque el puntero compartido no tiene un release
! La única forma es con un eliminador personalizado, lo cual es realmente maloliente para mí.
fuente
gcc -O3
no fue posible optimizar una recursión de la cola (en un ejemplo complicado).Respuestas:
Sí, esto eventualmente volará tu pila, a menos que el compilador simplemente aplique una optimización de llamada de cola al
node
destructor yshared_ptr
al destructor. Este último es extremadamente dependiente de la implementación estándar de la biblioteca. El STL de Microsoft, por ejemplo, nunca hará eso, porqueshared_ptr
primero disminuye el recuento de referencia de su destinatario (posiblemente destruyendo el objeto) y luego disminuye el recuento de referencia de su bloque de control (el recuento de referencia débil). Entonces el destructor interno no es una llamada de cola. También es una llamada virtual , lo que hace que sea aún menos probable que se optimice.Las listas típicas resuelven ese problema al no tener un nodo propio al siguiente, sino al tener un contenedor que posee todos los nodos y usa un bucle para eliminar todo en el destructor.
fuente
shared_ptr
al final. No puedo deshacerme por completo de los punteros ya que necesitaba la seguridad del hilo.std::atomic_*
sobrecargas para ellos, ¿no?std::atomic<node*>
también, y más barato.Respuesta tardía pero como nadie me la proporcionó ... Me encontré con el mismo problema y lo resolví usando un destructor personalizado:
Si realmente tiene una lista , es decir, cada nodo está precedido por un nodo y tiene como máximo un seguidor, y su
list
puntero es el primeronode
, lo anterior debería funcionar.Si tiene alguna estructura difusa (por ejemplo, un gráfico acíclico), puede usar lo siguiente:
La idea es que cuando lo haces:
El puntero compartido anterior
next
se destruye (porqueuse_count
es ahora0
), y señala lo siguiente. Esto hace exactamente lo mismo que el destructor predeterminado, excepto que lo hace de forma iterativa en lugar de recursiva y, por lo tanto, evita el desbordamiento de la pila.fuente
next = std::move(next->next)
llamadasnext->~node()
recursivas.next->next
es invalidado (por el operador de asignación de movimiento) antes de quenext
se destruya el valor señalado por , "deteniendo" la recursión. De hecho, utilizo este código y este trabajo (probado cong++
,clang
ymsvc
), pero ahora que lo dice, no estoy seguro de que esto esté definido por el estándar (el hecho de que el puntero movido se invalida antes de la destrucción del antiguo objeto señalado por el puntero de destino).operator=(std::shared_ptr&& r)
es equivalente astd::shared_ptr(std::move(r)).swap(*this)
. Todavía desde el estándar, el constructor de movimiento destd::shared_ptr(std::shared_ptr&& r)
maker
empty, por lo tanto,r
está vacío (r.get() == nullptr
) antes de la llamada aswap
. En mi caso, esto significa quenext->next
está vacío antes de que el viejo objeto señaladonext
sea destruido (por laswap
llamada).f
está activadanext
, nonext->next
, y comonext->next
es nula, se detiene de inmediato.Para ser honesto, no estoy familiarizado con el algoritmo de desasignación de puntero inteligente de ningún compilador de C ++, pero puedo imaginar un algoritmo simple y no recursivo que hace esto. Considera esto:
Por lo tanto, no habría posibilidad de que la pila se desbordara, y es mucho más simple que optimizar un algoritmo recursivo.
No estoy seguro de si esto encaja en la filosofía de "punteros inteligentes de costo casi cero".
Supongo que lo que describiste no provocaría un desbordamiento de la pila, pero podrías intentar construir un experimento inteligente para demostrar que estoy equivocado.
ACTUALIZAR
Bueno, esto prueba mal lo que escribí anteriormente:
Este programa construye eternamente y deconstruye una cadena de nodos. Causa desbordamiento de pila.
fuente