Czy zniszczenie dużej listy przepełni mój stos?

Rozważ następującą pojedynczo połączoną implementację listy:

struct node {
    std::unique_ptr<node> next;
    ComplicatedDestructorClass data;
}

Załóżmy teraz, że przestałem używać std::unique_ptr<node> headinstancji, która następnie wykracza poza zakres, powodując wywołanie jej destruktora.

Czy to zniszczy mój stos na wystarczająco duże listy? Czy można założyć, że kompilator wykona dość skomplikowaną optymalizację (wbudowany unique_ptrdestruktor w node, a następnie użyje rekurencji ogona), co staje się znacznie trudniejsze, jeśli wykonam następujące czynności (ponieważ datadestruktor zaciemniłby next, co utrudnia aby kompilator zauważył potencjalną możliwość ponownego zamawiania i możliwość wywołania ogona):

struct node {
    std::shared_ptr<node> next;
    ComplicatedDestructorClass data;
}

Jeśli w datajakiś sposób ma do niego wskaźnik, nodewówczas rekurencja ogona może być nawet niemożliwa (choć oczywiście powinniśmy starać się unikać takich naruszeń hermetyzacji).

Ogólnie więc, w jaki sposób należy zniszczyć tę listę w inny sposób? Nie możemy przechodzić przez listę i usuwać „bieżącego” węzła, ponieważ wspólny wskaźnik nie ma release! Jedynym sposobem jest niestandardowy deleter, który jest dla mnie naprawdę śmierdzący.

Tak, to ostatecznie nodezniszczy twój stos, chyba że kompilator po prostu zastosuje optymalizację wywołania ogona do destruktora i shared_ptr destruktora. Ten ostatni jest bardzo zależny od standardowej implementacji biblioteki. Na przykład STL Microsoftu nigdy tego nie zrobi, ponieważ shared_ptrnajpierw zmniejsza liczbę referencji swojego punktu (potencjalnie niszcząc obiekt), a następnie zmniejsza liczbę referencji bloku kontrolnego (liczba słabych referencji). Więc wewnętrzny destruktor nie jest wezwaniem do ogona. Jest to również połączenie wirtualne , co sprawia, że ​​jeszcze mniej prawdopodobne jest, że zostanie zoptymalizowane.

Typowe listy omijają ten problem, ponieważ jeden węzeł nie jest właścicielem drugiego, ale jeden kontener, który jest właścicielem wszystkich węzłów i używa pętli do usunięcia wszystkiego z destruktora.

Późna odpowiedź, ale ponieważ nikt jej nie podał ... napotkałem ten sam problem i rozwiązałem go za pomocą niestandardowego destruktora:

virtual ~node () throw () {
    while (next) {
        next = std::move(next->next);
    }
}

Jeśli naprawdę masz listę , tzn. Każdy węzeł jest poprzedzony jednym węzłem i ma co najwyżej jednego obserwatora, a twój listwskaźnik jest wskaźnikiem do pierwszego node, powyższe powinno działać.

Jeśli masz rozmytą strukturę (np. Wykres acykliczny), możesz użyć następujących opcji:

virtual ~node () throw () {
    while (next && next.use_count() < 2) {
        next = std::move(next->next);
    }
}

Chodzi o to, że kiedy to robisz:

next = std::move(next->next);

Stary wspólny wskaźnik nextjest zniszczony (ponieważ use_countjest teraz 0), a Ty wskazujesz na następujące. Robi to dokładnie to samo, co domyślny destruktor, tyle że robi to iteracyjnie zamiast rekurencyjnie, dzięki czemu unika się przepełnienia stosu.

Szczerze mówiąc, nie jestem zaznajomiony z algorytmem inteligentnej dealokacji wskaźnika w żadnym kompilatorze C ++, ale mogę sobie wyobrazić prosty, nierekurencyjny algorytm, który to robi. Rozważ to:

• Masz kolejkę inteligentnych wskaźników oczekujących na zwolnienie.
• Masz funkcję, która pobiera pierwszy wskaźnik i zwalnia go, i powtarza to, aż kolejka będzie pusta.
• Jeśli inteligentny wskaźnik wymaga zwolnienia, zostaje wypchnięty do kolejki i wywoływana jest powyższa funkcja.

Dlatego nie byłoby szansy na przepełnienie stosu, a optymalizacja algorytmu rekurencyjnego jest znacznie prostsza.

Nie jestem pewien, czy wpisuje się to w filozofię „prawie zerowych inteligentnych wskaźników”.

Sądzę, że to, co opisałeś, nie spowoduje przepełnienia stosu, ale możesz spróbować przeprowadzić sprytny eksperyment, aby udowodnić, że się mylę.

AKTUALIZACJA

Cóż, to okazuje się błędne, co napisałem wcześniej:

#include <iostream>
#include <memory>

using namespace std;

class Node;

Node *last;
long i;

class Node
{
public:
   unique_ptr<Node> next;
   ~Node()
   {
     last->next.reset(new Node);
     last = last->next.get();
     cout << i++ << endl;
   }
};

void ignite()
{
    Node n;
    n.next.reset(new Node);
    last = n.next.get();
}

int main()
{
    i = 0;
    ignite();
    return 0;
}

Ten program wiecznie buduje i dekonstruuje łańcuch węzłów. Powoduje to przepełnienie stosu.