c++ - 推导和模板化使用之间有什么区别？ (请看上下文)

Question

我正在编写各种类型的二叉搜索树(经典、splay、reb-black、avl、Treap、随机等)。

对于每种类型的树，我定义了一个通用类，该类接收节点类型、键类型以及键之间的函数比较作为参数。例如，对于 p AVL 树定义(并实现)以下类:

template <template <typename> class NodeType, typename Key, class Compare>
class Gen_Avl_Tree
{
...
};

这种方法的一个原因是将内存的处理与树的处理分开。树不关心分配或释放节点，只是插入、删除或搜索具有键值的节点；等等其他操作。另一个原因是根据应用情况允许节点有或没有虚拟析构函数的可能性。

然后，我定义两个类如下:

    template <typename Key, class Compare = less<Key>>
struct Avl_Tree : public Gen_Avl_Tree<AvlNode, Key, Compare>
{
  using Base = Gen_Avl_Tree<AvlNode, Key, Compare>;
  using Base::Base;
};

    template <typename Key, class Compare = less<Key>>
struct Avl_Tree_Vtl : public Gen_Avl_Tree<AvlNodeVtl, Key, Compare>
{
  using Base = Gen_Avl_Tree<AvlNodeVtl, Key, Compare>;
  using Base::Base;
};

Avl_Tree 使用“普通”节点，Avl_Tree_Vtl 使用带有虚拟析构函数的节点。两种类型都导出嵌套类型Node。例如:Avl_Tree::Node 和 Avl_Tree_Vtl::Node。

认识到这两个类在功能上是相同的，我认为替换以下内容的先前定义更为实际:

    template <typename Key, class Compare = less<Key>>
using struct Avl_Tree = Gen_Avl_Tree<AvlNode, Key, Compare>;

    template <typename Key, class Compare = less<Key>>
using Avl_Tree_Vtl = Gen_Avl_Tree<AvlNodeVtl, Key, Compare>;

但是，当实例化以下函数时，最后一种方法会导致编译器错误(clang 编译器 3.6):

template <template <typename, class> class TreeType,
      typename Key,
      class Compare = Aleph::less<Key>>
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
                    gsl_rng * r, int n, int k)
{ ... }

来自另一个函数:

template < template <typename /* key */, class /* Compare */> class TreeType>
void test(unsigned long n, gsl_rng * r)
{
...
   tuple<Stat, Stat, int, int> stats = sample_tree(tree, r, i, log(i)/log(2));
...
}

一行:

test<Avl_Tree>(n, r);

导致错误:

timeAllTree.C:190:6: error: no matching function for call to 'sample_tree'
            sample_tree(tree, r, i, log(i)/log(2)); 
            ^~~~~~~~~~~
timeAllTree.C:344:4: note: in instantiation of function template specialization
      'test<Avl_Tree>' requested here
          test<Avl_Tree>(n, r); 
          ^
timeAllTree.C:56:29: note: candidate template ignored: could not match 'type-parameter-0-1'
      against 'AvlNode'
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
                            ^

相比之下，由 Gen_Avl_Tree 派生定义的 Avl_Tree 可以完美编译并运行。

我的问题是，是否有理由相信从 Gen_Avl_Tree 派生的 Avl_Tree 在功能上与使用声明的 Avl_Tree 不同。或者这是编译器的问题

Answer 1

问题是现在类型看起来不同了。最初，你有:

template <typename Key, class Compare = less<Key>>
struct Avl_Tree : public Gen_Avl_Tree<AvlNode, Key, Compare>

因此，Avl_Tree 是 2 种类型的模板:Key 和 Compare。现在，您拥有:

template <typename Key, class Compare = less<Key>>
using struct Avl_Tree = Gen_Avl_Tree<AvlNode, Key, Compare>;

这里，Avl_Tree 只是 Gen_Avl_Tree 的别名，它是 3 类型的模板:NodeType， 键和比较。嗯，NodeType 不是一种类型，它是一个模板，但重点是它是 3 个方面的模板。

现在，你的函数:

template <template <typename, class> class TreeType,
          typename Key,
          class Compare = Aleph::less<Key>>
tuple<Stat, Stat, int, int> sample_tree(TreeType<Key, Compare> & tree, 
                gsl_rng * r, int n, int k)

期望模板采用两种类型。这无法匹配别名 Avl_Tree，因此是完全正确的编译器错误。您可能想做的是:

template <typename Tree>
tuple<Stat, Stat, int, int> sample_tree(Tree& tree, 
                gsl_rng * r, int n, int k)
{
    // or equivalent...
    using Key = typename Tree::Key;
    using Compare = typename Tree::Compare;
    // etc.
}

此版本的函数适用于派生的 Avl_Tree 和别名 Avl_Tree。