Сортируемый список объектов с O (1) удалением первого элемента - PullRequest
1 голос
/ 08 января 2012

Для Delphi (2009 или новее) есть реализация списка объектов со следующими двумя функциями:

  • позволяет настраивать сортировку

  • выполняет удаление первого элемента списка за O (1) раз

1 Ответ

4 голосов
/ 08 января 2012

Нет ничего, что поставляется с продуктом, который обладает этими свойствами. Очевидное и простое решение заключается в обратном индексировании списка, чтобы при удалении первого элемента код фактически удалял последний элемент базового списка.

Чтобы дать вам представление о том, к чему я стремлюсь, вот набросок начала очень простой реализации. Чтобы довести дело до конца, потребуется много работы.

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;

Я предполагаю, что вы хотите использовать массив в качестве основного хранилища, потому что я предполагаю, что вы хотите O (1) произвольный доступ.

Все остальные функции, которые вам нужны, которые используют параметр индекса, также должны вызывать ReversedIndex. Самое сложное, что можно написать - это процедуры сортировки. Классы в Generics.Collections используют IComparer<T>. Вы сделали бы то же самое, но затем делегировали бы сортировку FList, передав локально построенный компаратор IComparer<T>, который перевернул результаты компаратора, предоставленные вызывающей стороной.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...