C++: templated inherited recursive classes: impossible triple-threat?

Question

So, say you have a base class which is recursive (e.g. a linked list) and a derived class as well. The derived class should reuse the constructor from the base class, because you don't want to write redundant code. You could try the obvious thing, and it won't work:

class Base {
public:

     Base(int size) {
      if (size <= 0) { next = NULL; }
      else { next = new Base(size - 1); }
     }
     void print() { 
      cout << " Base  ";
      if (next != NULL) { next->print(); }
     }
protected:
     Base *next;
};
class Derived: public Base {
public:
     Derived(int size) : Base(size) {} 
     void print() 
      { 
           cout << " Derived ";
           if (next != NULL) 
           { next->print(); }
      }

};
int main()
{

     Derived d2(5);
     d2.print();
     cout << "\n";
     return 0;
}

This won't work - when you instantiate Derived, it constructs one Derived instance, then calls the Base class constructor which pumps out Base instance after Base instance. If you run "main" you'll get:

Derived  Base   Base   Base   Base   Base 

Now, you can get smart and use something like the following design pattern: http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern which will solve all your problems. Check out the following really neat code:

template <class targetT, class recursiveT>
class Base {
public:

     Base(targetT size) {
      if (size <= 0) { next = NULL; }
      else { next = new recursiveT(size - 1); }
     }

     void print() { 
      cout << " Base  ";
      if (next != NULL) 
      { next->print(); }
     }

protected:
     recursiveT *next;
};
class Derived: public Base<int, Derived> {
public:
     Derived(int size) : Base<int, Derived>(size) {} 
     void print() 
      { 
           cout << " Derived ";
           if (next != NULL) 
           { next->print(); }
      }
};
int main()
{

     Derived d1(5);
     d1.print();
     cout << "\n";
     return 0;
}

This passes the test - when we punt from the constructor of Derived back to the constructor of Base, templating causes Base to pump out instances of Derived. Neat! If you run main you'll see the following:

 Derived  Derived  Derived  Derived  Derived  Derived 

Just like you wanted!

Now things get strange. Say that we wanted Base and Derived to be templated themselves; say they are linked lists and we want them to hold arbitrary data.

So we can push this a little further:

template <class targetT, class recursiveT>
class Base {
public:

     Base(targetT size) {
      if (size <= 0) { next = NULL; }
      else { next = new recursiveT(size - 1); }
     }

     void print() { 
      cout << " Base  ";
      if (next != NULL) 
      { next->print(); }
     }

protected:
     recursiveT *next;
};
template <class T>
class Derived: public Base<T, Derived<T> > {
public:
     Derived(int size) : Base<T, Derived<T> >(size) {} 
     void print() 
      { 
           cout << " Derived ";
           if (next != NULL) 
           { next->print(); }
      }
}; 
int main()
{

     Derived<int> d1(5);
     d1.print();
     cout << "\n";
     return 0;
}

But amazingly, compilation now fails with g++:

X.cpp: In member function ‘void Derived<T>::print()’:
X.cpp:33: error: ‘next’ was not declared in this scope

Does anyone see why this should be the case? I'm almost suspecting g++ is wrong, here. I have this problem with gcc version 4.3.2 and gcc version 4.4.1.

Answer 1

The problem is that the base class, Base<T, Derived<T> >, is a dependent base class because it depends on the template parameters, but next is not a dependent name because it doesn't depend on the template parameters. The compiler does not look up nondependent names in dependent base classes.

You can fix this problem by making next dependent by accessing it via this->:

this->next

You can find out more from the C++ FAQ Lite article, "Why am I getting errors when my template-derived-class uses a member it inherits from its template-base-class?"