delphidelphi-2006tlist

What is an efficient way of deleting a large block of items from the start of a TList in Delphi


Delete (0) from a TList is expensive because all the subsequent items need to be moved down. If I need to delete a large number of items from the start of an even larger list what's the fastest way?


Solution

  • Deleting a large range of elements from the beginning of a TList is expensive. Although the class name flatters to deceive, a TList is in fact an array. In TList there is no facility to delete a range–each item must be deleted individually and then the rest of the list is moved down. For a large range that's going to provoke an awful lot of reallocations and full list moves.

    If you had a more modern Delphi you could use the generic list class TList<T> and avail yourself of the DeleteRange method. The documentation includes this vital note:

    This is an O(ACount) operation.

    In Delphi 2006 you can write something with equivalent performance characteristics like this:

    procedure DeleteRange(List: TList; AIndex, ACount: Integer);
    var
      i: Integer;
      NewCount: Integer;
    begin
      NewCount := List.Count-ACount;
      Assert(AIndex>=0);
      Assert(ACount>=0);
      Assert(NewCount>=0);
      for i := AIndex to NewCount-1 do
        List[i] := List[i+ACount]
      List.Count := NewCount;
    end;