Quand une référence circulaire à un pointeur parent est-elle acceptable?

Cette question Stack Overflow concerne un enfant ayant une référence à son parent, via un pointeur.

Les commentaires étaient assez critiques au départ sur le fait que la conception était une horrible idée.

Je comprends que ce n'est probablement pas la meilleure idée en général. D'un point de vue général, il semble juste de dire "ne faites pas ça!"

Cependant, je me demande quelles sortes de conditions existeraient où vous auriez besoin de faire quelque chose comme ça. Cette question ici et les réponses / commentaires associés suggèrent même que les graphiques ne fassent pas quelque chose comme ça.

La clé ici n'est pas de savoir si deux objets ont des références circulaires, mais si ces références indiquent la propriété de l'autre.

Deux objets ne peuvent pas se "posséder": cela provoque un dilemme insoluble pour l'ordre d'initialisation et de suppression. L'un doit être une référence facultative, sinon indiquer qu'un objet ne gérera pas la durée de vie de l'autre.

Considérons une liste doublement liée: deux nœuds se lient l'un à l'autre, mais aucun ne "possède" l'autre (la liste les possède tous les deux). Cela signifie qu'aucun des nœuds n'alloue de mémoire à l'autre ou n'est autrement responsable de la gestion de l'identité ou de la durée de vie de l'autre.

Les arbres ont une relation similaire, bien que les nœuds d'un arbre puissent allouer des enfants et les parents possèdent des enfants. Le lien d'un enfant au parent facilite la traversée, mais là encore, ne définit pas la propriété.

Dans la plupart des conceptions OO, une référence à un autre objet en tant que membre de données d'un objet implique la propriété. Par exemple, supposons que nous ayons des classes Car et Engine. Aucun des deux n'est très utile en soi. On peut dire que ces objets dépendent les uns des autres: ils nécessitent la présence de l'autre pour effectuer un travail utile. Mais qui "possède" l'autre? Dans ce cas, nous dirions que Car possède le moteur, car la voiture est le "conteneur" dans lequel vivent tous les composants automobiles. Dans un design OO et réel, la voiture est la somme de ses parties, et toutes ces parties sont connectées ensemble dans le contexte de la voiture. Le moteur peut avoir une référence à Car, ou il peut avoir une référence à TorqueConverter,

Les références circulaires peuvent être une mauvaise odeur de conception, mais pas nécessairement. Lorsqu'ils sont utilisés judicieusement et correctement documentés, ils peuvent faciliter l'utilisation des structures de données.

Essayez de parcourir un arbre sans références allant dans les deux sens entre les parents et les enfants. Bien sûr, vous pouvez proposer une approche basée sur la pile qui est fragile et complexe, ou vous pouvez utiliser l'approche basée sur les références qui est trivialement simple.

Il y a plusieurs aspects à considérer dans une telle conception:

