Quando è accettabile un riferimento circolare a un puntatore padre?

21
La domanda

Questa overflow dello stack riguarda un bambino che fa riferimento al suo genitore tramite un puntatore.

Inizialmente i commenti erano piuttosto critici sul fatto che il design fosse un'idea orribile.

Capisco che probabilmente non è la migliore idea in generale. Da una regola generale, sembra giusto dire "non farlo!"

Tuttavia, mi chiedo che tipo di condizioni esisterebbero dove dovresti fare qualcosa del genere. Questa domanda qui e le risposte / commenti associati suggeriscono anche che i grafici non facciano qualcosa del genere.

    
posta enderland 04.01.2016 - 22:44
fonte

6 risposte

40

La chiave qui non è se due oggetti hanno riferimenti circolari, ma se quei riferimenti indicano proprietà l'uno dell'altro.

Due oggetti non possono "possedere" l'un l'altro: ciò causa un dilemma intrattabile per l'inizializzazione e l'ordine di cancellazione. Uno deve essere un riferimento facoltativo o indicare in altro modo che un oggetto non gestirà la durata dell'altro.

Considera una lista doppiamente collegata: due nodi si collegano l'uno all'altro, ma nessuno dei due "possiede" l'altro (la lista li possiede entrambi). Ciò significa che nessuno dei nodi alloca la memoria per l'altro o è altrimenti responsabile dell'identità o della gestione a vita dell'altro.

Gli alberi hanno una relazione simile, anche se i nodi di un albero possono assegnare bambini e genitori ai propri figli. Il link da un bambino a un genitore aiuta con il traversal, ma ancora non definisce la proprietà.

Nella maggior parte dei progetti OO, un riferimento a un altro oggetto come membro dati di un oggetto implica la proprietà. Ad esempio, supponiamo di avere classi auto e motore. Nessuno dei due è molto utile da solo. Possiamo dire che questi oggetti dipendono l'uno dall'altro: richiedono la presenza dell'altro per svolgere un lavoro utile. Ma quale "possiede" l'altro? In questo caso diremmo che l'auto è proprietaria del motore perché l'auto è il "contenitore" in cui vivono tutti i componenti automobilistici. Sia nel design OO che nel mondo reale, l'auto è la somma delle sue parti e tutte queste parti sono collegate tra loro all'interno del contesto dell'automobile. Il motore può avere un riferimento a Car, o potrebbe avere un riferimento a TorqueConverter, ma nessun componente all'interno di Car possiede l'auto anche se tale componente ha un riferimento alla Car.

I riferimenti circolari possono essere un cattivo odore di design, ma non necessariamente. Se usati in modo giudizioso e documentati correttamente, possono semplificare l'uso delle strutture dati.

Prova ad attraversare un albero senza riferimenti andando in entrambe le direzioni tra genitori e figli. Certo, potresti creare un approccio basato su stack che è fragile e complesso, oppure potresti utilizzare l'approccio basato su riferimenti che è banalmente semplice.

    
risposta data 04.01.2016 - 23:07
fonte
15

Ci sono diversi aspetti da considerare in un tale progetto:

  • le dipendenze strutturali
  • la relazione di proprietà (i.e.composition vs. altro tipo di associazione)
  • le esigenze di navigazione

Dipendenza strutturale tra classi:

Se miri a riutilizzare le classi di componenti, dovresti evitare una dipendenza non necessaria ed evitare tali strutture circolari chiuse.

Tuttavia a volte due classi sono concettualmente strongmente interconnesse. In questo caso, evitare la dipendenza non è un'opzione reale. Esempio: un albero e le sue foglie, o più in generale un composito e i suoi componenti .

Proprietà degli oggetti:

Un oggetto possiede l'altro? O altrimenti dichiarato: se un oggetto è distrutto, anche l'altro sarà distrutto?

Questo argomento è stato affrontato in modo approfondito da Snowman, quindi non ho intenzione di affrontarlo qui.

Esigenze di navigazione tra oggetti:

Un ultimo problema è la necessità di navigazione. Prendiamo il mio esempio preferito, il modello di design composito del Gang of four .

Gamma & al. menziona esplicitamente la potenziale necessità di avere un riferimento genitore esplicito: " Mantenere il riferimento dai componenti del bambino al genitore può semplificare il traversale e la gestione di una struttura composita " Naturalmente puoi immaginare un attraversamento top-down sistematico, ma per oggetti compositi molto grandi può rallentare in modo significativo le operazioni e in modo esponenziale. Un riferimento diretto, anche circolare, può facilitare in modo significativo la manipolazione dei tuoi materiali compositi.

Un esempio potrebbe essere un modello grafico di un sistema elettronico. Una struttura composita potrebbe rappresentare schede, circuiti, elementi elettronici. Per visualizzare e manipolare il modello, sono necessari alcuni proxy geometrici in una vista GUI. È quindi molto più facile navigare dall'elemento GUI selezionato dall'utente al componente, per scoprire quale è il genitore e con i relativi elementi fratello / sorella, piuttosto che iniziare una ricerca dall'alto verso il basso.

