Mam wiele długich list (mają do 20 000 pozycji). Mają różne początki, ale w końcu mogą wskazywać ten sam węzeł od jakiegoś węzła. Postanowiłem pozwolić takiej połączonej liście rosnąć razem i dzielić się pamięcią między nimi.

Dlatego zdecydowałem się zaimplementować połączoną listę ze współdzielonymi wskaźnikami:

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

W ten sposób wszystko działa dobrze. Połączone listy, które nie są już potrzebne, są usuwane. Jeśli współdzielą część z inną połączoną listą, usuwana jest tylko ich część nieudzielona.

Problem pojawia się, gdy listy dłuższe połączone bez części udostępnionych zostaną usunięte. Usuwanie rozpoczyna się od pierwszego elementu. Zmniejsza to liczbę odwołań do następnego elementu, który może być również usunięty, a to powtarza się rekurencyjnie, aż stos przepełni się.

Oto przykład kodu, który tworzy długą listę połączonych, a następnie nie udaje się go usunąć.

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;

Z góry dziękuję za jedno z następujących:

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

Zauważ, że to pytanie nie jest specyficzne dla c ++ 11. Nie obchodzi mnie, która implementacja wspólnych pointów jest używana. Zaimplementowałem nawet własne udostępnione wskaźniki. To pozwoliło mi mieć trochę dłuższe listy, ale pojawiła się rekursja w destruktorach i przepełnienie stosu. I nie widzę żadnego sposobu, w jaki mogłyby być udostępniane wskaźniki zaimplementowane bez rekursji w destruktorach.

EDYTOWAĆ:

Aby uniknąć zamieszania: Chcę powtórzyć, że całe listy mogą być udostępniane. Można więc nazwać je drzewami.

Oto przykład:

lista1 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ę to przedstawić w 3 SharedLinkedList, która nie marnuje momentu, zapisując 1,2,3,4,5,6,7 kilka razy, ale wskazują one to samo miejsce. Dlatego potrzebne jest zliczanie referencji.

delete list3; ma usuwać tylko część, która nie jest współdzielona, ​​tj. elementy 10,11,12.