Error in using templates in C++

Question

I want to implement an AVL Tree using templates in C++. The header file, C++ file and the main file are as below :

AVLTree.h

#include <iostream>

using namespace std;

namespace MYTree
{
    template <class T>
    class AVLTree
    {
        public:
            struct AVLNode
            {
                struct AVLNode *left;
                struct AVLNode *right;
                struct AVLNode *parent;
                int balanceFactor;
            };

            //Constructor
            AVLTree();
            //Variables
            AVLNode *root;
            //Methods
            AVLNode<T> *lookup(const T &key);
            AVLNode<T> *insert(const T &key);
            void remove(const T &key);
    };
}

AVLTree.cpp

#include "AVLTree.h"

#include <iostream>

using namespace std;

template <class T>
AVLTree<T>::AVLTree()
{
    cout <<"HI\n";
}


template <class T>
AVLNode<T>* AVLTree<T>::lookup(const T &key)
{
}

template <class T>
AVLNode<T>* AVLTree<T>::insert(const T &key)
{
}

template <class T>
void AVLTree<T>::remove(const T &key)
{
}

main.cpp

#include "AVLTree.h"

#include <iostream>

using namespace std;

int main()
{
    AVLTree<int> tree();

    return 0;
}

When I compile the main.cpp, I get the following errors :

In file included from main.cpp:1:
AVLTree.h:27: error: `MyTree::Node' is not a template
AVLTree.h:28: error: `MyTree::Node' is not a template
AVLTree.h:30: confused by earlier errors, bailing out

Edit :

main.cpp:9: error: `AVLTree' undeclared (first use this function)
main.cpp:9: error: (Each undeclared identifier is reported only once for each function it appears in.)
main.cpp:9: error: expected primary-expression before "int"
main.cpp:9: error: expected `;' before "int"

I am using templates for the very first time. Can someone help me ?

Answer 1

AVLNode isn't a template; it's a regular class nested within a template. So within the template, just use the class name:

AVLNode *lookup(const T &key);

and outside the template, qualify it with the template's scope:

template <class T>
AVLTree<T>::AVLNode* AVLTree<T>::lookup(const T &key)
{
}

You'll also need to fix the definition of AVLNode; you're currently declaring Node to be a data member of AVLTree (which you don't want), and attempt to define a type AVLNode to be an alias for Node (which won't compile since Node isn't a type). Just define a class type, with no data members or typedefs:

struct AVLNode
{
    AVLNode *left;
    AVLNode *right;
    AVLNode *parent;
    int balanceFactor;
};

As noted in the comments, templates (including member functions of class templates) usually need to be defined in a header, as the definition must be available wherever it's used.

You'll also need to make sure the definitions are in the correct namespace, and qualify the template name appropriately (MYTree::AVLNode) when you're not in that namespace.

AVLTree<int> tree(); declares a function; remove the () to create a default-initialised object.

Finally, don't do using namespace std; in the global namespace, as it can lead to confusing name conflicts.

Answer 2

This typedef

       typedef struct Node AVLNode;

is invalid. First of all you have no defined structure Node and secondly this typedef hides declaration of name struct AVLnode

It shall be removed. The error messages are results of this typedef because in this declarations

        AVLNode<T> *lookup(const T &key);
        AVLNode<T> *insert(const T &key);

you specified name AVLNode as a template name.

Nevertheless your code contains other errors. Template member functions have to be placed in the same header file where the template class is defined. Otherwise you will get linker errors that references are undefined.

This statement in main

AVLTree<int> tree();

is not a definition of an object. It is a function declaration that has return type AVLTree<int> and has no parameters.

Answer 3

you use AVLNode<T> but AVLNode is not a template, as the message say.

Answer 4

With this:

struct AVLnode
{
    ...
}Node;

you declare a member variable named Node.

When you later do

typedef struct Node AVLNode;

you try to use the member variable as a structure.

Remember that you are programming C++, where structure names can be used as types just the same as class names.

You also try to use AVLNode as a template in e.g.

AVLNode<T> *lookup(const T &key);

But just as the error messages says, the AVLNode structure is not a templated structure.