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> head
instancji, 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_ptr
destruktor w node
, a następnie użyje rekurencji ogona), co staje się znacznie trudniejsze, jeśli wykonam następujące czynności (ponieważ data
destruktor 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 data
jakiś sposób ma do niego wskaźnik, node
wó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.
źródło
gcc -O3
nie było w stanie zoptymalizować rekurencji ogona (w skomplikowanym przykładzie).Odpowiedzi:
Tak, to ostatecznie
node
zniszczy twój stos, chyba że kompilator po prostu zastosuje optymalizację wywołania ogona do destruktora ishared_ptr
destruktora. Ten ostatni jest bardzo zależny od standardowej implementacji biblioteki. Na przykład STL Microsoftu nigdy tego nie zrobi, ponieważshared_ptr
najpierw 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.
źródło
shared_ptr
. Nie mogę całkowicie pozbyć się wskaźników, ponieważ potrzebowałem bezpieczeństwa wątku.std::atomic_*
przeciążeń, nie?std::atomic<node*>
, i taniej.Późna odpowiedź, ale ponieważ nikt jej nie podał ... napotkałem ten sam problem i rozwiązałem go za pomocą niestandardowego destruktora:
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
list
wskaźnik jest wskaźnikiem do pierwszegonode
, powyższe powinno działać.Jeśli masz rozmytą strukturę (np. Wykres acykliczny), możesz użyć następujących opcji:
Chodzi o to, że kiedy to robisz:
Stary wspólny wskaźnik
next
jest zniszczony (ponieważuse_count
jest teraz0
), 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.źródło
next = std::move(next->next)
wywoływaniemnext->~node()
.next->next
to, ponieważ jest unieważniane (przez operatora przypisania ruchu), zanim wskazana wartośćnext
zostanie zniszczona, a tym samym „zatrzymanie” rekurencji. Właściwie używam tego kodu i tej pracy (przetestowanej zg++
,clang
imsvc
), ale teraz, kiedy to mówisz, nie jestem pewien, czy jest to zdefiniowane przez standard (fakt, że przesunięty wskaźnik jest unieważniany przed zniszczeniem wskazanego starego obiektu wskaźnikiem docelowym).operator=(std::shared_ptr&& r)
jest równoważnastd::shared_ptr(std::move(r)).swap(*this)
. Wciąż ze standardu konstruktor ruchu makestd::shared_ptr(std::shared_ptr&& r)
czynir
pustym, dlategor
jest pusty (r.get() == nullptr
) przed wywołaniemswap
. W moim przypadku środki tenext->next
są puste, zanim stary obiekt wskazywany przeznext
zostanie zniszczony (przezswap
wywołanie).f
jest włączonenext
, a nienext->next
, a ponieważnext->next
jest puste, natychmiast się zatrzymuje.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:
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:
Ten program wiecznie buduje i dekonstruuje łańcuch węzłów. Powoduje to przepełnienie stosu.
źródło