Зависимая область и вложенные шаблоны

Когда я скомпилирую это:

#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

Реализация findLeaf такова:

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

Эта ошибка возникает:

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

Ответ 1

Грамматика С++ ужасающая, и, как таковая, при заданном классе шаблона невозможно знать, относится ли ::node к переменной/константе или типу.

В соответствии с этим стандартом вы обязуетесь использовать typename перед типами, чтобы удалить эту двусмысленность, и обрабатывает все другие способы использования, как если бы это была переменная.

Таким образом,

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

является правильной сигнатурой для определения.

Ответ 2

Нет, это не связано с грамматикой С++, но с ленивым созданием шаблонов С++ и двухфазный поиск.

В С++ зависимое имя - это имя или символ, значение которого зависит от одного или нескольких параметры шаблона:

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

Разбирая этот фрагмент отдельно, не зная всех будущих значений T, компилятор С++ не может определить, является ли frob в T именем функции, именем типа, чем-то другим или существует ли вообще.

Чтобы привести пример, почему это имеет значение, представьте себе некоторые типы, которые вы замените на 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!

Поместите их в наш Foo-шаблон:

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
}

Релевантно в этом состоит понятие двухфазного поиска. На первом этапе, незапрашиваемый код анализируется и компилируется:

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

Этот первый этап - это то, что позволяет компиляторам выдавать сообщения об ошибках в самом определении шаблона.

Вторая фаза вызовет ошибки вашего шаблона в сочетании с тогда известным типом T.

Некоторые ранние компиляторы С++ будут анализировать только шаблоны только после их создания; с этими компиляторами, неоднозначность не нужна, поскольку в момент создания экземпляра аргументы шаблона известны. Проблема с этим однофазным поиском заключается в том, что многие ошибки в самом шаблоне не будут обнаружены вообще или только в конце компиляции, потому что шаблоны по умолчанию создаются лениво, т.е. Расширяются только части шаблона класса, которые фактически используется, плюс он дает вам более загадочные сообщения об ошибках, которые могут быть root в аргументе template.

Итак, чтобы двухфазный поиск работал, вы должны помочь компилятору. В этом случае вы должны использовать typename, чтобы сообщить компилятору, что вы имеете в виду тип:

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

Теперь компилятор знает, что x является переменной типа Frob:)