New List Class – Implementation

A problem occurred during the update of the list class. It was desired that the append, insert and remove functions to not be inline functions. Defining them in the class automatically makes them inline. Therefore, they were defined outside the main List class. They are still in the list.h include file, but because they are template functions, no code is generated until a class is instantiated and the function is used.

The problem occurred for the functions that return an element pointer. The List class contains the public Element structure (next and previous element pointers and the generic value of type T). The Element structure needs to be defined within the List class since it contains the type T of the template. Inside the class definition, the Element structure can be simply referred to as “Element” or “Element *” for pointers. Outside the function, the syntax “List<type>::Element” and “List<type>::Element *” is needed where “type” is the instantiated type. For defining template functions “List<T>::Element” and “List<T>::Element *” are used.

Therefore, to define a template function that returns and Element pointer and takes an Element pointer as an argument would appear that it should be written as:

    template <class T> List<T>::Element *List<T>::fun(List<T>::Element *element)

Unfortunately, the compiler gave the error: error: expected constructor, destructor, or type conversion before '*' token. The problem was with the return value since the argument syntax was in the List class previously causing no issues.

No help was obtained from the Borland C++ 4.5 Programmer's Guide manual (the Language Structure section is a very good guide for C++). Next the ANSI-ISO C++ PDF checked to see if there was a way to define these functions in the main List class definition but tell the compiler not to make them inline.

No way to prevent inlining was found, but the “typename” C++ keyword was discovered instead (apparently this keyword came about after the Borland manual was written). It turns out that certain syntax with templates can be ambiguous. Take the example:

    int N;
    template <class T> func(void)
    {
  T::A *N;
  . . .
    }

The A could be a type within T (like Element within List) or could be a static data member of T. If A is a type within T, then N would be a pointer to this type (the global N would be then inaccessible within the function). If A is a static data member of T, then the statement above would be the multiplication of the static member A::T times the global N. By default, the compiler assumes that the statement is multiplication (technically this is a valid C++ statement, though it doesn't actually do anything).

So it turns out that for the function statement, the compiler was treating the “*” as multiplication, hence the error message. The typename keyword overrides this default. So for the example, the typename keyword would be used:

    typename T::A *N;

To tell the compiler that N should be a pointer to T::A. Therefore, for the function problem, the line would be written as:

    template <class T> typename List<T>::Element *List<T>::fun(. . .)

Which tells the compiler that “List<T>::Element *” is a type and not something else. Problem solved.