Arbeiten mit TList

[Bomberbb]

Hallo,

ich möchte eine verkettete Liste von Punkttypen erstellen. Da ich nicht das Rad neu erfinden will, hab ich mit TList angeschaut und versucht , davon meine Liste abzuleiten. Ich bin mir aber nicht sicher, ob das nun von der Logik her so richtig ist.

Was haltet Ihr davon:

Delphi-Quellcode:

Unit listen;

Interface
Uses
  Classes,
  Typendef;

Type
  PunktType = Record
    X : real;
    Y : real;
    lage : byte;
  End;
  pPunktType = ^PunktType;

  { TPunktTypeList class }

  TPunktTypeList = Class(TList)
  Private
  Protected
    Procedure Notify(Ptr : Pointer;Action : TListNotification); Override;
    Function GetPkt(inIndex : Integer) : PunktType;
    Procedure SetPkt(inIndex : Integer;inPkt : Punkttype);
  Public
    Constructor Create;

    Function Add(inPkt : Punkttype) : Integer;
    Function Remove(inIndex : Integer) : Integer;
    Property Items[inIndex : Integer] : Punkttype Read GetPkt Write SetPkt;Default;
  End;

  { TPunktTypeList class }

Implementation

{ TPunktTypeList }

Function TPunktTypeList.Add(inPkt : Punkttype) : Integer;
Var
  p                                     : pPunkttype;
Begin
  New(p);
  Result:=Inherited Add(p);
End;

Constructor TPunktTypeList.Create;
Begin
  Inherited Create;
End;

Function TPunktTypeList.GetPkt(inIndex : Integer) : PunktType;
Begin
  Result:=pPunkttype(Inherited Items[inIndex])^;
End;

Procedure TPunktTypeList.Notify(Ptr : Pointer;Action : TListNotification);
Begin
  If Action = lnDeleted Then
    Dispose(pPunkttype(Ptr));
  Inherited Notify(Ptr, Action);
End;

Function TPunktTypeList.Remove(inIndex : Integer) : Integer;
Begin
  Result:=Inherited Remove(Inherited Items[inIndex]);
End;

Procedure TPunktTypeList.SetPkt(inIndex : Integer;inPkt : Punkttype);
Begin
  pPunkttype(Inherited Items[inIndex])^:=inPkt;
End;
End.

[DeddyH]

Wäre es nicht einfacher, aus dem Record eine Klasse zu machen und die Liste dann von TObjectlist abzuleiten?

[Bomberbb]

Das wäre mir lieber, aber der Punkttype ist der grundlegende Typ in unserem Programm. Da wird das Ersetzen eines Records durch eine Klasse doch ungemein schwierig.

[DeddyH]

Na gut, wenn es nicht anders geht. Allerdings fällt mir auf, dass die Parameter und Rückgabewerte vom Typ PunktType sind, aber eigentlich vom Typ pPunktType sein müssten.

[thkerkmann]

Nö, soweit geht das schon, aber

Delphi-Quellcode:

Function TPunktTypeList.Add(inPkt : Punkttype) : Integer;
Var
  p                                     : pPunkttype;
Begin
  New(p);
  Result:=Inherited Add(p);
End;

ist nicht so gut, da dein inPkt gar nicht in die Liste aufgenommen wird, sonder ein leerer Punkt.

Delphi-Quellcode:

Function TPunktTypeList.Add(inPkt : Punkttype) : Integer;
Var
  p                                     : pPunkttype;
Begin
  New(p);
  p^ := inPkt; // <=== fehlt hier
  Result:=Inherited Add(p);
End;

Gruss

[Edit:thkerkmann]Korrektur Zugweisung [/Edit]

[Bomberbb]

Stimmt. :wall: Ja es ist wieder Zeit sich über sich selbst aufzuregen. Danke!

[grenzgaenger]

du weisst aber schon, dass TList ein Array ist und keine liste ... :roll:

[Bomberbb]

