Aufdringliche Listen

Question

Ich habe im Internet nicht allzu viele Informationen über sie finden können. Was sind sie und wann werden sie normalerweise verwendet?

Danke.

Answer 1

Eine intrusive 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-intrusive Listen, bei denen die Daten nichts über die Implementierung der Liste (oder eines anderen Containers) wissen.

Answer 2

Ich mag das aufdringliche Modell eigentlich.

1. Es ist besser auf Speicher (nicht viele kleine Zuweisungen für Dinge zu auf andere Dinge zeigen)
2. Sie ermöglicht es Ihnen, ein Objekt in mehreren Containern gleichzeitig zu haben.
3. Es ermöglicht Ihnen, ein Element mit einem Suchmodus (Hash) zu finden, aber dann das nächste Element in lexographischer Reihenfolge zu finden
   • Dies ist no dasselbe wie bei #2, aber es kann mit Steigerung multi_index_container aber beachten Sie, dass multi_index_container hat gewisse Mängel, die bei aufdringlichen Containern keine Rolle spielen.

Aufdringlich ist GUT

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

Answer 3

Es ist erstaunlich, dass so viele Leute dies völlig falsch verstehen (wie die Antwort von Ziezi). Die Leute scheinen die Dinge zu sehr zu verkomplizieren, obwohl es eigentlich ganz einfach ist.

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

Zum Beispiel (aufdringlicher verknüpfter Listenknoten):

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

Beachten Sie, dass die Zeiger next und prev nebeneinander stehen und eindringen auf die privaten Datenfelder der Entität wie z. B. FeldA. Dies "verstößt" gegen die von standardmäßigen verknüpften Listen erzwungene Trennung von Belangen (siehe unten), hat aber den Vorteil, dass der Umfang der Listenwanderung zum Auffinden bestimmter Knoten erheblich reduziert wird und weniger Speicher zugewiesen wird.

In einer intrusiven verknüpften Liste ist die "verknüpfte Liste" selbst oft virtuell, so dass es normalerweise nicht notwendig ist, überhaupt eine verknüpfte Listenstruktur/Klasse zu erstellen.

Stattdessen können Sie einfach einen Kopfzeiger auf das erste Datenelement in einem Eigentümer/Manager speichern. Dieser Manager enthält auch Add/Remove-Funktionen, um Zeiger nach Bedarf zu aktualisieren. Für weitere Informationen siehe https://gameprogrammingpatterns.com/spatial-partition.html

Ein einziges Paar von next/prev-Zeigern bedeutet, dass jedes Objekt nur zu einer Liste gehören kann. Sie können aber natürlich bei 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 (d.h. 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 intrusive verknüpfte Listenknoten und Daten):

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

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

Beachten Sie, dass die next/prev-Zeiger sich nicht einmischen auf die eigentliche Dateneinheit und die Trennung der Bereiche wird beibehalten.

Aktualisierung:

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

Auf diese Weise werden zwar die nächsten/vorherigen Zeiger von den Daten getrennt, doch müssen die Zeiger arithmetisch berechnet werden, um auf die mit der Liste (dem Knoten) verbundenen Daten zugreifen zu können.

Dieser Ansatz fügt meiner Meinung nach unnötige Komplexität hinzu (im Vergleich zum direkten Einbetten von next/prev-Feldern), nur um das zweifelhafte Ziel zu erreichen, die next/prev-Zeiger zu verstecken. Wenn Sie aufdringliche Listen brauchen, halten Sie sie so einfach wie möglich. (Außerdem ist es in Sprachen mit verwaltetem Speicher ohnehin schwierig oder unmöglich, Zeigerarithmetik zu betreiben).

Answer 4

Intrusivlisten sind Listen, bei denen die Objekte selbst Köpfe oder Zellen von Listen sind. Sie sind je nach Kontext gut oder schlecht.

Innerhalb eines definierten Moduls (unsichere Gruppe von Klassen, die zusammenarbeiten) kann es das BESTE Mittel sein, um Beziehungen zwischen Klassen herzustellen. Sie ermöglichen die direkte und vollständige Verwaltung gemeinsamer Beziehungen wie Einzigartigkeit (z.B.: Äpfel kommen nicht zweimal in Apfelbäumen vor, und es wird kein Schlüssel dafür benötigt, und Äpfel gehören nicht zu zwei verschiedenen Bäumen), sie sind in beide Richtungen navigierbar (direkter Zugriff auf einen Apfelbaum bei einem Apfel und auf Äpfel bei einem Apfelbaum). Alle Grundoperationen sind O(1) (keine Suche in einem externen Container).

Aufdringliche Listen sind zwischen zwei Modulen SEHR SCHLECHT. Weil sie zusammen gebunden werden, und Module Rechtfertigung ist die Verwaltung von Code-Unabhängigkeit.

Answer 5

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

I. Intrusionsbehälter.

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. Pro:

• speichert die Objekte selbst.

• beinhaltet keine Speicherverwaltung.

• Iteration ist schneller.

• bessere Ausnahmegarantien.

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

• bessere Speicherlokalisierung.

2. Nachteile:

• enthält zusätzliche Daten für die Containerintegration. (Jeder Lagertyp muss an die Anforderungen des Containers angepasst (modifiziert) werden).
• Vorsicht bei möglichen Nebenwirkungen, wenn der Inhalt des gespeicherten Objekts geändert wird (insbesondere bei assoziativen Containern).
• Verwaltung der Lebensdauer des eingefügten Objekts, unabhängig vom Container.
• Objekt kann möglicherweise entsorgt werden, bevor es aus dem Container gelöscht wird, was zur Ungültigkeit des Iterators führt.
• intrusive Container sind NICHT kopierbar und NICHT zuweisbar.

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

Das Objekt "weiß" nicht und enthält keine Details über den Container, in dem es gespeichert werden soll. Beispiel:

struct Node
{
    T data;
}

1. Pro:

• enthält keine zusätzlichen Informationen über die Containerintegration.
• die vom Container verwaltete Lebensdauer des Objekts. (weniger komplex.)

2. Nachteile:

• speichern Kopien der vom Benutzer übergebenen Werte. (Inplace-Konstruktion möglich.)
• ein Objekt kann nur zu einem Container gehören. (oder der Container sollte Zeiger auf Objekte speichern.)
• Gemeinkosten für die Speicherung von Kopien. (Buchhaltung bei jeder Zuweisung).
• Nicht kopierbare oder nicht bewegliche Objekte können nicht in nicht-intrusiven Containern gespeichert werden.
• kann ein abgeleitetes Objekt nicht speichern und trotzdem seinen ursprünglichen Typ beibehalten. (Slicing - Verlust der Polymorphie).