Redirected to comp.std.c++.

In article <CGDyoE.E7I@dvorak.amd.com>,
Sandeep Srinivasan <sandeep@dvorak.amd.com> wrote:
> I am trying to write a graph class...
> With the following forward declarations...
> SLList is a template class a singly linked list...
> The following class defn.. results in a link error
> ...the linker complains that it cant instantiate
> SLList<Graph> since it does not know its size...

In the future please mention what compiler and version you're using
and please provide complete, even if dummy, code.  Without these
things it's very difficult to debug or provide compiler bug
workarounds.  For example, you didn't show the definition of SLList
but whether the Node class is nested can make a difference with some
compilers.  Btw, are you sure it's the linker, not the compiler,
that's complaining?

The code boils down to a common problem when using templates: when
can/should the compiler expand a class template definition?  Here's
Sandeep's code, stripped down and filled out:

 template<class T>
 struct Node {
    T t;
    Node<T>* next;
 };

 template<class T>
 class SLList {
     Node<T>* head;
 };

 class Graph;

 class Edge {
     SLList<Graph> grphs;
 };

 class Graph {
     SLList<Edge> edgs;
 };

Should the use of SLList<Graph> be legal or is a compiler allowed to
give an error that "Graph is an incomplete type when expanding
Node<Graph>"?  I'm hoping that the code will be legal and I do know
that this issue is being considered by ANSI/ISO.  I strongly recommend
that you let your compiler writers know that you want this code to be
legal.

SLList<Graph> needs to contain a pointer to Node<Graph>.  Since only a
pointer is needed, Node<Graph> does not need to be expanded in order
for the compiler to determine the layout of SLList<Graph>, which is
needed to determine the layout of Edge.  In order for your code and
code like the following to work, the expansion of a class template and
its member functions must be done on a strictly need-to-know basis.

 template<class Letter> class Envelope : public Letter {/*...*/};
 class String {
 public:
    Envelope<String> operator+(const char*);
 };

 template<int DIMS> class Array {
    //...
 public:
    Array<DIMS-1> operator[](int index);
 };
 class Array<0> {/* specialization */};

One workaround is to delay the definition of some class templates.
Declare (but do not define) Node before the definition of SLList and
move the Node definition after the use of SLList<Graph>.  This forces
the compiler to delay expanding Node until it knows the layout of
Graph.  Because this is extremely tedious if you use SLList much, I
think compilers should do this workaround on their own.

> One way around it is to use SLList<Graph&> or SLList<Graph*>
> ..but this means writing new member functions for the SLList
> class to handle pointer and reference template instantiations...

This is probably the best solution for you.  Instead of SLList, you
can write and use SLListP which acts juts like SLList but internally
only stores pointers:

 template<class T>
 class SLListP {
    SLList<void*> list;
 public:
    void add(const T& t);
    T pop();
    ~SLListP();
 };

 template<class T>
 void SLListP<T>::add(const T& t) { list.add(new T(t)); }

 template<class T>
 T SLListP<T>::pop()
    { T* tmp = (T*)list.pop(); T r = *tmp; delete tmp; return r; }

 template<class T>
 SLListP<T>::~SLListP() { delete (T*)list.pop(); }

This should be a viable workaround as long as all the member functions
are not inline.  I've tried Watcom, BC++, Cfront, and g++ and they all
seem to delay the expansion of non-inline template member functions
until the member function is used.

Jamshid Afshar
jamshid@ses.com