Que signifie, pour une structure de données pour être "intrusif"?

Question

J'ai vu le terme intrusive utilisé pour décrire des structures de données comme les listes et les piles, mais ça veut dire quoi?

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

Aussi, pourquoi faire intrusif (ou non intrusives)? Quels sont les avantages? Quels sont les inconvénients?

Answer 1

Intrusive structure de données est celui qui exige l'aide d'éléments qu'il a l'intention de les stocker afin de les stocker.

Permettez-moi de reformuler ce qui. Lorsque vous mettez quelque chose dans la structure de données, que ce "quelque chose" devient conscient du fait que c'est dans cette structure de données, d'une certaine façon. L'ajout de l'élément de données modifications de la structure de l'élément.

Par exemple, vous pouvez construire un non-intrusive arbre binaire, où chaque nœud de disposer d'une référence à gauche et à droite sous les arbres, et une référence à l'élément de la valeur de ce noeud.

Ou, vous pouvez construire une intrusif où les références à ces sous-arbres sont incorporés dans la valeur elle-même.

Un exemple d'un intrusif structure de données serait une liste ordonnée d'éléments qui sont mutables. Si l'élément change, la liste doit être réorganisée, de sorte que les objets de la liste a à empiéter sur la vie privée des éléments afin d'obtenir leur coopération. c'est à dire. l'élément a à savoir à propos de la liste il est, et de l'informer des changements.

ORM-systèmes habituellement tournent autour intrusive structures de données, afin de minimiser l'itération sur les 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 modifier le nom de l'un d'entre eux, et que vous voulez enregistrer dans la base de données, l'intrusion de la liste des employés serait dit quand l'employé de l'objet a changé, car cet objet ne sait qui liste dans.

Un non-intrusive liste ne serait pas dit, et aurait pour comprendre ce qui a changé et comment elle a changé par lui-même.

Answer 2

Dans un intrusive contenant les données lui-même est chargé de stocker les informations nécessaires pour le conteneur. Qui signifie que, d'un côté le type de données doit être spécialisée en fonction de la façon dont il sera stocké, de l'autre côté, cela signifie que les données "sait" comment elle est stockée et peut donc être optimisé un peu mieux.

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 intrusif de conception pour la transparence.