c++ - 集合和字典( map )的一个类

Question

我想同时实现哈希表和平衡二叉树(特别是 AVL)，以满足集合 和字典( map )的需要。

对于第一个目的，只有一个 Key 类，对于第二个目的，有 Key 和 Data(或 Value)。

这两个版本共享很多功能(尤其是在树的情况下)，所以我真的不想实现两次:

template<class Key> class AVLTree;
template<class Key, class Val> class AVLTree;

我怎样才能优雅地创建一个“HashTable”类和一个“AVLTree”类，使用一个模板签名并将它们用于两个目的(可能使用包装器/派生类 [[Un]Ordered]“Set”和“ map ”？

(不，我不想使用 STL)

谢谢

Answer 1

显而易见的答案是:像 STL 那样做。

引入你需要的最通用的AVLTree形式:

template <class K, class V, class KeyOfValue, class Compare>
class AVLTree;

(参见 _Rb_tree_base 作为引用)。在这种情况下，AVLTree 只存储Value。但出于比较值的原因，它能够通过 KeyOfValue 对象检索 Value 的 Key。

使用它，您的 dictionary 应用程序就很明显了。然后可以通过对 Key 和 Value 使用相同的类型以及对 KeyOfValue 使用同一类型来对 set 进行建模。 (可能你不想每次都把它拼出来。只需为此使用一个包装器模板。)