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 ?

Mike Seymour · Accepted Answer · 2014-03-18T10:32:35.243

2

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.

edited Mar 18 '14 at 10:32

answered Mar 18 '14 at 09:38

Mike Seymour

249,747
28
448
644

2

+1, but you could also mention [the inability to implement templates in source files](http://stackoverflow.com/q/495021/1782465). – Angew is no longer proud of SO Mar 18 '14 at 09:44
@Angew: Good point, I didn't notice that it was in a source file. – Mike Seymour Mar 18 '14 at 09:45
I followed your answer and the template errors are gone. But there are some errors in main.cpp. Please see the edit in errors. – Hellboy Mar 18 '14 at 09:50
@Hellboy: `AVLTree` is in a namespace, so you'll need to qualify it as `MYTree::AVLTree` when you're not in that namespace. – Mike Seymour Mar 18 '14 at 09:52
@Mike, How should I declare an object in main.cpp ? Using MYTree::AVLTree tree() is wrong and using MyTree::AVLTree tree gives a compilation error : undefined reference to `MyTree::AVLTree::AVLTree()' – Hellboy Mar 18 '14 at 10:30
@Hellboy: Indeed, with the `()` it declares a function, which is not what you want. It should be `MYTree::AVLTree tree;`. Note the capitalisation of `MYTree` - that must match the namespace name. – Mike Seymour Mar 18 '14 at 10:31
Oh..Capitalisation is not a problem. I wrote it wrong here. Declaring an object like the latter still gives an error. – Hellboy Mar 18 '14 at 10:34
@Hellboy: It sounds like the definition of the default constructor is missing - did you move that into the header with the other members? – Mike Seymour Mar 18 '14 at 10:34
I had to implement the methods in the header file as suggested by Vlad. So, it worked. – Hellboy Mar 18 '14 at 10:36

score 1 · Answer 2 · answered Mar 18 '14 at 09:50

1

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.

answered Mar 18 '14 at 09:50

Vlad from Moscow

301,070
26
186
335

AVLTree tree() doesn't give a compilation error. However, "HI" is not printed which should be printed from the constructor. – Hellboy Mar 18 '14 at 10:07
@Hellboy It does not issue a compilation error because the construction is a valid function declaration. So neither constructor is called. – Vlad from Moscow Mar 18 '14 at 10:17
If I write AVLTree tree; , it causes this error : undefined reference to `MyTree::AVLTree::AVLTree()' – Hellboy Mar 18 '14 at 10:20
@Hellboy I wrote in my post that member function definitions shall be included in the header where the template class is defined. – Vlad from Moscow Mar 18 '14 at 10:30
So, that means I have to implement the method in the AVLTree.h file itself? – Hellboy Mar 18 '14 at 10:32

score 0 · Answer 3 · answered Mar 18 '14 at 09:38

0

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

answered Mar 18 '14 at 09:38

Joel Falcou

6,247
1
17
34

Some programmer dude · Answer 4 · 2014-03-18T09:43:51.677

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.

Error in using templates in C++

4 Answers4