Какой стандартный класс в Делфи позволит хранить и выбирать пары ключ(строка)-значение(строка)-индекс в обе стороны?

Question

Мне нужно хранить связку Ключ(строка) - Индекс(число) - Значение(строка), для того чтобы была возможность:

имея Индекс - выбрать Значение (очень часто, желательно прямой доступ)
имея Индекс - выбрать Ключ (нередко)
имея Ключ - выбрать Значение (редко)

Все пары ключ-ключ уникальные. Индексы монотонные (от 0 до 10 000 например). Данные приходят неотсортированными. Сортировка не важна.

Текущая реализация - 2 симметричных словаря + список:

TKMLibraryKey = string;
TKMLibraryLine = string;

fText: TList<TKMLibraryLine>;
fDictionaryKeyIndex: TDictionary<TKMLibraryKey, Word>;
fDictionaryIndexKey: TDictionary<Word, TKMLibraryKey>;

Занимаемая память - (V, K + I, I + K) * n

Как это можно сделать проще? Может быть есть какой-то словарь с симметричными парами типа Ключ-Ключ? Чтобы можно было ограничиться двумя коллекциями:

fText: TList<TKMLibraryLine>;
TBiDiDictionary<TKMLibraryKey, Word>;

Только на основе стандартных классов, без всяких внеших библиотек.

Answer 1

Я вижу реализацию этого через своего наследника TDictionary, как-то так:

type
  PStringPair = ^TStringPair;
  TStringPair = TPair<string, string>;

  FIndexedDidctionary = class
  private
    FIndexes: TArray<TStringPair>;
    FKeyPairs: TDictionary<string, string>;
    function GetKeyByIndex(Index: Word): string;
    function GetValueByIndex(Index: Word): string;
    function GetValueByKey(const Key: string): string; inline;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Add(Index: Word; const Key, Value: string);
    procedure Remove(Index: Word);
    property KeyByIndex[Index: Word]: string read GetKeyByIndex;
    property ValueByIndex[Index: Word]: string read GetValueByIndex; default;
    property ValueByKey[const Key: string]: string read GetValueByKey;
  end;


{ FIndexedDidctionary }

procedure FIndexedDidctionary.Add(Index: Word; const Key, Value: string);
const
  INDEX_GROW_CHUNK = 1024;
begin
  if Index >= Length(FIndexes) then
    SetLength(FIndexes, (Index div INDEX_GROW_CHUNK + 1) * INDEX_GROW_CHUNK);

  FKeyPairs.Add(Key, Value);
  FIndexes[Index] := TStringPair.Create(Key, Value);
end;

constructor FIndexedDidctionary.Create;
begin
  FKeyPairs := TDictionary<string, string>.Create;
end;

destructor FIndexedDidctionary.Destroy;
begin
  FKeyPairs.Free;
end;

function FIndexedDidctionary.GetKeyByIndex(Index: Word): string;
begin
  if Index >= Length(FIndexes) then
    Exit(''); // при желании можно заменить на raise Exception
  Result := FIndexes[Index].Key;
end;

function FIndexedDidctionary.GetValueByIndex(Index: Word): string;
begin
  if Index >= Length(FIndexes) then
    Exit(''); // при желании можно заменить на raise Exception
  Result := FIndexes[Index].Value;
end;

function FIndexedDidctionary.GetValueByKey(const Key: string): string;
begin
  Result := FKeyPairs[Key];
end;

procedure FIndexedDidctionary.Remove(Index: Word);
begin
  if Index >= Length(FIndexes) then
    Exit; // при желании можно заменить на raise Exception
  var Item := PStringPair(@FIndexes[Index]);
  FKeyPairs.Remove(Item.Key);
  Item.Key := '';
  Item.Value := '';
end;

Код выше - это пример из блокнота, на работоспособность не проверял. Подразумевается только добавление и удаление элементов по индексу, но не изменение существующих.

Answer 2

@Alekcvp натолкнул на мысль.

Первым делом, конечно, можно слегка оптимизировать до:

TKMLibraryKey = string;
TKMLibraryLine = string;

fText: TList<TKMLibraryLine>;
fIndexKey: TList<TKMLibraryKey>;
fDictionaryKeyIndex: TDictionary<TKMLibraryKey, Word>;

Далее, по мотивам того что предлагает @Alekcvp (только без дублирования строк):

fText: TList<TPair<TKMLibraryKey, TKMLibraryLine>>;
fDictionaryKeyIndex: TDictionary<TKMLibraryKey, Word>;

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

Занимаемая память - (V, K, K + I) * n

БЛОГ НА HUSL

Какой стандартный класс в Делфи позволит хранить и выбирать пары ключ(строка)-значение(строка)-индекс в обе стороны?

Ответы (2 шт):