Naturalmente, come Gamma & ho sottolineato, devi assicurare gli invarianti della relazione circolare. Questo può essere complicato, come ha dimostrato la domanda SO a cui fai riferimento. Ma è perfettamente gestibile e in maniera sicura.

Conclusione

Il bisogno di navigazione non deve essere sottovalutato. Non è senza motivo che UML lo abbia esplicitamente indirizzato nella notazione di modellazione. E sì, ci sono situazioni perfettamente valide in cui sono necessari riferimenti circolari.

L'unico punto è che a volte le persone tendono ad andare in tale direzione in fretta. Quindi vale la pena considerare tutti i 3 aspetti coinvolti prima di prendere la decisione di andare o no.

    
risposta data 05.01.2016 - 01:42
fonte
7

Di solito, i riferimenti circolari sono una pessima idea perché significano dipendenze circolari. Probabilmente già sai perché le depedenze circolari sono cattive, ma per completezza, la versione tl; dr è che ogni volta che le classi A e B dipendono l'una dall'altra, è impossibile capire / correggere / ottimizzare / etc A o B senza anche capire / correggere / ottimizzare / ecc l'altra classe allo stesso tempo. Che porta rapidamente a codebase in cui non puoi cambiare nulla senza cambiare tutto.

Tuttavia è possibile avere un riferimento circolare senza creare dipendenze circolari malvagie. Questo funziona fintanto che il riferimento è strettamente facoltativo in senso funzionale. Con ciò intendo che potresti facilmente rimuoverlo dalle classi e che funzionerebbero anche se funzionassero più lentamente. Il caso d'uso principale di cui sono a conoscenza per tali riferimenti circolari che creano non dipendenze sta consentendo il rapido attraversamento di strutture di dati basate su nodi come liste collegate, alberi e heap. Ad esempio, in linea di massima qualsiasi operazione che puoi eseguire su una lista doppiamente collegata puoi anche eseguire su una lista collegata singolarmente, ci sono solo alcune operazioni (come lo spostamento all'indietro nella lista) che hanno una grande O con la versione doppiamente collegata.

    
risposta data 04.01.2016 - 22:55
fonte
5

Il motivo per cui di solito non è una buona idea farlo è perché viola il principio di inversione delle dipendenze . La gente ha scritto molto su questo in modo molto più dettagliato di quanto io possa coprire adeguatamente in questo post, ma si riduce a renderlo difficile da mantenere, perché l'accoppiamento è così stretto. La modifica di una classe richiede quasi sempre una modifica nell'altra, mentre se le dipendenze puntano solo in un modo, le modifiche su un lato dell'interfaccia vengono isolate. Se entrambe le classi puntano a un'interfaccia astratta, ancora meglio.

L'unica eccezione principale è quando non si hanno due classi diverse a livelli di astrazione diversi, ma due nodi della stessa classe, come in un albero, una lista doppiamente collegata, ecc. Qui è più di una struttura relazione rispetto ad una relazione di astrazione. Riferimenti circolari per motivi di efficienza algoritmica sono accettabili e persino incoraggiati in questi casi.

    
risposta data 05.01.2016 - 00:32
fonte
4

[...] suggests even for graphs to not do something like this.

A volte devi solo accedere alle cose in modo bottom-up da una struttura dati diversa dall'albero, mentre l'albero deve accedere alle cose dall'alto verso il basso.

Ad esempio, un quadruplo potrebbe memorizzare elementi in un software di grafica vettoriale. Tuttavia, la selezione dell'utente viene memorizzata in un elenco di selezione separato di riferimenti / puntatori di elementi vettoriali. Quando l'utente vuole eliminare quella selezione, dobbiamo aggiornare il quadruplo, e potrebbe essere molto più efficiente aggiornare l'albero in modo bottom-up partendo dalle foglie piuttosto che dall'alto verso il basso. Altrimenti dovresti, per ogni elemento, lavorare da root a foglia e poi eseguire di nuovo il backup.

    
risposta data 05.01.2016 - 20:45
fonte
1

Doom 3 ha un esempio di oggetto figlio con un puntatore a un oggetto genitore. In particolare utilizza elenchi intrusivi . Per riassumere, un elenco intrusivo è come un elenco collegato, tranne che ogni nodo contiene un puntatore all'elenco stesso.

I vantaggi:

  • Quando gli oggetti possono esistere in più elenchi contemporaneamente, la memoria per i nodi di elenco deve essere allocata e deallocata una sola volta.

  • Quando un oggetto deve essere distrutto, puoi facilmente rimuoverlo da tutti gli elenchi in cui si trova senza cercare linearmente in ogni elenco.

Penso che questo sia uno scenario piuttosto specifico, ma se capisco la tua domanda, è un esempio di un uso accettabile di un oggetto figlio contenente un puntatore al suo oggetto padre.

    
risposta data 05.01.2016 - 17:43
fonte

Leggi altre domande sui tag