Kiedy dopuszczalne jest cykliczne odniesienie do wskaźnika macierzystego?

To pytanie o przepełnienie stosu dotyczy dziecka mającego odniesienie do swojego rodzica za pomocą wskaźnika.

Komentarze były początkowo dość krytyczne, ponieważ projekt był okropnym pomysłem.

Rozumiem, że to prawdopodobnie nie jest najlepszy pomysł w ogóle. Zgodnie z ogólną zasadą wydaje się słuszne powiedzenie „nie rób tego!”

Zastanawiam się jednak, jakie byłyby warunki, w których trzeba by zrobić coś takiego. To pytanie tutaj i powiązane odpowiedzi / komentarze sugerują, że nawet grafy nie robią czegoś takiego.

Kluczem tutaj nie jest to, czy dwa obiekty mają odwołania cykliczne, ale czy te odniesienia wskazują na ich własność .

Dwa obiekty nie mogą „posiadać” siebie nawzajem: powoduje to trudny dylemat dla kolejności inicjalizacji i usuwania. Jedno musi być opcjonalnym odniesieniem lub w inny sposób wskazywać, że jeden obiekt nie będzie zarządzał czasem życia drugiego.

Rozważ podwójnie połączoną listę: dwa węzły łączą się ze sobą w przód iw tył, ale żaden z nich „nie jest właścicielem” drugiego (lista jest ich właścicielem). Oznacza to, że żaden węzeł nie przydziela pamięci drugiemu ani nie jest w inny sposób odpowiedzialny za tożsamość lub zarządzanie czasem życia drugiego.

Drzewa mają podobny związek, chociaż węzły w drzewie mogą przydzielać dzieci, a rodzice mają własne dzieci. Łącze między dzieckiem a rodzicem pomaga w przejściu, ale ponownie nie definiuje własności.

W większości projektów OO odwołanie do innego obiektu jako elementu danych obiektu oznacza własność. Załóżmy na przykład, że mamy klasy Car and Engine. Żadne z nich nie jest bardzo przydatne samo w sobie. Można powiedzieć, że obiekty te są od siebie zależne : wymagają obecności drugiego, aby wykonać użyteczną pracę. Ale który „jest właścicielem” drugiego? W tym przypadku powiedzielibyśmy, że Car jest właścicielem silnika, ponieważ samochód jest „kontenerem”, w którym mieszkają wszystkie części samochodowe. Zarówno w wersji OO, jak i rzeczywistej, samochód jest sumą jego części, a wszystkie te części są ze sobą połączone w kontekście samochodu. Silnik może mieć odniesienie do samochodu lub może mieć odniesienie do TorqueConverter,

Odnośniki kołowe mogą mieć nieprzyjemny zapach, ale niekoniecznie. Gdy są używane rozsądnie i poprawnie udokumentowane, mogą ułatwić korzystanie ze struktur danych.

Spróbuj przemierzać drzewo bez odniesień, idąc w obie strony między rodzicami a dziećmi. Jasne, możesz wymyślić podejście oparte na stosie, które jest kruche i złożone, lub możesz zastosować podejście oparte na referencjach, które jest banalnie proste.

W takim projekcie należy wziąć pod uwagę kilka aspektów:

• zależności strukturalne
• relacja własności (skład a inny rodzaj powiązania)
• potrzeby nawigacji

Zależność strukturalna między klasami:

Jeśli dążysz do ponownego użycia klas komponentów, powinieneś unikać niepotrzebnej zależności i unikać takich zamkniętych struktur kołowych.

Niemniej jednak czasami dwie klasy są silnie ze sobą powiązane koncepcyjnie. W takim przypadku unikanie zależności nie jest realną opcją. Przykład: drzewo i jego liście, lub bardziej ogólnie kompozyt i jego składniki .

Własność przedmiotów:

Czy jeden obiekt jest właścicielem drugiego? Lub inaczej powiedziane: jeśli jeden przedmiot zostanie zniszczony, czy drugi również zostanie zniszczony?

Ten temat został dogłębnie poruszony przez Bałwana, więc nie zamierzam się nim tutaj zajmować.

Potrzeby nawigacyjne między obiektami:

Ostatnim problemem jest potrzeba nawigacji. Weźmy mój ulubiony przykład, kompozytowe wzorca projektowego z bandy czworga .

Gamma i in. wyraźnie wspomina o potencjalnej potrzebie wyraźnego odniesienia do rodzica: „ Utrzymanie odniesienia od komponentów potomnych do ich rodzica może uprościć przechodzenie i zarządzanie strukturą złożoną ” Oczywiście można sobie wyobrazić systematyczne przechodzenie od góry w dół, ale w przypadku bardzo dużych obiektów złożonych może znacznie spowolnić operacje w sposób wykładniczy. Bezpośrednie odniesienie, nawet okrągłe, może znacznie ułatwić manipulowanie twoimi kompozytami.

Przykładem może być model graficzny układu elektronicznego. Struktura złożona może reprezentować płytki elektroniczne, obwody, elementy. Aby wyświetlić i manipulować modelem, potrzebujesz geometrycznych proxy w widoku GUI. Z pewnością znacznie łatwiej jest nawigować od elementu GUI wybranego przez użytkownika do komponentu, aby dowiedzieć się, który jest rodzicem i z którymi są powiązane elementy brat / siostra, niż rozpocząć wyszukiwanie z góry na dół.

