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

J'ai vu le terme intrusif utilisé pour décrire des structures de données telles que des listes et des piles, mais qu'est-ce que cela signifie?

Pouvez-vous donner un exemple de code d'une structure de données intrusive, et en quoi elle diffère d'une structure non intrusive?

Aussi, pourquoi le rendre intrusif (ou non intrusif)? Quels sont les bénéfices? Quels sont les inconvénients?

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.

Permettez-moi de 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 binaire non intrusif, où chaque nœud a une référence aux sous-arbres gauche et droit, et une référence à la valeur d'élément de ce nœud.

Vous pouvez également en créer une intrusive dans laquelle les références à ces sous-arbres sont intégrées dans la valeur elle-même.

Un exemple de structure de données intrusive serait une liste ordonnée d'éléments modifiables. Si l'élément change, la liste doit être réorganisée, donc l'objet de la liste doit empiéter sur la confidentialité des éléments afin d'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'objets. Par exemple, si vous récupérez une liste de tous les employés dans la base de données, puis changez le nom de l'un d'entre eux et souhaitez l'enregistrer à nouveau dans la base de données, la liste intrusive d'employés sera informée lorsque l'objet employé a changé car cela l'objet sait dans quelle liste il se trouve.

Une liste non intrusive ne serait pas révélée et devrait déterminer ce qui a changé et comment cela a changé par elle-même.

Dans un conteneur intrusif, les données elles-mêmes sont responsables du stockage des 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 façon dont il sera stocké, de l'autre, cela signifie que les données "savent" comment elles sont stockées et peuvent donc être légèrement mieux optimisées.

Non intrusif:

template<typename T>
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<int> IntList;

Intrusif:

template<typename T>
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<IntListItem> IntList;

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