Returning a struct pointer from class method

Question

EDIT: Changed example code to code from my project that doesn't work.

I'm writing code in C++, learning templates and got stuck with some problem. There's a class:

template<class T, class Cmp>
class AVLtree {
public:
    AVLtree(const Cmp& _cmp) : root(nullptr), cmp(_cmp) {}
    AVLtree(const AVLtree& ref);
    ~AVLtree();

    AVLtree& operator = (const AVLtree& ref);

    void Add(const T& key);
    void TraverseDfs(void (*visit)(const T& key));
private:
    struct Node {
        Node* left;
        Node* right;
        T key;
        int balance;
        unsigned int height;
        unsigned int inheritence;

        Node(const T& _key) : left(nullptr), right(nullptr), key(_key), balance(0), height(1), inheritence(1) {}
    };
    Node* root;
    Cmp cmp;

    void deleteTree(Node* root);
    void traverse(Node* node, void(*visit) (const T& key));
    Node* addNode(Node* node, const T& key);
    Node* removeNode(Node* p, T key);
    int bfactor(Node* node);
    unsigned int height(Node* node);
    void fixheight(Node* node);
    Node* rotateRight(Node* p);
    Node* rotateLeft(Node* q);
    Node* balance(Node* p);
    Node* findmin(Node* p);
    Node* removemin(Node* p);
};

I want to define method addNode(Node* node, const T& key) out of class and here's what I write:

template<class T, class Cmp>
AVLtree<T, Cmp>::Node* AVLtree<T, Cmp>::addNode(Node* node, const T& key) {
    return new Node(key);
    if (!node) {
        return new Node(key);
    }
    if (cmp(key, node->key)) {
        node->left = addNode(node->left, key);
    }
    else {
        node->right = addNode(node->right, key);
    }
}

Then I try to run program and get such errors and warnings:

warning C4346: 'Node': dependent name is not a type

message : prefix with 'typename' to indicate a type

error C2061: syntax error: identifier 'Node'

error C2143: syntax error: missing ';' before '{'

error C2447: '{': missing function header (old-style formal list?)

It seems that I'm doing something wrong because, if I define method addNode(Node* node, const T& key) inside class, it works fine:

template<class T, class Cmp>
class AVLtree {
public:
   ...
private:
   ...
   Node* addNode(Node* node, const T& key) {
        return new Node(key);
        if (!node) {
            return new Node(key);
        }
        if (cmp(key, node->key)) {
            node->left = addNode(node->left, key);
        }
        else {
            node->right = addNode(node->right, key);
        }
     }
};

Any guesses what might be wrong?

Answer 1

Thanks for answers. Got a solution:

Just added typename before method definition outside of class. It looks like this:

template<class T, class Cmp>
typename AVLtree<T, Cmp>::Node* AVLtree<T, Cmp>::addNode(Node* node, const T& key) {
   ... 
}

It seems that this is some spicialization of Visual Studio because I can see that other compilers work fine with such code without any errors.

Answer 2

It seems that I'm doing something wrong

No. This is a famous "bug/feature" from oldish version of Microsoft's compiler.

Inside the body of C1<T>::Work definition, the name lookup for Node is supposed to find C1<T>::Node. See Name lookup on cppreference.com for more information:

Member function definition

For a name used inside a member function body, a default argument of a member function, exception specification of a member function, or a default member initializer, the scopes searched are the same as in class definition, except that the entire scope of the class is considered, not just the part prior to the declaration that uses the name. For nested classes the entire body of the enclosing class is searched.

Your code is accepted by other compilers, e.g. gcc:

template<class T>
class C1 {
public:
   void CallWork() { Work(); }
private:
   struct Node {
      T x;
   };
   Node* Work();
};

template<class T>
C1<T>::Node* C1<T>::Work()
{
    return new Node{1};
}

live demo