Ja, soweit ich weiß ist eine TList ein Array von Zeigern. Aber es bietet mir die Funktionen einer verketteten Liste und eine bessere Speicherverwaltung als ein dynamisches Array.

[grenzgaenger]

kommt drauf an was du machen willst, willst nur ein paar daten im speicher hin und herschieben, so ist ein array sicher recht gut. nachteilig wird das ganze, wenn du viele daten umordnen willst, bei der verketteten liste musst du nur ein paar pointer umhängen, bei einem array (z.b. tList) den ganzen speicher umschichten.

aber sonst, ist natürlich die TList bequemer ... :-) , ist aber natürlich keine (verkettete) liste ...

Zitat:

Zitat von Bomberbb

eine bessere Speicherverwaltung als ein dynamisches Array.

tut mir leid dich enttäuschen zu müssen, TList ist ein dynamisches Array ... :angel2:

[bernau]

Zitat:

Zitat von grenzgaenger

tut mir leid dich enttäuschen zu müssen, TList ist ein dynamisches Array ... :angel2:

Was wäre denn performanter als eine TList?



Gerd

[mirage228]

Zitat:

Zitat von grenzgaenger

Zitat:

Zitat von Bomberbb

eine bessere Speicherverwaltung als ein dynamisches Array.

tut mir leid dich enttäuschen zu müssen, TList ist ein dynamisches Array ... :angel2:

Ein "gefaketes" dynamisches Array um genau zu sein ;)

[grenzgaenger]

Zitat:

Zitat von bernau

Zitat:

Zitat von grenzgaenger

tut mir leid dich enttäuschen zu müssen, TList ist ein dynamisches Array ... :angel2:

Was wäre denn performanter als eine TList?



Gerd

kommt auf den fall an.

Zitat:

Zitat von mirage228

Zitat:

Zitat von grenzgaenger

Zitat:

Zitat von Bomberbb

eine bessere Speicherverwaltung als ein dynamisches Array.

tut mir leid dich enttäuschen zu müssen, TList ist ein dynamisches Array ... :angel2:

Ein "gefaketes" dynamisches Array um genau zu sein ;)

weshalb gefakte? das ist ein pures dyn Array. nur mit ein paar verwaltungsfunktionen versehen.

[mirage228]

Zitat:

Zitat von grenzgaenger

weshalb gefakte? das ist ein pures dyn Array. nur mit ein paar verwaltungsfunktionen versehen.

Es ist es als statisches Array deklariert (PPointerList oder so) und wird manuell verwaltet... könnte mir schon vorstellen, dass die Klasse aus einer Zeit ohne dynamische Arrays stammt (Delphi 3 und früher) und es daher noch so gelöst wurde... :gruebel:

[grenzgaenger]

Zitat:

Zitat von mirage228

Zitat:

Zitat von grenzgaenger

weshalb gefakte? das ist ein pures dyn Array. nur mit ein paar verwaltungsfunktionen versehen.

Es ist es als statisches Array deklariert (PPointerList oder so) und wird manuell verwaltet... könnte mir schon vorstellen, dass die Klasse aus einer Zeit ohne dynamische Arrays stammt (Delphi 3 und früher) und es daher noch so gelöst wurde... :gruebel:

danke, wieder etwas dazugelernt. ist tatsächlich ein statisches array

[littleDave]

Zitat:

Zitat von mirage228

Ein "gefaketes" dynamisches Array um genau zu sein ;)

Jedoch hat eine TList den Vorteil, dass nur die Pointer auf die Daten in der Liste gespeichert werden. Wenn man jetzt zwei Datensätze austauschen will, muss nur die beiden Pointer vertauscht werden und nicht der Inhalt der Daten. Somit hat TList schon einen großen Geschwindigkeitsvorteil zwischen einem array of irgendwas. Ich glaube, dass TList intern mit Speicherblöcken arbeitet - das array wird - sagen wir mal - mit 64 Pointern initialisiert. Count wird einfach auf 0 gesetzt. Jetzt kann man extrem schnell 64 beliebige Daten in die Liste hinzufügen, ohne dass die Liste vergrößert werden muss. Es wird einfach Count jeweils erhöht und der Pointer wird in den bereits reservierten Speicherbereich geschrieben. Das Löschen von Elementen hat natürlich noch das Problem, dass die danachfolgenden Pointer zurückgeschoben werden müssen, jedoch ist das sehr schnell, da die Pointer in den allermeisten Fällen weniger Speicher verbrauchen als die Daten, auf den die Pointer zeigen.