Oczywiście, jak wskazali Gamma i in., Musisz zapewnić niezmienników okrągłej relacji. Może to być trudne, jak pokazało pytanie SO, do którego się odwołujesz. Ale jest to doskonale zarządzalne i bezpieczne.

Wniosek

Potrzeba nawigacji nie powinna być zaniżona. Nie bez powodu UML wyraźnie zajął się tym w notacji modelowania. I tak, istnieją całkowicie uzasadnione sytuacje, w których potrzebne są odwołania cykliczne.

Chodzi tylko o to, że czasami ludzie szybko zmierzają w takim kierunku. Warto więc wziąć pod uwagę wszystkie 3 aspekty, zanim podejmiesz decyzję, czy to zrobić, czy nie.

Zwykle odwołania cykliczne są bardzo złym pomysłem, ponieważ oznaczają zależności cykliczne. Prawdopodobnie już wiesz, dlaczego zależności kołowe są złe, ale ze względu na kompletność, wersja tl; dr jest taka, że ​​ilekroć klasy A i B zależą od siebie, nie można zrozumieć / naprawić / zoptymalizować / itd. Ani A, ani B rozumienie / poprawianie / optymalizowanie / itp. drugiej klasy w tym samym czasie. Co szybko prowadzi do baz kodowych, w których nie można niczego zmienić bez zmiany wszystkiego.

Jednakże, to jest możliwe, aby odwołanie cykliczne bez tworzenia zło wzajemnie od siebie zależnych. Działa to tak długo, jak odniesienie jest ściśle opcjonalne w sensie funkcjonalnym. Rozumiem przez to, że możesz łatwo usunąć go z zajęć, a one nadal będą działać, nawet jeśli będą działały wolniej. Głównym przypadkiem, dla którego zdaję sobie sprawę z tego, że takie cykliczne odwołania nie tworzące zależności są umożliwienie szybkiego przejścia do struktur danych opartych na węzłach, takich jak listy połączone, drzewa i stosy. Na przykład, w zasadzie każda operacja, którą możesz wykonać na podwójnie połączonej liście, którą możesz również wykonać na pojedynczo połączonej liście, zdarza się, że jest kilka operacji (takich jak przejście do tyłu przez listę), które mają znacznie lepsze duże- O z podwójnie połączoną wersją.

Powodem tego zazwyczaj nie jest dobry pomysł, ponieważ narusza zasadę inwersji zależności . Ludzie napisali o tym dużo bardziej szczegółowo niż ja mogę odpowiednio opisać w tym poście, ale sprowadza się to do utrudnienia w utrzymaniu, ponieważ sprzęgło jest tak ciasne. Zmiana jednej klasy prawie zawsze wymaga zmiany w drugiej, podczas gdy jeśli zależności wskazują tylko w jedną stronę, zmiany po jednej stronie interfejsu są izolowane. Jeśli obie klasy wskazują na abstrakcyjny interfejs, nawet lepiej.

Jedynym głównym wyjątkiem jest sytuacja, gdy nie masz dwóch różnych klas na różnych poziomach abstrakcji, ale dwa węzły tej samej klasy, takie jak drzewo, podwójnie połączona lista itp. Tutaj jest to bardziej relacja strukturalna niż związek abstrakcyjny. Odniesienia cykliczne ze względu na wydajność algorytmiczną są dopuszczalne, a nawet zalecane w tego rodzaju przypadkach.

[...] sugeruje nawet, aby wykresy nie robiły czegoś takiego.

Czasami musisz po prostu uzyskać dostęp do rzeczy w sposób oddolny z innej struktury danych niż drzewo, podczas gdy drzewo musi uzyskać dostęp do rzeczy w sposób z góry na dół.

Jako przykład, drzewo czteroosobowe może przechowywać elementy w oprogramowaniu grafiki wektorowej. Jednak wybór użytkownika jest przechowywany na osobnej liście wyboru odniesień / wskaźników elementów wektorowych. Gdy użytkownik chce usunąć tę selekcję, musimy zaktualizować drzewo czwórkowe, a tam może być o wiele bardziej wydajna aktualizacja drzewa w sposób oddolny, zaczynając od liści, a nie od góry. W przeciwnym razie musisz dla każdego elementu pracować od korzenia do liścia, a następnie wykonać kopię zapasową ponownie.

Doom 3 ma przykład obiektu podrzędnego ze wskaźnikiem do obiektu nadrzędnego. W szczególności wykorzystuje natrętne listy . Podsumowując, natrętna lista jest jak lista połączona, tyle że każdy węzeł zawiera wskaźnik do samej listy.

Zalety:

• Gdy obiekty mogą istnieć na kilku listach jednocześnie, pamięć dla węzłów listy musi zostać przydzielona i cofnięta tylko raz.

• Kiedy obiekt musi zostać zniszczony, możesz łatwo usunąć go ze wszystkich list, na których się znajduje, bez przeszukiwania każdej listy liniowo.

Myślę, że jest to dość specyficzny scenariusz, ale jeśli rozumiem twoje pytanie, jest to przykład dopuszczalnego użycia obiektu potomnego zawierającego wskaźnik do obiektu nadrzędnego.