Aufdringliche Listen

Question 1

Ich konnte online nicht allzu viele Informationen über sie finden. Was sind sie und wann werden sie typischerweise verwendet?

Vielen Dank.

Question 2

Eine aufdringliche Liste ist eine Liste, bei der der Zeiger auf den nächsten Listenknoten in derselben Struktur wie die Knotendaten gespeichert ist. Dies ist normalerweise eine schlechte Sache, da es die Daten an die spezifische Listenimplementierung bindet. Die meisten Klassenbibliotheken (z. B. die C++-Standardbibliothek) verwenden nicht aufdringliche Listen, bei denen die Daten nichts über die Implementierung der Liste (oder eines anderen Containers) wissen.

Question 3

Ich mag eigentlich das aufdringliche Modell.

Es ist besser für den Speicher (nicht viele kleine Zuweisungen für Dinge, die auf andere Dinge zeigen)
Es ermöglicht Ihnen, ein Objekt gleichzeitig in mehreren Containern zu haben.

Es ermöglicht Ihnen, ein Element mit einem Suchmodus (Hash) zu finden, aber dann das nächste Element in lexografischer Reihenfolge zu finden
- Das ist nicht das gleiche wie Nr. 2, aber es kann mit Boosts erreicht werden multi_index_containeraber beachte das multi_index_container weist bestimmte Mängel auf, die bei aufdringlichen Containern keine Probleme darstellen.

Aufdringlich ist gut

…man muss nur wissen, was man tut (was für jeden Container gilt).

Question 4

Es ist überraschend, wie viele Leute das völlig falsch verstehen (wie die Antwort von Ziezi). Die Leute scheinen Dinge zu verkomplizieren, wenn es wirklich ziemlich einfach ist.

In einer aufdringlichen verknüpften Liste gibt es keine explizite ‘Node’-Struktur/Klasse. Stattdessen enthält die ‘Data’-Struktur/Klasse selbst einen Next- und Prev-Zeiger/Verweis auf andere Daten in der verknüpften Liste.

Zum Beispiel (aufdringlicher verknüpfter Listenknoten):

struct Data { 
   Data *next; 
   Data *prev; 
   int fieldA; 
   char * fieldB; 
   float fieldC; 
}

Beachten Sie, wie die next- und prev-Zeiger neben und stehen eindringen auf den privaten Datenfeldern der Entität wie fieldA. Dies ‘verstößt’ gegen die Trennung von Belangen, die durch standardmäßige verknüpfte Listen (siehe unten) erzwungen wird, hat aber Vorteile, da es den Umfang des Durchlaufens von Listen zum Auffinden bestimmter Knoten sowie geringere Speicherzuweisungen erheblich reduziert.

In einer aufdringlichen verketteten Liste ist die ‘verkettete Liste’ selbst oft virtuell, es besteht normalerweise überhaupt keine Notwendigkeit, eine Struktur/Klasse einer verketteten Liste zu erstellen.

Stattdessen können Sie einfach einen Kopfzeiger auf das erste Datenelement in einem Eigentümer/Manager speichern. Dieser Manager enthält auch Funktionen zum Hinzufügen/Entfernen, um Zeiger nach Bedarf zu aktualisieren. Weitere Informationen finden Sie unter https://gameprogrammingpatterns.com/spatial-partition.html

Ein einzelnes Paar von Next/Prev-Zeigern bedeutet, dass jedes Objekt nur zu einer Liste gehören kann. Sie können jedoch natürlich nach Bedarf mehrere Paare von Next/Prev-Zeigern hinzufügen (oder ein Array von Next/Prev-Zeigern definieren), um Objekte in mehreren Listen zu unterstützen.

In einer nicht-intrusiven (dh standardmäßigen) verknüpften Liste sind die Next/Prev-Zeiger Teil einer dedizierten ‘Knoten’-Entität und die eigentliche Daten-Entität einfach ein Feld in diesem Knoten.

Zum Beispiel (nicht aufdringlicher verknüpfter Listenknoten und Daten):

struct Data { 
   int fieldA; 
   char * fieldB; 
   float fieldC; 
}  

struct Node { 
   Node *next; 
   Node *prev; 
   Data *data; 
}

Beachten Sie, wie die next/prev-Zeiger nicht stören auf die eigentliche Datenentität und die Trennung von Bedenken wird beibehalten.

Aktualisieren:

