Tengo un número de listas enlazadas largas (tienen hasta 20,000 artículos). Tienen diferentes comienzos, pero eventualmente pueden apuntar al mismo nodo desde algún nodo en adelante. He decidido dejar que esa lista enlazada crezca junta y comparta la memoria entre ellos.

Es por eso que he decidido implementar la lista enlazada con punteros compartidos:

#include <memory>
struct SharedLinkedList {
    int someData;
    std::shared_ptr<SharedLinkedList> next;
};

De esta manera todo funciona bien. Las listas enlazadas que ya no son necesarias se eliminan. Si comparten alguna parte con otra lista vinculada, solo se eliminará su parte no compartida.

El problema aparece cuando las listas enlazadas más largas sin partes compartidas están a punto de ser eliminadas. La eliminación comienza con el primer elemento. Esto disminuye el número de referencias al siguiente elemento que también se puede eliminar y esto se repite de forma recursiva hasta que la pila se desborda.

Aquí está el ejemplo de código que crea una larga lista enlazada y luego falla al eliminarlo.

SharedLinkedList* beginningOfList;
SharedLinkedList* actualElement = new SharedLinkedList();
SharedLinkedList* nextElement;

beginningOfList = actualElement;
for (int i = 0; i < 1000; i++) { // 100 is OK, 1000 is KO
    nextElement = new SharedLinkedList();
    actualElement->next = std::shared_ptr<SharedLinkedList>(nextElement);
    actualElement = nextElement;
}
delete beginningOfList;

Agradezco de antemano por cualquiera de los siguientes:

Explicación de shared_pointers y de lo que me estoy perdiendo. ¿Cómo puedo usarlos? ¿Y puede incluso hacerse con ellos? ¿El hecho de compartir la memoria no fue lo que inventaron los indicadores de compartir?Consejos sobre cómo volver a implementar mi código.Este código se usará para cálculos científicos que se ejecutarán en mi computadora. ¿Puedo modificar algo de alguna manera para tener un tamaño más grande de pila?

Tenga en cuenta que esta pregunta no es específica de c ++ 11. No me importa qué implementación de pointes compartidos se use. Incluso implementé mis propios punteros compartidos. Esto me permitió tener listas enlazadas un poco más largas, pero también apareció la recursión en los destructores y el desbordamiento de pila. Y no veo cómo se podrían implementar punteros compartidos sin recursión en los destructores.

EDITAR:

Solo para evitar confusiones: quiero repetir que se pueden compartir todas las listas. Así que uno podría llamarlos árboles.

Aquí está el ejemplo:

La lista 1 contiene: 1,2,3,4,5,6,7.

La lista2 contiene: 6,6,6,1,2,3,4,5,6,7

La lista 3 contiene: 10,11,12,1,2,3,4,5,6,7

Quiero representar esto en 3 SharedLinkedList que no desperdician la memoria almacenando 1,2,3,4,5,6,7 varias veces pero apuntan al mismo lugar. Por eso es necesario contar con referencias.

delete list3; se supone que elimina solo la parte que no se comparte, es decir, los elementos 10,11,12.