What would be the difference between derivation and templatized using? (please see context)

Question

I'm programming various types of binary search trees (classic, splay, reb-black, avl, Treap, randomized, etc).

For each type of tree, I define a generic class that receives as parameters the node type, the key type, and function comparison between the keys. For example, for a p AVL tree define (and implement) the following class:

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

One reason for this approach is to separate the handling of memory of handling of tree. The tree does not care about allocate or deallocate the node simply inserts, deletes, or searches nodes with a key value; and so on with other operations. Another reason is to allow the possibility according to application circumstances that node has or not a virtual destructor.

Then, I define two classes as follows:

    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 uses "normal" nodes and Avl_Tree_Vtl uses nodes with virtual destructor. Both types export the nested type Node. For instances: Avl_Tree::Node and Avl_Tree_Vtl::Node.

Appreciating the fact that both classes are functionally identical, I considered more practical to replace the previous definitions for the following:

    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>;

However, this last approach causes a compiler error (clang compiler 3.6) when the following function is instantiated:

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)
{ ... }

from another function:

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));
...
}

A line as:

test<Avl_Tree>(n, r);

causes the error:

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, 
                            ^

By contrast, Avl_Tree defined by derivation from Gen_Avl_Tree compiles and works perfectly.

My question is if there is reason to believe that Avl_Tree derived from Gen_Avl_Tree is functionally distinct from Avl_Tree declared by using. Or is this a problem with the compiler

Answer 1

The problem is that the types look different now. Originally, you had:

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

So Avl_Tree is a template on 2 types: Key and Compare. Now, you have:

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

Here, Avl_Tree is just an alias for Gen_Avl_Tree which is a template on 3 types: NodeType, Key, and Compare. Well, NodeType isn't a type, it's a template, but the point is it's a template on 3 things.

Now, your function:

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)

expects a template template that takes two types. This cannot match the alias-ed Avl_Tree, hence the complete correct compiler error. What you probably want to do instead is:

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.
}

This version of the function would work for both the derived Avl_Tree and the aliased Avl_Tree.