Möglicherweise sehen Sie andere Websites wie z https://www.data-structures-in-practice.com/intrusive-linked-lists/ Verwenden Sie eine ‘List’-Struktur (eigentlich ein Knoten), die next/prev-Zeiger enthält und das einzige aufdringliche Feld in der ‘Data’-Struktur/Klasse ist.

Dies verbirgt zwar die next/prev-Zeiger vor den Daten, leidet jedoch unter der Notwendigkeit, eine Zeigerarithmetik durchzuführen, um einfach auf die tatsächlichen Daten zuzugreifen, die der Liste (Knoten) zugeordnet sind.

Dieser Ansatz fügt meiner Option unnötige Komplexität hinzu (im Gegensatz zum direkten Einbetten von Next/Prev-Feldern), nur um das zweifelhafte Ziel zu erreichen, die Next/Prev-Zeiger zu verbergen. Wenn Sie aufdringliche Listen benötigen, halten Sie sie so einfach wie möglich. (Außerdem ist es in Sprachen mit verwaltetem Speicher sowieso schwierig oder unmöglich, Zeigerarithmetik durchzuführen.)

Question 5

Aufdringliche Listen sind Listen, bei denen Objekte selbst Köpfe oder Zellen von Listen sind. Sie sind gute oder schlechte Dinge, je nach Kontext.

Innerhalb eines definierten Moduls (nicht trennbare Gruppe von Klassen, die zusammenarbeiten) kann dies das BESTE Mittel sein, um Beziehungen zwischen Klassen zu knüpfen. Sie ermöglichen die kostenlose direkte und vollständige Verwaltung gemeinsamer Beziehungen wie Eindeutigkeit (z. B. Äpfel erscheinen nicht zweimal in Apfelbäumen, und dies erfordert keinen Schlüssel dafür, und Äpfel gehören nicht zu zwei verschiedenen Bäumen), sie sind navigierbar in beide Richtungen (direkter Zugang zum Apfelbaum bei einem Apfel und zu Äpfeln bei einem Apfelbaum). Alle Grundoperationen sind O(1) (keine Suche in einem externen Container).

Aufdringliche Listen sind SEHR SCHLECHT zwischen zwei Modulen. Weil sie miteinander verbunden werden und die Modulbegründung die Verwaltung der Codeunabhängigkeit ist.

Question 6

Hier eine kurze Beschreibung, die auch für Listen gilt:

I. Aufdringliche Container.

Das zu speichernde Objekt enthält zusätzliche Informationen, um die Integration in den Container zu ermöglichen. Beispiel:
struct Node
{
    Node* next;   // additional
    Node* prev;   // information 
    T data;
} 
1. Vorteile:

speichert die Objekte selbst.

beinhaltet keine Speicherverwaltung.

Iteration ist schneller.

bessere Ausnahmegarantien.

Vorhersagbarkeit beim Einfügen und Löschen von Objekten. (Es ist keine zusätzliche (nicht vorhersagbare) Speicherverwaltung erforderlich.)

bessere Speicherlokalität.

2. Nachteile:

enthält zusätzliche Daten für die Container-Integration. (Jeder Lagertyp muss an die Behälteranforderungen angepasst (modifiziert) werden.)

Vorsicht vor möglichen Nebeneffekten beim Ändern des Inhalts des gespeicherten Objekts. (insbesondere bei assoziativen Containern.)

Lebenszeitverwaltung des eingefügten Objekts, unabhängig vom Container.

Objekt kann möglicherweise verworfen werden, bevor es aus dem Container gelöscht wird, was zur Invalidierung des Iterators führt.

Aufdringliche Container sind NICHT kopierbar und NICHT zuweisbar.

II. Nicht-intrusive Container (C++-Standardcontainer)

Objekt “kennt” und enthält keine Details über den Container, in dem gespeichert werden soll. Beispiel:
struct Node
{
    T data;
}
1. Vorteile:

enthält keine zusätzlichen Informationen zur Container-Integration.

vom Container verwaltete Objektlebensdauer. (weniger komplex.)

2. Nachteile:

Kopien der vom Benutzer übergebenen Werte speichern. (Inplace-Bauweise möglich.)

ein Objekt kann nur zu einem Container gehören. (oder der Container sollte Zeiger auf Objekte speichern.)

Mehraufwand für das Speichern von Kopien. (Buchführung über jede Zuordnung.)

~~Nicht kopierbare oder nicht bewegliche Objekte KÖNNEN NICHT in unaufdringlichen Behältern aufbewahrt werden.~~

kann abgeleitetes Objekt nicht speichern und dennoch seinen ursprünglichen Typ beibehalten. (Slicing – löst Polymorphismus.)