Dependent Area 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 

The findLeaf implementation is as follows:

 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

The C ++ grammar is horrific, and as such, given a template class, it is impossible to know whether ::node a variable / constant or type.

According to this standard, you agree to use typename in front of types to remove this ambiguity, and treats all other uses as if it were a variable.

In this way,

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

is the correct signature to determine.

Answer 2

No, this is not related to C ++ grammar, but to lazy C ++ template creation and two-phase search.

---

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

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

Parsing this fragment separately, not knowing all future values ​​of T, the C ++ compiler cannot determine if frob in T function name, a type name, something else, or whether it exists at all.

To give an example of why this matters, imagine some types that you will replace with 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 them in 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 search . At the first stage, unsolicited code is analyzed 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 step is what allows compilers to display error messages in the template definition itself.

The second phase will cause errors in your template in combination with the then-known type T.

Some early C ++ compilers will only analyze templates only after they are created; with these compilers, ambiguity is not needed, because at the time of instantiation the template arguments are known. The problem with this single-phase search is that many errors in the template itself will not be detected at all or only at the end of compilation, because the default templates are created lazily, i.e. Only the parts of the class template that are actually used are expanded, plus it gives you more cryptic error messages that may be root in the template argument.

So for two-phase search to work, you must help the compiler. In this case, you should use typename to tell the compiler what you mean by type:

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

Now the compiler knows that x is a variable of type Frob :)