Pointer to generic type

Pointer to generic type

落墨 发布于 2021-11-28 字数 1042 浏览 516 回复 4 原文

In the process of transforming a given efficient pointer-based hash map implementation into a generic hash map implementation, I stumbled across the following problem:

I have a class representing a hash node (the hash map implementation uses a binary tree)

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;

In addition to that there is a function that should return a pointer to a hash node. I wanted to write

PHashNode = ^THashNode <KEY_TYPE, VALUE_TYPE>

but that doesn't compile (';' expected but '<' found).

How can I have a pointer to a generic type?

And adressed to Barry Kelly: if you read this: yes, this is based on your hash map implementation. You haven't written such a generic version of your implementation yourself, have you? That would save me some time :)

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

陌路黄昏 2022-06-07 4 楼

There's a generic hash map called TDictionary in the Generics.Collections unit. Unfortunately, it's badly broken at the moment, but it's apparently going to be fixed in update #3, which is due out within a matter of days, according to Nick Hodges.

很酷不放纵 2022-06-07 3 楼

If Delphi supported generic pointer types at all, it would have to look like this:

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

That is, mention the generic parameters on the left side where you declare the name of the type, and then use those parameters in constructing the type on the right.

However, Delphi does not support that. See QC 66584.

On the other hand, I'd also question the necessity of having a pointer to a class type at all. Generic or not. they are needed only very rarely.

鸵鸟症 2022-06-07 2 楼

To actually answer your question, you can't make a pointer to a generic type, because "generic types" don't exist. You have to make a pointer to a specific type, with the type parameters filled in.

Unfortunately, the compiler doesn't like finding angle brackets after a ^. But it will accept the following:

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

   TSpecific = TGeneric<string>;

   PGeneric = ^TSpecific;

But "PGeneric = ^TGeneric<string>;" gives a compiler error. Sounds like a glitch to me. I'd report that over at QC if I was you.

Why are you trying to make a pointer to an object, anyway? Delphi objects are a reference type, so they're pointers already. You can just cast your object reference to Pointer and you're good.

熟人话多 2022-06-07 1 楼

Sorry, Smasher. Pointers to open generic types are not supported because generic pointer types are not supported, although it is possible (compiler bug) to create them in certain circumstances (particularly pointers to nested types inside a generic type); this "feature" can't be removed in an update in case we break someone's code. The limitation on generic pointer types ought to be removed in the future, but I can't make promises when.

If the type in question is the one in JclStrHashMap I wrote (or the ancient HashList unit), well, the easiest way to reproduce it would be to change the node type to be a class and pass around any double-pointers as Pointer with appropriate casting. However, if I were writing that unit again today, I would not implement buckets as binary trees. I got the opportunity to write the dictionary in the Generics.Collections unit, though with all the other Delphi compiler work time was too tight before shipping for solid QA, and generic feature support itself was in flux until fairly late.

I would prefer to implement the hash map buckets as one of double-hashing, per-bucket dynamic arrays or linked lists of cells from a contiguous array, whichever came out best from tests using representative data. The logic is that cache miss cost of following links in tree/list ought to dominate any difference in bucket search between tree and list with a good hash function. The current dictionary is implemented as straight linear probing primarily because it was relatively easy to implement and worked with the available set of primitive generic operations.

That said, the binary tree buckets should have been an effective hedge against poor hash functions; if they were balanced binary trees (=> even more modification cost), they would be O(1) on average and O(log n) worst case performance.