[comp.std.c++, this news article first appeared in comp.lang.c++, and
debates the merits of using STL in a recursive looking style, instead of the
traditional pointer way, ie this:
#include <list>
class Node
  {
  list<Node> children;
  }

instead of:
class Node
  {
  list<Node*> children;
  }

Since my compiler (VC++ 5) does not even support the recursive looking
format, and since STL could be implemented to run the above format more or
less efficiently I decided to forward to comp.std.c++.
You may want to start from the end.]

Second reply:

Thank you for your input.  Which compiler were you using, or were you saying
that the various examples  theoretically should compile?

>Your compiler is evidently trying to instantiate Foo<A>::Bar a
>little too early.  But it's not a serious bug because you should
>not be declaring potentially recursive types anyway.
> ...
> Use pointers.  Besides, when you remove nodes from the tree
>and you want to rearrange the tree, you'll only have to move around
>a bunch of pointers.
>...
>But it is not good style to program this way.  In general, a class
>SomeClass<T> will instantiate objects of type T, use typedefs or
>nested structs defined in class T.


I grant that there are more traditional (for C/C++) ways to solve this
problem (ie use pointers).  The way I proposed reminds me more of
programming languages like LISP.  However, there are advantages to my
approach:

1. Simplicity.  A significant number of bugs in C++ are due to memory
allocation problems.  By allowing a "stable" piece of software like STL to
do my memory allocation, I increase the likelyhood that my code will be
correct.  Also, the code is much more succinct (at least between my 2
implementations).

2. Memory:  Less Heap fragmentation, etc.

3. Efficiency?:  My original problem had no efficiency requirements which is
why I thought of this solution.  However, when writing this message I
realised that for certain problem sets (many insert/ removal allocations,
few moves) this could be more efficient because new and delete are normally
fairly expensive operations.


First reply:
Siemel Naran wrote in message ...
>On 06 Oct 1998 12:18:20 PDT, vxir@concentric.net <vxir@concentric.net>
wrote:
>
>>template <class T> class FooT
>>  {
>>public:
>>  class Bar
>>    {
>>    public:
>>    T var;
>>    };
>>  };
>
>OK.
>
>
>>Notice that this template never actually declares a member variable
>>of type T, because it never declares a member variable of type Bar (and
the
>>only instance of T is in Bar).  This means that I could theoretically do
the
>>following:
>>
>>class A
>>  {
>>  public:
>>  FooT<A> var;
>>  };
>
>This code should compile.  In particular, all three of the following
>quantities are  well defined:
>   sizeof(FooT<A>)
>   sizeof(A)
>   sizeof(Foo<T>::Bar)
>
>
>>However, since it does not, the code is theoretically possible.  Yet on my
>>compiler (VC++ 5.0)  I receive the error "Bar" uses undefined class "A".
>
>When in class A you say "FooT<A> var", the compiler instantiates
>Foo<A>.  Typedefs and member variables in Foo<A> will be expanded.
>So if template class Foo<T> declares member/static variables of type
>T, uses functions/objects defined in class T, or even uses a typedef
>defined in class T, you will get an error something like this:
>"undefined/incomplete type 'class A' needed for instantiation of
>Foo<A>".  Nested classes will not be expanded though.  So Foo<A>::Bar
>will not be instantiated.
>
>Your compiler is evidently trying to instantiate Foo<A>::Bar a
>little too early.  But it's not a serious bug because you should
>not be declaring potentially recursive types anyway.
>
>
>
>>This relates to STL, because it would be very useful to be able to do this
>>with many of its classes.  For example,  here is an implementation of a
>>tree:
>
>Use pointers.  Besides, when you remove nodes from the tree and you want
>to rearrange the tree, you'll only have to move around a bunch of
>pointers.
>
>The only problem now is that you have to manage deletion of the objects
>manually.  This is not a big deal though.  BTW, I think it is better style
>to do the deletion of the Node objects in the dtor of the Tree object.
>Don't make a recursive dtor, where each Node calls delete on each of
>its children nodes.
>
>
>>#include <list>
>>
>>class Node
>>  {
>>  list<Node> children;
>>  }
>
>This compiles.  If a class SomeClass<T> is implemented so that it
>only contains/instantiates objects of type T* then this works.  In
>particular, sizeof(T*) is known -- all pointers to user defined
>classes have the same sizeof, and pointers to the builtin types
>have sizeof's known by the compiler.
>
>But it is not good style to program this way.  In general, a class
>SomeClass<T> will instantiate objects of type T, use typedefs or
>nested structs defined in class T.
>
>
>--
>----------------------------------
>Siemel B. Naran (sbnaran@uiuc.edu)
>----------------------------------

Original posting:

Let us say I have the following template:
template <class T> class FooT
  {
public:
  class Bar
    {
    public:
    T var;
    };
  };
Notice that this template never actually declares a member variable
of type T, because it never declares a member variable of type Bar (and the
only instance of T is in Bar).  This means that I could theoretically do the
following:
class A
  {
  public:
  FooT<A> var;
  };
Note that if FooT DID declare an instance of A, then I would have a class
which contains itself (circular reference) -- which is illegal...
However, since it does not, the code is theoretically possible.  Yet on my
compiler (VC++ 5.0)  I receive the error "Bar" uses undefined class "A".
This relates to STL, because it would be very useful to be able to do this
with many of its classes.  For example,  here is an implementation of a
tree:
#include <list>
class Node
  {
  list<Node> children;
  }
In particular, I was trying to make a tree whose children are accessed
by "keys":
#include <map>
class Node
  {
map<uint,Node> children;
  };
The problem is that map declares the template Pair<A,B>, which instantiates
A and B.

Gurus, Is this valid C++ syntax?
Could a couple of people with access to other compilers paste the
code in to see what happens?

Thanks,
Andy
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]