Was bedeutet es, wenn eine Datenstruktur “aufdringlich” ist?

Ich habe den Begriff gesehen aufdringlich verwendet, um Datenstrukturen wie Listen und Stapel zu beschreiben, aber was bedeutet es?

Können Sie ein Codebeispiel für eine aufdringliche Datenstruktur geben und wie sie sich von einer nicht aufdringlichen unterscheidet?

Warum auch aufdringlich (oder nicht aufdringlich)? Was sind die Vorteile? Was sind die Nachteile?

Eine aufdringliche Datenstruktur ist eine Struktur, die die Hilfe der Elemente erfordert, die sie speichern möchte, um sie zu speichern.

Lassen Sie mich das umformulieren. Wenn Sie etwas in diese Datenstruktur einfügen, wird diesem „Etwas“ auf irgendeine Weise bewusst, dass es sich in dieser Datenstruktur befindet. Das Hinzufügen des Elements zur Datenstruktur ändert das Element.

Beispielsweise können Sie einen nicht-intrusiven Binärbaum erstellen, bei dem jeder Knoten einen Verweis auf die linken und rechten Teilbäume und einen Verweis auf den Elementwert dieses Knotens hat.

Oder Sie können eine aufdringliche erstellen, bei der die Verweise auf diese Unterbäume in den Wert selbst eingebettet sind.

Ein Beispiel für eine aufdringliche Datenstruktur wäre eine geordnete Liste von Elementen, die veränderbar sind. Wenn sich das Element ändert, muss die Liste neu geordnet werden, sodass das Listenobjekt in die Privatsphäre der Elemente eindringen muss, um ihre Zusammenarbeit zu erreichen. dh. das Element muss wissen, in welcher Liste es sich befindet, und es über Änderungen informieren.

ORM-Systeme drehen sich normalerweise um störende Datenstrukturen, um die Iteration über große Listen von Objekten zu minimieren. Wenn Sie beispielsweise eine Liste aller Mitarbeiter in der Datenbank abrufen, dann den Namen eines von ihnen ändern und ihn wieder in der Datenbank speichern möchten, würde die aufdringliche Mitarbeiterliste informiert, wenn sich das Mitarbeiterobjekt dadurch geändert hat Objekt weiß, in welcher Liste es sich befindet.

Eine nicht aufdringliche Liste würde nicht informiert und müsste selbst herausfinden, was sich geändert hat und wie es sich geändert hat.

In einem intrusiven Container sind die Daten selbst dafür verantwortlich, die notwendigen Informationen für den Container zu speichern. Das bedeutet einerseits, dass der Datentyp je nach Art der Speicherung spezialisiert werden muss, andererseits bedeutet dies, dass die Daten „wissen“, wie sie gespeichert werden, und somit etwas besser optimiert werden können.

Nicht aufdringlich:

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;

Aufdringlich:

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;

Ich persönlich bevorzuge aufdringliches Design wegen seiner Transparenz.