• les dépendances structurelles
• la relation de propriété (iecomposition vs autre type d'association)
• les besoins de navigation

Dépendance structurelle entre les classes:

Si vous visez à réutiliser des classes de composants, vous devez éviter les dépendances inutiles et éviter ces structures circulaires fermées.

Néanmoins, parfois, deux classes sont conceptuellement fortement liées. Dans ce cas, éviter la dépendance n'est pas une vraie option. Exemple: un arbre et ses feuilles, ou plus généralement un composite et ses composants .

Propriété des objets:

Un objet est-il propriétaire de l'autre? Ou autrement dit: si un objet est détruit, l'autre doit-il également être détruit?

Ce sujet a été abordé en profondeur par Snowman, donc je ne vais pas en parler ici.

Besoins de navigation entre les objets:

Un dernier problème est le besoin de navigation. Prenons mon exemple préféré, le motif de conception composite du Gang of four .

Gamma & al. mentionner explicitement le besoin potentiel d'avoir une référence parent explicite: "Le maintien de la référence des composants enfants à leur parent peut simplifier la traversée et la gestion d'une structure composite " Bien sûr, vous pourriez imaginer une traversée systématique de haut en bas, mais pour les très grands objets composites, il peut considérablement ralentir les opérations et de manière exponentielle. Une référence directe, même circulaire peut faciliter considérablement la manipulation de vos composites.

Un exemple pourrait être un modèle graphique d'un système électronique. Une structure composite pourrait représenter les cartes électroniques, les circuits, les éléments. Pour afficher et manipuler le modèle, vous auriez besoin de proxys géométriques dans une vue GUI. Il est alors certainement beaucoup plus facile de naviguer de l'élément GUI sélectionné par l'utilisateur vers le composant, pour savoir quel est le parent et avec quels sont les éléments frère / sœur associés, que de lancer une recherche descendante.

Bien sûr, comme Gamma & al l'a souligné, vous devez vous assurer des invariants de la relation circulaire. Cela peut être délicat, comme l'a montré la question SO à laquelle vous vous référez. Mais c'est parfaitement gérable et d'une manière sûre.

Conclusion

Le besoin de navigation ne doit pas être sous-estimé. Ce n'est pas sans raison que UML l'a explicitement adressé dans la notation de modélisation. Et oui, il existe une situation parfaitement valable où des références circulaires sont nécessaires.

Le seul point est que parfois les gens ont tendance à aller trop vite dans une telle direction. Il vaut donc la peine de considérer tous les 3 aspects impliqués avant de prendre la décision d'y aller ou non.

Habituellement, les références circulaires sont une très mauvaise idée car elles signifient des dépendances circulaires. Vous savez probablement déjà pourquoi les dépendances circulaires sont mauvaises, mais pour des raisons d'exhaustivité, la version tl; dr est que chaque fois que les classes A et B dépendent l'une de l'autre, il est impossible de comprendre / corriger / optimiser / etc A ou B sans aussi comprendre / fixer / optimiser / etc l'autre classe en même temps. Ce qui conduit rapidement à des bases de code où vous ne pouvez rien changer sans tout changer.

Cependant, il est possible d'avoir une référence circulaire sans créer de mauvaises dépendances circulaires. Cela fonctionne tant que la référence est strictement facultative au sens fonctionnel. J'entends par là que vous pourriez facilement le retirer des cours et ils fonctionneraient toujours, même s'ils se trouvent ralentir. Le cas d'utilisation principal que je connais pour de telles références circulaires ne créant pas de dépendance est de permettre une traversée rapide des structures de données basées sur les nœuds telles que les listes liées, les arbres et les tas. Par exemple, en principe, toute opération que vous pouvez effectuer sur une liste à double liaison, vous pouvez également effectuer sur une liste à liaison unique, il se trouve qu'il y a juste quelques opérations (comme revenir en arrière dans la liste) qui ont une bien meilleure grande- O avec la version à double liaison.

La raison pour laquelle ce n'est généralement pas une bonne idée de le faire, c'est parce que cela viole le principe d'inversion de dépendance . Les gens ont écrit beaucoup à ce sujet de manière beaucoup plus détaillée que je ne peux en parler de manière adéquate dans ce post, mais cela se résume à la rendre difficile à maintenir, car le couplage est si serré. Changer l'une ou l'autre classe nécessite presque toujours un changement dans l'autre, alors que si les dépendances ne pointent que dans un sens, les changements d'un côté de l'interface sont isolés. Si les deux classes pointent vers une interface abstraite, c'est encore mieux.

La seule exception principale est lorsque vous n'avez pas deux classes différentes à différents niveaux d'abstraction, mais deux nœuds de la même classe, comme dans un arbre, une liste doublement liée, etc. Ici, il s'agit plus d'une relation structurelle que d'une relation d'abstraction. Dans un souci d'efficacité algorithmique, les références circulaires sont acceptables et même encouragées dans ce type de cas.

[...] suggère même aux graphiques de ne pas faire quelque chose comme ça.

Parfois, il vous suffit d'accéder aux éléments de façon ascendante à partir d'une structure de données différente de celle de l'arborescence, tandis que l'arborescence doit accéder aux éléments de manière descendante.

Par exemple, un quadtree peut stocker des éléments dans un logiciel de graphisme vectoriel. Cependant, la sélection de l'utilisateur est stockée dans une liste de sélection distincte de références / pointeurs d'éléments vectoriels. Lorsque l'utilisateur souhaite supprimer cette sélection, nous devons mettre à jour le quadtree, et il pourrait être beaucoup plus efficace de mettre à jour l'arbre de façon ascendante à partir des feuilles plutôt que de haut en bas. Sinon, vous devrez, pour chaque élément, travailler de la racine à la feuille, puis sauvegarder à nouveau.

Doom 3 contient un exemple d'objet enfant avec un pointeur sur un objet parent. Plus précisément, il utilise des listes intrusives . Pour résumer, une liste intrusive est comme une liste liée, sauf que chaque nœud contient un pointeur sur la liste elle-même.

Avantages:

• Lorsque des objets peuvent exister dans plusieurs listes simultanément, la mémoire des nœuds de liste doit être allouée et désallouée une seule fois.

• Lorsqu'un objet doit être détruit, vous pouvez facilement le supprimer de toutes les listes dans lesquelles il se trouve sans rechercher linéairement dans chaque liste.

Je pense que c'est un scénario assez spécifique, mais si je comprends votre question, c'est un exemple d'une utilisation acceptable d'un objet enfant contenant un pointeur sur son objet parent.