6

在将给定的基于指针的高效哈希映射实现转换为通用哈希映射实现的过程中，我偶然发现了以下问题：

我有一个代表哈希节点的类（哈希映射实现使用二叉树）

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>

但这不会编译（';' 预期但 '<' 找到）。

如何获得指向泛型类型的指针？

并写给巴里凯利：如果你读到这个：是的，这是基于你的哈希映射实现。您自己没有编写过这样一个通用版本的实现，是吗？那会节省我一些时间:)

4

4 回答 4

11

对不起，粉碎者。不支持指向打开泛型类型的指针，因为不支持泛型指针类型，尽管在某些情况下（特别是指向泛型类型内的嵌套类型的指针）可以创建它们（编译器错误）；如果我们破坏了某人的代码，则无法在更新中删除此“功能”。将来应该取消对泛型指针类型的限制，但我不能承诺何时。

如果有问题的类型是JclStrHashMap我写的（或古老的HashList单元），那么最简单的重现它的方法是将节点类型更改为一个类，并通过Pointer适当的转换传递任何双指针。但是，如果我今天再次编写该单元，我不会将存储桶实现为二叉树。我有机会在 Generics.Collections 单元中编写字典，尽管在交付可靠的 QA 之前，所有其他 Delphi 编译器的工作时间都太紧了，而且通用特性支持本身也在不断变化，直到相当晚。

我更愿意将哈希映射存储桶实现为双散列、每个存储桶的动态数组或连续数组中的单元格链接列表之一，以使用代表性数据的测试中最好的结果为准。逻辑是树/列表中跟随链接的缓存未命中成本应该支配树和具有良好哈希函数的列表之间的桶搜索的任何差异。当前字典被实现为直线探测，主要是因为它相对容易实现并且与可用的原始通用操作集一起使用。

也就是说，二叉树存储桶应该是对不良哈希函数的有效对冲；如果它们是平衡的二叉树（=>甚至更多的修改成本），那么它们平均为 O(1)，最坏情况下的性能为 O(log n)。

于 2009-04-27T14:41:20.747 回答
4

要真正回答您的问题，您不能指向泛型类型，因为“泛型类型”不存在。您必须创建一个指向特定类型的指针，并填写类型参数。

不幸的是，编译器不喜欢在 ^ 之后找到尖括号。但它将接受以下内容：

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

   TSpecific = TGeneric<string>;

   PGeneric = ^TSpecific;

但是“ PGeneric = ^TGeneric<string>;”给出了编译器错误。对我来说听起来像是一个小故障。如果我是你，我会在 QC 报告。

无论如何，您为什么要创建指向对象的指针？Delphi 对象是一种引用类型，因此它们已经是指针。你可以将你的对象引用转换为指针，你很好。

于 2009-04-27T13:59:14.170 回答
4

如果Delphi 完全支持泛型指针类型，它必须看起来像这样：

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

也就是说，在声明类型名称的左侧提及泛型参数，然后在右侧构造类型时使用这些参数。

但是，Delphi不支持这一点。参见QC 66584。

另一方面，我也质疑拥有指向类类型的指针的必要性。通用与否。很少需要它们。

于 2009-04-27T14:04:23.533 回答
2

在 Generics.Collections 单元中有一个名为 TDictionary 的通用哈希映射。不幸的是，它目前已经严重损坏，但它显然会在更新 #3 中得到修复，根据 Nick Hodges 的说法，该更新将在几天内发布。

于 2009-04-27T13:50:42.473 回答