liste d'objets triables avec O (1) suppression du premier élément

Question

Pour Delphi (2009 ou plus récent), est-il une mise en œuvre d'une liste d'objets avec ces deux caractéristiques:

• permet de trier sur mesure

• effectue des suppressions du premier élément de la liste en O (1) temps

Answer 1

Il n'y a rien qui est livré avec le produit qui a ces propriétés. La solution évidente et simple est d'inverser l'indexation de la liste de sorte que lorsque vous supprimez le premier élément, le code efface réellement le dernier élément de la liste sous-jacente.

Pour vous donner une idée de ce que je veux dire, voici l'esquisse des débuts d'une implémentation très basique. Il faudrait beaucoup de travail à mener à terme.

type 
    TMyObjectList<T> = class 
    private 
    FList: TObjectList<T>; 
    function GetItem(Index: Integer): T; 
    function ReversedIndex(Index: Integer): Integer; 
    public 
    constructor Create; 
    destructor Destroy; override; 
    property Items[Index: Integer]: T read GetItem; default; 
    procedure Delete(Index: Integer); 
    end; 

function TMyObjectList<T>.Create; 
begin 
    inherited; 
    FList := TObjectList<T>.Create; 
end; 

destructor TMyObjectList<T>.Destroy; 
begin 
    FList.Free;//don't use FreeAndNil because it offends Nick Hodges ;-) 
    inherited; 
end; 

function TMyObjectList<T>.ReversedIndex(Index: Integer): Integer; 
begin 
    Result := Count-1-Index; 
end; 

function TMyObjectList<T>.GetItem(Index: Integer): T; 
begin 
    Result := FList[ReversedIndex(Index)]; 
end; 

procedure TMyObjectList<T>.Delete(Index: Integer); 
begin 
    FList.Delete(ReversedIndex(Index)); 
end; 

Je suppose que vous voulez un tableau que votre stockage sous-jacent parce que je suppose que vous voulez O (1) accès aléatoire.

Toutes les autres fonctions dont vous avez besoin, qui utilisent un paramètre d'index, doivent également appeler ReversedIndex. La chose la plus difficile à écrire serait les routines de tri. Les classes dans Generics.Collections utilisent IComparer<T>. Vous feriez la même chose, mais délégueriez le tri à FList en passant un comparateur local IComparer<T> qui a annulé les résultats du comparateur fourni par l'appelant.