Указатель на универсальный тип - PullRequest
Новая
       18

Указатель на универсальный тип

5 голосов
/ 27 апреля 2009

В процессе преобразования данной эффективной реализации хэш-карты на основе указателя в общую реализацию хэш-карты я наткнулся на следующую проблему:

У меня есть класс, представляющий хеш-узел (реализация хеш-карты использует двоичное дерево) 

THashNode <KEY_TYPE, VALUE_TYPE> = class
public
  Key      : KEY_TYPE;
  Value    : VALUE_TYPE;
  Left     : THashNode <KEY_TYPE, VALUE_TYPE>;
  Right    : THashNode <KEY_TYPE, VALUE_TYPE>;
end;

В дополнение к этому есть функция, которая должна возвращать указатель на хеш-узел. Я хотел написать 

PHashNode = ^THashNode <KEY_TYPE, VALUE_TYPE>

но это не компилируется (';' ожидается, но '<' найдено). </p>

Как мне получить указатель на универсальный тип?

И обратился к Барри Келли: если вы читаете это: да, это основано на вашей реализации хэш-карты. Вы сами не написали такую ​​общую версию своей реализации? Это сэкономило бы мне немного времени:)

Ответы [ 4 ]

11 голосов
/ 27 апреля 2009

Извините, Smasher. Указатели на открытие универсальных типов не поддерживаются, потому что универсальные типы указателей не поддерживаются, хотя возможно (ошибка компилятора) создавать их при определенных обстоятельствах (особенно указатели на вложенные типы внутри универсального типа); эта «особенность» не может быть удалена в обновлении, если мы нарушаем чей-то код. Ограничение на общие типы указателей должно быть снято в будущем, но я не могу давать обещания, когда.

Если рассматриваемый тип - тот, который я написал в JclStrHashMap (или в древнем HashList блоке), то проще всего воспроизвести его, изменив тип узла на класс и передавая любой двойные указатели как Pointer с соответствующим приведением. Однако, если бы я снова писал этот блок сегодня, я бы не реализовал сегменты как двоичные деревья. У меня появилась возможность написать словарь в модуле Generics.Collections, хотя со всеми остальными время работы компилятора Delphi было слишком коротким, прежде чем отправлять его для надежного контроля качества, а сама поддержка универсальных функций была в движении до довольно позднего времени.

Я бы предпочел реализовать сегменты карты хеш-функции в виде одного из динамических массивов с двойным хешированием, для каждого сегмента или связанных списков ячеек из непрерывного массива, в зависимости от того, что получилось лучше всего при тестировании с использованием представительных данных. Логика заключается в том, что стоимость пропуска кэша для следующих ссылок в дереве / списке должна доминировать над любой разницей в поиске сегментов между деревом и списком с хорошей хэш-функцией. Текущий словарь реализован как прямолинейное зондирование в первую очередь потому, что его было относительно легко реализовать и работать с доступным набором примитивных универсальных операций.

Тем не менее, сегменты двоичного дерева должны были быть эффективным хеджированием против плохих хеш-функций; если бы они были сбалансированными двоичными деревьями (=> даже больше стоимости модификации), они были бы в среднем O (1) и O (log n) в худшем случае.

4 голосов
/ 27 апреля 2009

Чтобы на самом деле ответить на ваш вопрос, вы не можете сделать указатель на универсальный тип, потому что «универсальные типы» не существуют. Вы должны сделать указатель на определенный тип, заполнив параметры типа.

К сожалению, компилятору не нравится находить угловые скобки после ^. Но он примет следующее: 

   TGeneric<T> = record
      value: T;
   end;

   TSpecific = TGeneric<string>;

   PGeneric = ^TSpecific;

Но "PGeneric = ^TGeneric<string>;" выдает ошибку компилятора. Звучит как глюк для меня. Я бы доложил об этом в КК, если бы я был тобой.

Почему вы пытаетесь сделать указатель на объект? Объекты Delphi являются ссылочным типом, поэтому они уже являются указателями. Вы можете просто привести свою ссылку на объект на Pointer, и все хорошо.

4 голосов
/ 27 апреля 2009

Если бы Delphi вообще поддерживал универсальные типы указателей, он должен выглядеть следующим образом: 

type
  PHashNode<K, V> = ^THashNode<K, V>;

То есть упомяните общие параметры слева, где вы объявляете имя типа, а затем используйте эти параметры при построении типа справа.

Однако Delphi не поддерживает это. См. QC 66584 .

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

2 голосов
/ 27 апреля 2009

В модуле Generics.Collections есть общая хэш-карта с именем TDictionary. К сожалению, в данный момент он сильно сломан, но, по-видимому, он будет исправлен в обновлении № 3, которое, по словам Ника Ходжеса .

, должно быть выпущено в течение нескольких дней.
...