Ein Element aus der Mitte eines dynamischen Arrays löschen

[Benni]

Servus Leute,

nehmen wir mal an, wir haben ein dynamisches Array, z.B.:

<pre>var bsp: array of integer;</pre>

Nachdem dieses Array nun mit SetLength(bsp, 20000) gesetzt wurde, wie entferne ich dann z.B. Element 9485, so dass danach noch 19999 Elemente da sind? Geht dies ohne viel "umherkopieren" im Speicher?

Ich verwende einen Record, der einiges an Daten enthält. Wenn ich nun alle Elemente nach Nr. 9485 um eines nach vorne kopiere und dann Element 20000 mit SetLength lösche, könnte das im Extremfall einiges an Zeit in Anspruch nehmen. Gibt es eine einfachere Variante?

Vielen Dank!

Ciao

Benjamin Heil

[Robert Marquardt]

Es gab Programmiersprachen mit denen man das und noch merkwuerdgeres machen konnte, aber bei Delphi heisst es kopieren

[Ulrich Gerhardt]

Wenn du vorhast, öfter was "mitten im Array" zu löschen oder einzufügen, solltest du statt des Arrays eine (verkettete) Liste in Betracht ziehen (nicht zu verwechseln mit der TList von Delphi).
<br>Ciao, Uli

[Robert Marquardt]

Na mit einer TList geht es auch. Die macht die Kopiererei selber

[Jens Schumann]

Hallo Robert,<br>hier muß ich Ulrich recht geben. Bei einer verketteten Liste wird das Element Xn gelöscht und der Zeiger auf das nächste Element in Xn-1 auf Xn+1 gesetzt. D.h. es werden nur zwei Zeiger gesetzt und nix kopiert

[Hagen Reddmann]

Im Falle von einer einfach verketteten Liste muss nur ein Zeiger modifiziert werden, allerdings muß ersteinmal die korrekte Vorgängernode ermittelt werden. Dies kann man nur indem man von der Root=ersten Node bis zur zu entfernenden Node die List durchiteriert. Dadurch entsteht bei sehr großen Listen ein enormer Overhead. Man nimmt dann doppelt verlinkte Listen, in denen jede Node einen zeiger auf die nächste und vorherige Node enthält. In diesem Falle entfällt das Iterierien, man muß nun 2 Zeiger modifizieren und pro Node wird der Speicherverbrauch um einen Zeiger erhöht.<br>

Allerdings meinte Robert das normale TList Object, und dieses arbeitet NICHT als verkettete List. In TList wird einfach ein dynamisch alloziertes array of Pointer benutzt. KEINE dynamisches array sondern die Allozierung wird durch TList per Hand erledigt. Dies bringt enorme Vorteile da TList eben mehr Speicher reserviert (in Blocks) als eigentlich nötig wären. Damit ist TList bei wiederholten Einfügungen/Entfernungen von Zeigern den dynamischen Arrays klar im Vorteil. Bei dynamischen Arrays hat Borland leider keine solchen "Overhead" eingebaut, was dazu führt das jede Längenänderung eines dynm. arrays auch immer eine Reallokation des Speichers nötig macht.<br>
Bei TList wie auch dynamischen Arrays jedesmal beim Einfügen/Entfernen auch kompiert werden. Nur beim "Anhängen" eines Elementes entfält das Kopieren, und bei TList mit hoher Wahrscheinlichkeit auch das Reallozieren des Speichers.<br>

Im Falle von verketteten Listen wird nichts kopiert, sondern nur der Speicher jeder Node muß beim Einfügen alloziert werden und beim Entfernen dealloziert werden. z.B. eine verkettet List of Integer könnte so definiert sein:

<pre>

type
PNode = ^TNode;
TNode = packed record
Prev: PNode;
Next: PNode;
Data: Integer;
end;<br>

var
Root: PNode;

</pre>

Wie man sieht wird für ein Daten-Integer zwei zusätzliche Zeiger benötigt. Mehr Speed braucht meistens mehr Speicher, weniger Speicherverbrauch -> weniger Speed.<br>
Im Normalfalle haben alle Nodes den gleichen Speicherbedarf. Das führt dazu das man die Allokation des notwendigen Speichers einer Node in Gruppen erledigt. Statt nun immer eine Node zu allozieren oder zu deallozieren werden zwei Nodebäume verwaltet, sprich zwei Roots. Die ein enthält eine List auf alle momentan benutzen Nodes und die andere Root zeigt auf die unbenutzen Nodes. Wird nun eine Node eingefügt so wird erstmal die erste Node aus der unbenutzen Liste entfernt und diese dann in die benutze Liste eingefügt. Beim Entfernen passiert alle umgekehrt. Nun haben wir beim Entfernen 5 Zeiger zu modifizieren, Node.Prev.Next := Node.Next, Node.Next.Prev := Node.Prev; FreeRoot.Prev := Node; Node.Next := FreeRoot; FreeRoot := Node;<br>

Gruß Hage

[Minz]

Hallo Benni,

sollte vorher noch geklärt werden, ob die Reihenfolge deiner Elemente wichtig ist

Gruß Min