Qu’est-ce que cela signifie pour une structure de données d’être «intrusive»?

Une structure de données intrusive est une structure qui nécessite l’aide des éléments qu’elle a l’intention de stocker pour les stocker.

Laissez-moi reformuler cela. Lorsque vous mettez quelque chose dans cette structure de données, ce “quelque chose” prend conscience du fait qu’il se trouve dans cette structure de données, d’une certaine manière. L’ajout de l’élément à la structure de données modifie l’élément.

Par exemple, vous pouvez créer un arbre binary non intrusif, où chaque noeud a une référence aux sous-arbres gauche et droit, et une référence à la valeur de l’élément de ce noeud.

Ou, vous pouvez créer un intrusif où les références à ces sous-arbres sont incorporées dans la valeur elle-même.

Un exemple de structure de données intrusive serait une liste ordonnée d’éléments mutables. Si l’élément change, la liste doit être réorganisée, de sorte que l’object liste doit empiéter sur la confidentialité des éléments pour obtenir leur coopération. c’est à dire. l’élément doit connaître la liste dans laquelle il se trouve et l’informer des changements.

Les systèmes ORM tournent généralement autour de structures de données intrusives, pour minimiser l’itération sur de grandes listes d’objects. Par exemple, si vous extrayez une liste de tous les employés de la firebase database, puis modifiez le nom de l’un d’entre eux et souhaitez la sauvegarder dans la firebase database, la liste intrusive des employés sera affichée lorsque l’object employé change. object sait quelle liste il se trouve

Une liste non intrusive ne serait pas dite et devrait déterminer ce qui a changé et comment elle a changé.

Dans un conteneur intrusif, les données elles-mêmes sont chargées de stocker les informations nécessaires pour le conteneur. Cela signifie que d’un côté, le type de données doit être spécialisé en fonction de la manière dont il sera stocké, de l’autre côté, cela signifie que les données “savent” comment elles sont stockées et peuvent donc être légèrement optimisées.

Non intrusif:

template class LinkedList { struct ListItem { T Value; ListItem* Prev; ListItem* Next; }; ListItem* FirstItem; ListItem* LastItem; [...] ListItem* append(T&& val) { LastItem = LastItem.Next = new ListItem{val, LastItem, nullptr}; }; }; LinkedList IntList; 

Intrusif:

 template class LinkedList { T* FirstItem; T* LastItem; [...] T* append(T&& val) { T* newValue = new T(val); newValue.Next = nullptr; newValue.Prev = LastItem; LastItem.Next = newValue; LastItem = newValue; }; }; struct IntListItem { int Value; IntListItem* Prev; IntListItem* Next; }; LinkedList IntList; 

Personnellement, je préfère le design intrusif pour sa transparence.