Стратегия индексации коллекций

Question

У меня есть коллекция TPersistent объектов. Я хочу проиндексировать их по месту в памяти (в качестве основного индекса) и по их свойствам (используя rtti). Коллекция может иметь несколько индексов на основе свойств (на основе разных свойств).

Какова стратегия и структура данных для решения этой проблемы, чтобы я мог удалять недопустимые объекты (те, которые уже были уничтожены) из коллекции без нарушения прав доступа при работе с индексами на основе свойств?

Изменить: чтобы уточнить вещи, я надеюсь реализовать этот вид интерфейсов (класс и методы):

type
  TMyItem=class(TPersistent)
  public
    property HasProp[Name: string]: Boolean read GetHasProp;
    property PropValue[Name: string]: Variant read GetPropValue write SetPropValue;
  end;

  TMyCollection=class(TPersistent)
  private
    FMainList: TSortedList;
    FIndexes : TIndexes;
  public
    function Add(AItem: TMyItem): Integer;
    procedure Extract(AItem: TMyItem);
    procedure Delete(AItem: TMyItem);

    // and new sorted list based on the given property name to the FIndexes
    procedure AddIndex(const APropName: string);
    // remove sorted list correspoding to the given property name from FIndexes
    procedure RemoveIndex(const APropName: string);

    // just to see if the item is in the collection
    function Find(AItem: TMyItem): Boolean;
    // try to find first item which property specified by APropName has value specified by APropValue
    function Find(const APropName: string; const APropValue: Variant; var AItem: TMyItem): Boolean;
  end;

FMainList содержит список указателей на экземпляры TMyItem. Сортировка по приведению указателей к NativeInt. Так что не будет проблем, если я найду недопустимые объекты. Однако в индексе на основе свойств я сортирую TMyItems по значению их свойства. Поэтому EAccessViolation будет вызываться, если я пытаюсь найти запись для недопустимого TMyItem (тот, который уже был уничтожен), так как мне нужно получить значение свойства.

Моя текущая идея для решения этой проблемы заключается в сохранении позиции TMyItem в каждом индексе на основе свойств в основной записи, которая хранится в FMainList. Но этот подход также требует обновления всех позиций каждый раз, когда новый элемент добавляется или удаляется. Это то, чего я хочу избежать. Так есть ли другой лучший механизм?

Answer 1

Подобные вопросы обычно приводят к выбору между сохранением или вычислением индекса, что является синонимом выбора между скоростью и памятью. Это также отчасти зависит от использования: это те, Find рутины часто называют?

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

Лично я бы рассчитывал / получал каждый индекс по запросу. Конечно, потребуется некоторое время, чтобы перебрать все элементы, но когда счет останется, скажем, ниже 100 КБ или даже выше, я уверен, что он не пострадает ни от какой задержки. И когда вы основываете дизайн на TCollection Как и комментарии menjaraz, вам не нужно беспокоиться об удаленных элементах: их не будет.

Обновить:

Поскольку вы хотите искать значения в свойствах с произвольными именами, для которых требуется использование RTTI, эта итерационная задача может немного замедлиться. Чтобы устранить это, я написал эту оптимизацию для вас. Он основан на исключении элементов в операции поиска, которые не имеют свойства. Для этого я храню имена свойств, которые коллекция содержит в своих элементах, а также к какому классу они принадлежат. Единственным ограничением является то, что не может быть повторяющихся имен свойств, но я подозреваю, что вы все равно объедините классы с одинаковыми именами свойств в общем предке. (Однако можно добавить классы с одинаковыми именами свойств, если второе наследуется от первого.)

unit MyCollection;

interface

uses
  Classes, TypInfo;

type
  TMyItem = class(TCollectionItem)
  end;

  TMyCollection = class(TOwnedCollection)
  private
    FPrevItemClass: TClass;
    FPropList: TStringList;
    function GetItem(Index: Integer): TMyItem;
    procedure RegisterItemClass(AClass: TClass);
    procedure SetItem(Index: Integer; Value: TMyItem);
  protected
    procedure Notify(Item: TCollectionItem;
      Action: TCollectionNotification); override;
  public
    constructor Create(AOwner: TPersistent); virtual;
    destructor Destroy; override;
    function Find(AItem: TMyItem): Boolean; overload;
    function Find(const APropName: String; AValue: Variant;
      var AItem: TMyItem): Boolean; overload;
    property Items[Index: Integer]: TMyItem read GetItem write SetItem;
      default;
  end;

implementation

resourcestring
  SDupPropName = 'Duplicate property name. Only classes with unique ' +
                 'property names are supposed to be added to this collection.';

{ TMyCollection }

constructor TMyCollection.Create(AOwner: TPersistent);
begin
  inherited Create(AOwner, TMyItem);
  FPropList := TStringList.Create;
  RegisterItemClass(TMyItem);
end;

destructor TMyCollection.Destroy;
begin
  FPropList.Free;
  inherited Destroy;
end;

function TMyCollection.Find(AItem: TMyItem): Boolean;
var
  I: Integer;
begin
  for I := 0 to Count - 1 do
    if Items[I] = AItem then
    begin
      Result := True;
      Exit;
    end;
  Result := False;
end;

function TMyCollection.Find(const APropName: String; AValue: Variant;
  var AItem: TMyItem): Boolean;
var
  I: Integer;
  ItemClass: TClass;
begin
  Result := False;
  if FPropList.Find(APropName, I) then
  begin
    ItemClass := TClass(FPropList.Objects[I]);
    for I := 0 to Count - 1 do
      if Items[I] is ItemClass then
        if GetPropValue(Items[I], APropName, False) = AValue then
        begin
          AItem := Items[I];
          Result := True;
        end;
  end;
end;

function TMyCollection.GetItem(Index: Integer): TMyItem;
begin
  Result := TMyItem(inherited GetItem(Index));
end;

procedure TMyCollection.Notify(Item: TCollectionItem;
  Action: TCollectionNotification);
begin
  inherited Notify(Item, Action);
  if Action = cnAdded then
    if Item.ClassType <> FPrevItemClass then
      if FPropList.IndexOfObject(TObject(Item.ClassType)) = -1 then
        RegisterItemClass(Item.ClassType)
end;

procedure TMyCollection.RegisterItemClass(AClass: TClass);
var
  PropCount: Integer;
  PropList: PPropList;
  I: Integer;
  J: Integer;
  PropName: String;
begin
  PropCount := GetTypeData(AClass.ClassInfo)^.PropCount;
  if PropCount > 0 then
  try
    GetPropList(AClass.ClassInfo, PropList);
    for I := 0 to PropCount - 1 do
    begin
      PropName := PropList[I].Name;
      if not FPropList.Find(PropName, J) then
      begin
        FPropList.AddObject(PropName, TObject(AClass));
      end
      else
        if not AClass.InheritsFrom(TClass(FPropList.Objects[J])) then
          raise EInvalidOperation.Create(SDupPropName);
    end;
    FPrevItemClass := AClass;
  finally
    FreeMem(PropList);
  end;
end;

procedure TMyCollection.SetItem(Index: Integer; Value: TMyItem);
begin
  inherited SetItem(Index, Value);
end;

end.