指向通用类型的指针 [英] Pointer to generic type

问题描述

在将基于指针的基于指针的哈希映射实现转换为通用散列映射实现的过程中，我偶然遇到以下问题：

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

  THashNode< KEY_TYPE，VALUE_TYPE> = class 
 public 
 Key：KEY_TYPE; 
值：VALUE_TYPE; 
左：THashNode< KEY_TYPE，VALUE_TYPE> ;; 
右：THashNode< KEY_TYPE，VALUE_TYPE> ;; 
结束
  

除此之外还有一个函数应该返回一个指向哈希节点的指针。我想写

  PHashNode = ^ THashNode< KEY_TYPE，VALUE_TYPE> 
  

但是没有编译（';''但是'<'找到） p>

如何使用通用类型的指针？

并向Barry Kelly表示：如果您阅读：是的，这是基于你的哈希图实现。你还没有自己写这样的一般版本的实现，有吗？这将节省我一些时间：）

解决方案

对不起，Smasher。不支持打开通用类型的指针，因为通用指针类型不受支持，尽管在某些情况下可能（编译器错误）创建它们（特别是泛型类型中的嵌套类型的指针）;如果我们破坏某人的代码，则此更新中的功能无法删除。通用指针类型的限制在将来应该被删除，但是我不能做出承诺。

如果有问题的类型是 JclStrHashMap 我写了（或古代 HashList 单位），那么最简单的重现方式是将节点类型更改为成为一个类，并通过适当的转换传递任何双指针作为指针。但是，如果我今天再写这个单元，我不会将二进制桶作为二叉树来实现。我有机会在Generics.Collections单元中编写字典，尽管所有其他Delphi编译器的工作时间过于紧张，然后才能发布稳固的质量检查，通用功能支持本身一直在缓和。

我希望实现哈希映射桶作为双重散列，每桶动态数组或连续数组的单元格的链接列表之一，无论从使用代表性数据的测试中得出最佳结果。逻辑是，树/列表中以下链接的高速缓存未命中费用应该支配具有良好散列函数的树和列表之间的桶搜索中的任何差异。目前的字典被实现为直线性探测，主要是因为它相对容易实现并与可用的原始通用操作组合使用。

那就是说，二叉树桶本来应该是一个有效的对冲哈希功能差的工具;如果他们是平衡的二叉树（ => 甚至更多的修改成本），他们将平均为O（1）和O（log n）最坏情况下的性能。 p>

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 :)

解决方案

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.

这篇关于指向通用类型的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！