Dependent scope and nested templates

Question

When I compile this:

#ifndef BTREE_H
#define BTREE_H
#include <QList>

template <class T, int degree>
class btree
{
public:
    class node
    {
    public :
        node();
    private:
        node* parent;
        QList<T> values;
        QList<node*> children;
    };
public:
    btree();
    void insert(const T& value);
    node* findLeaf(const T& value);
    void performInsertion(const T& value, node& place);
    //
    node* root;
};
#endif // BTREE_H

Implementation of findLeaf is this:

template <class T, int degree>
btree<T,degree>::node* btree<T,degree>::findLeaf(const T &value)
{
    if(root == NULL)
        return root;
}

This error occurs:

 error: need ‘typename’ before ‘btree<T, degree>::Node’
 because ‘btree<T, degree>’ is a dependent scope

Answer 1

No, this has not to do with C++'s grammar, but with lazy instantiation of C++ templates and two phase lookup.

---

In C++, a dependent name is a name or symbol whose meaning depends on one or more template parameters:

template <typename T>
struct Foo {
    Foo () {
        const int x = 42;
        T::Frob (x);
    }
};

By parsing that snippet alone, without knowin all future values of T, no C++ compiler can deduce whether frob in T is a function name, a type name, something else, or whether it exists at all.

To give an example for why this is relevant, imagine some types you will substitute for T:

struct Vietnam {
    typedef bool Frob; // Frob is the name of a type alias
};    

struct Football {
    void Frob (int) {} // Frob is a function name
};

struct BigVoid {};     // no Frob at all!

Put those into our Foo-template:

int main () {
    Foo<Vietnam> fv;   // Foo::Foo would declare a type
    Foo<Football> ff;  // Foo::Foo would make a function call
    Foo<BigVoid> fbv;  // Foo::Foo is not defined at all
}

Relevant in this is the concept of two-phase lookup. In the first phase, non-dependent code is parsed and compiled:

template <typename T>
struct Foo {
    Foo () {
        const int x = 42; // does not depend on T
        T::Frob (x);      // full check skipped for second phase, only rudimentary checking
    }
};

This first phase is what lets compilers emit error messages in the template definition itself.

The second phase would trigger errors of your template in conjunction with the then-known type T.

Some early C++ compilers would only parse templates once you instantiate them; with those compilers, disambiguation wasn't needed, because at the point of instantiation, the template arguments are known. The problem with this one-phase lookup is that many errors in the template itself won't be detected at all or only late in the compile, because templates are by default instantiated lazily, i.e. only parts of a class-template are expanded that are actually used, plus it gives you more cryptic error messages that possibly root in the template-argument.

So in order for two-phase lookup to work, you must help the compiler. In this case, you must use typename in order to tell the compiler that you mean a type:

template <typename T>
struct Foo {
    Foo () {
        const int x = 42;
        typename T::Frob (x);
    }
};

The compiler now knows that x is a variable of type Frob :)

Answer 2

The C++ grammar is horrendous, and as such it is not possible, when given a template class, to know whether the ::node you refer to is a variable/constant or a type.

The Standard therefore mandates that you use typename before types to remove this ambiguity, and treats all other usages as if it was a variable.

Thus

template <typename T, int degree>
typename btree<T,degree>::node* btree<T,degree>::findLead(T const& value)
^~~~~~~~

is the correct signature for the definition.