Declaring a struct in a template class, undefined

Question

I'm currently trying to implement a sort algorithm in a list template class using node structures private to the list class. I'm using a few private recursive functions which return a pointer to a node type which causes g++ to give me a declaration error. Here's a sample of what I have -

template<class T>
class SList
{
private:
    struct NODE
    {
        T* elem;
        NODE* next;
    } *_head, *_tail;

NODE* sort(NODE* node);

public:
    //other declarations...

}

template<class T>
NODE* SList<T>::sort(NODE* node) //Error: 'NODE' does not name a type
{
    //sorting algorithm
}

Is this a limitation of c++ or am I missing something?

Answer 1

Below works fine:

template<class T>
typename SList<T>::NODE* SList<T>::sort(typename SList<T>::NODE* node)
^^^^^^^^^^^^^^^^^^^                     ^^^^^^^^^^^^^^^^^^^

Is this a limitation of c++

No. Because there can be any structure/type named NODE outside the scope of SList<>; so actually it's a facility which C++ provides you where you can have same name types in different scope.

"Why I need keyword typename" can be found here.

Answer 2

The type you want to refer to is within SList, thus you must refer to it as such:

template<class T>
typename SList<T>::NODE* SList<T>::sort(typename SList<T>::NODE* node);

Answer 3

Since Node is an internal class you need to tell the compiler where Node's definition comes from.

Furthermore, Node's definition changes depending on what SList's template parameter is (it is a dependent type)

So you have to explicitly refer to Node as such:

template<class T>
typename SList<T>::NODE* SList<T>::sort(typename SList<T>::NODE* node) 
{
    //sorting algorithm
}

• Note the typename because Node is a dependent type (it depends on the type of SList)
• Note the SList<T>::Node because Node is a type dependent on SList's type.