[Bomberbb]

Meine Intention hierbei war einfach, dass bei Add nur einmal neuer Speicher für den neuen Punkt angefordert wird. Beim Arbeiten mit dynamischen Arrays kann es meines Wissens nach oft sein, dass das komplette Array im Speicher verschoben wird. Wenn ich einige hundert Punkte habe und beim hinzufügen immer ein setlength mache, finde ich das nicht ganz optimal.

Gut das gleiche hätte auch eine verkette Liste getan, aber die hätte ich komplett implementieren müssen...

So nun hab ich mir auch mal ein wenig Quelltext von TList angesehen.
@littleDave
TPointerList ist so definiert:

Delphi-Quellcode:

 MaxListSize = Maxint div 16;

 TPointerList = array[0..MaxListSize - 1] of Pointer;

Also wird gleich für die maximale Länge der Liste Speicher für die Pointer reserviert und dieser auch nicht zur Laufzeit verändert.

Beim Löschen werden nicht alle folgenden Elemente zurückgeschoben, sondern nur der letzte gültige Pointer an die leere Stelle kopiert.

[bernau]

Zitat:

Zitat von Bomberbb

Also wird gleich für die maximale Länge der Liste Speicher für die Pointer reserviert und dieser auch nicht zur Laufzeit verändert.

Ne.Ne. Es wird nur ein Zeiger auf eine TPointerlist-Struktur gelegt. Der Speicher ist nicht reserviert. Wäre schlimm wenn es so wäre, denn maxint hat einen Wert von rund 2.000.000.000 wenn direkt so viele Pointer angelegt würden, dann hast du mit einem Schlag 8GB verbraucht. :-)


Gerd

[littleDave]

TPointerList ist nur ein Dummy-Typ. In TList wird ja einfach PPointerList verwendet. Der Compiler weiß dann, dass der Speicher, auf den der Pointer zeigt, ein array ist. Somit kann man direkt PPointerList[i] aufrufen und der Compiler macht das restliche. Man könnte TPointerList auch definieren als array[0..0] of pointer. Es wird das gleiche rauskommen. Der Typ ist nur dafür da, damit man die eckigen Klammern benutzen kann.

Zitat:

Zitat von Bomberbb

@littleDave
TPointerList ist so definiert:

Delphi-Quellcode:

 MaxListSize = Maxint div 16;

 TPointerList = array[0..MaxListSize - 1] of Pointer;

Also wird gleich für die maximale Länge der Liste Speicher für die Pointer reserviert und dieser auch nicht zur Laufzeit verändert.

Gott sei dank: nein. Schau dir mal die Funktion TList.SetCapacity an. Dort steht ein ReallocMem, womit neuer Speicher angefragt bzw. wieder freigegeben wird.

Zitat:

Zitat von Bomberbb

Beim Löschen werden nicht alle folgenden Elemente zurückgeschoben, sondern nur der letzte gültige Pointer an die leere Stelle kopiert.

Leider auch nein:

Delphi-Quellcode:

procedure TList.Delete(Index: Integer);
begin
  { ... }
  if Index < FCount then
 
    // Mit dem Move-Befehl werden alle Pointer, die nach index kommen, 
    // um eine Position (4 Byte bei 32Bit-Systemen) nach vorne geschoben

    System.Move(FList^[Index + 1], FList^[Index],
      (FCount - Index) * SizeOf(Pointer));

  { ... }
end;

[Bomberbb]

Stimmt auch wieder ...
Nun ja, auf jeden Fall hab ich bei diesem Thread einiges gelernt! :-D
Danke dafür!!!