Współdzielone wskaźniki usuwają rekursywnie rekurencyjne struktury danych, a przepełnienia stosu

Question

Mam wiele długo powiązanych list (mają do 20 000 pozycji). Mają różne początki, ale mogą ostatecznie wskazywać na ten sam węzeł od pewnego węzła. Postanowiłem pozwolić takiej połączonej liście rosnąć razem i dzielić pamięć między nimi.

Dlatego ve postanowił wdrożyć połączony ze wspólną listę wskaźników:

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

ten sposób wszystko działa poprawnie. Połączone listy, które nie są już potrzebne, są usuwane. Jeśli dzielą one jakąś część z innymi połączonymi listami, tylko ich nie-współdzielona część zostanie usunięta.

Problem pojawia się, gdy dłuższe połączone listy bez części wspólnych zostaną usunięte. Usuwanie rozpoczyna się od pierwszego elementu. Zmniejsza to liczbę odwołań do następnego elementu, który można również usunąć, a to powtarza się rekurencyjnie, aż do przepełnienia stosu.

Oto przykład kodu, który tworzy długo połączoną listę, a następnie kończy się niepowodzeniem.

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; 

Dziękuję z góry za jedną z następujących czynności:

1. Wyjaśnienie shared_pointers i czego mi brakuje. Jak mogę z nich korzystać? I czy można to nawet zrobić za ich pomocą? Czy takie dzielenie pamięci nie jest rzeczą, o której wymyślono wskaźniki akcji?
2. porady, jak ponownie wprowadzić mój kod
3. Ten kod będzie używany do obliczeń naukowych, które będą uruchamiane na moim komputerze. Czy mogę coś zmodyfikować, żeby mieć większy rozmiar stosu?

Należy zauważyć, że to pytanie nie jest specyficzne dla C++ 11. Nie obchodzi mnie, która implementacja wspólnych punktów jest używana. Wprowadziłem nawet własne własne wskaźniki. To pozwoliło mi mieć nieco dłużej połączone listy, ale pojawiła się również rekurencja w destruktorach i przepełnieniu stosu. I nie widzę sposobu, w jaki mogłyby być współdzielone wskaźniki realizowane bez rekursji w destruktorach.

EDIT:

Wystarczy aviod niejasności: Chcę powtórzyć całe wykazy mogą być udostępniane. Więc można nazwać je drzewami.

Oto przykład:

list1 zawiera: 1,2,3,4,5,6,7.

lista2 zawiera: 6,6,6,1,2,3,4,5,6,7

lista3 zawiera: 10,11,12,1,2,3,4,5,6 , 7

Chcę reprezentować to w 3 SharedLinkedList, które nie marnują momory, przechowując 1,2,3,4,5,6,7 kilka razy, ale wskazują na to samo miejsce. Dlatego potrzebne jest zliczanie referencji.

delete list3; ma usunąć tylko część, która nie jest udostępniona, tj. Elementy 10,11,12.

Answer 1

Jeśli używasz shared_ptr będzie zarządzać własności dla Ciebie. Gdy licznik odniesie się do 0, wywoła destruktor wskazanego przedmiotu. Teraz wskazany obiekt zostaje zniszczony, a jako jego element znajduje się następny wspólny wskaźnik, który niszczy następny ... Powoduje to rekurencyjny sposób deallocating memory. Teraz możesz spróbować zwolnić pamięć iteracyjnie. Musisz tylko zachować odniesienie do następnego elementu, aby uniknąć jego zniszczenia i usunąć ręcznie później:

void destroy(SharedLinkedList* l) { 
    auto next=l->next; // take 2nd element 
    delete l;   // delete first 

    while (next) 
    next=next->next; // move next forward, deleting old next 
    } 

Answer 2

Ogólnie rzecz biorąc, shared_ptr jest prawdopodobnie nie dobrym pomysłem dla powiązanych list, z tego powodu, dla którego zwracasz uwagę.W takim przypadku prawdopodobnie musisz zrobić to ręcznie, utrzymując liczbę rodziców w każdym węźle. (To chyba możliwe wypracować jakiś pętli, która pozwala uniknąć przepełnienia stosu shared_ptr, ale wyniki byłyby prawdopodobnie bardziej skomplikowane niż zarządzający pamięć ręcznie.)