C++ template recursion - how to solve ?

Question

Im stuck again with templates.

say, i want to implement a guicell - system. each guicell can contain a number of child-guicells. so far, so tree-structure. in std-c++ i would go for sthg. like:

template <typename T>
class tree
{
public:

    void add (T *o)  { _m_children.push_back (o); }
    void remove (T *o)  { ... };

    list<T*> _m_children;
};

class _cell : public tree<_cell>
{
public:
    _cell ()      { x = 0; y =0; }
    long       x,y;
};

But now i want to go further, and make the cells referencable if the coder wishes so. so i basically implement a refTree - class for that purpose that also takes just pointers (cell) as input.

template <typename T>
class refTree
{
public:
   void add (T *o)   { _ref<T> r = o;  _m_children.push_back (r);  }
   void remove (T *o)       { ... }

   list<_ref<T> > _m_children;
};

Also this is still working fine. using

class _cell : public refTree<_cell>
{
   :
};

no changes to the user-code, but all added cell are now referenced before they are added to the tree.

Good, but now i want to be able to chose on _cell - level which tree-template implementation to use. So this means i have to make the _cell - class a template class that takes a template class as parameter (the chosen tree template).

template <template <typename> class __TyTree = tree>
class Cell : public __TyTree <Cell>  // cannot work - no question, Cell expects input
{
};

And here we got the recursive problem - ofcourse the compiler can't resolve that, because Cell is awaiting a tree - parameter which is expecting a simple-type parameter (which should be a Cell ofc. is awaiting a tree - parameter which is expecting a simple.... ).

You get the picture - what is a proper solution to that kind of problem ?

Answer 1

There is no recursion. Template argument for Cell is __TyTree, not __TyTree<Cell>.

template <template <typename> class __TyTree = tree>
class Cell : public __TyTree <Cell<__TyTree> >
{
};

int main()
{
   Cell          mycell0; // error
   Cell<>        mycell1; // ok. tree is used
   Cell<tree>    mycell2;
   Cell<refTree> mycell3;
}

P.S. You should not use two leading underscores in __TyTree because it is reserved for implementation purposes by C++ Standard.

Answer 2

You have two separate problems: what's in a cell and how cells are connected to each other. You need to use two separate data structures for that. In other words, the right link to break is the inheritance of cell from tree. The tiny amount of memory you save is not worth it - drop the "intrusive" approach. The cell should not be aware of the way the tree holds it.