Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > std::list of template class

Reply
Thread Tools

std::list of template class

 
 
alex221@pisem.net
Guest
Posts: n/a
 
      01-21-2007
In need to implement a tree structure in which every node has arbitrary
number of children the following code has come into mind:

using std::list;
template < class Contents > class Tree_node{

Contents cn;
list < BTree_node < Contents > > children;

........
}

template < class Contents > class Tree{
list < Tree_node < Contents > > ;

........
}

on what microsoft VC++ compiler complains with error message
error C2079: 'child_list' uses undefined class 'list<class
BTree_node<int>,class std::allocator<class BTree_node<int> > >'
when trying to instantiate
Tree <int> tree;

What is the workaround for this?
Thanks in advance

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      01-21-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> In need to implement a tree structure in which every node has arbitrary
> number of children the following code has come into mind:
>
> using std::list;
> template < class Contents > class Tree_node{
>
> Contents cn;
> list < BTree_node < Contents > > children;


Do you mean:

list < Tree_node < Contents > > children;
^^^^

> .......
> }
>
> template < class Contents > class Tree{
> list < Tree_node < Contents > > ;
>
> .......
> }
>
> on what microsoft VC++ compiler complains with error message
> error C2079: 'child_list' uses undefined class 'list<class
> BTree_node<int>,class std::allocator<class BTree_node<int> > >'
> when trying to instantiate
> Tree <int> tree;


You seem to be running into the trap

class X {

std::list< X > some_member;

};

This is not required to compile and if it does, the behavior is undefined.
The reason is that X is incomplete in std::list<X>. It is regrettable that
the standard requires completeness for type arguments in std::list<>, but
it does in [17.4.3.6/2].


> What is the workaround for this?


(a) Don't bother: fix the typo from BTree_node to Tree_node and hope for the
best. Most implementation of std::list<> do actually not require the type
argument to be a complete type. (You might run into trouble with g++
installations that were built with the concept-checks option enabled. So
much for portability.)

(b) Write your own std::list<> drop in replacement that, for sure, does not
require completeness. That can be done in about 900 LOC. Or use an STL
implementation that makes this guarantee.

(c) Introduce yet another level of indirection

class X {

std::list<X*> some_ptr;

};

and deal with the memory management issues that arise.



Best

Kai-Uwe Bux

 
Reply With Quote
 
 
 
 
Daniel T.
Guest
Posts: n/a
 
      01-21-2007
(E-Mail Removed) wrote:

> In need to implement a tree structure in which every node has arbitrary
> number of children the following code has come into mind:
>
> using std::list;
> template < class Contents > class Tree_node{
>
> Contents cn;
> list < BTree_node < Contents > > children;
>
> .......
> }
>
> template < class Contents > class Tree{
> list < Tree_node < Contents > > ;
>
> .......
> }
>
> on what microsoft VC++ compiler complains with error message
> error C2079: 'child_list' uses undefined class 'list<class
> BTree_node<int>,class std::allocator<class BTree_node<int> > >'
> when trying to instantiate
> Tree <int> tree;
>
> What is the workaround for this?


Define class BTree_node.
 
Reply With Quote
 
Greg
Guest
Posts: n/a
 
      01-21-2007

(E-Mail Removed) wrote:
> In need to implement a tree structure in which every node has arbitrary
> number of children the following code has come into mind:
>
> using std::list;
> template < class Contents > class Tree_node{
>
> Contents cn;
> list < BTree_node < Contents > > children;
>
> .......
> }
>
> template < class Contents > class Tree{
> list < Tree_node < Contents > > ;
>
> .......
> }
>
> on what microsoft VC++ compiler complains with error message
> error C2079: 'child_list' uses undefined class 'list<class
> BTree_node<int>,class std::allocator<class BTree_node<int> > >'
> when trying to instantiate
> Tree <int> tree;
>
> What is the workaround for this?


Deciding whether the name of the class template is Tree_node or
BTree_node would probably help with the compiler problem.

There is some disagreement whether an object may safely have a Standard
container of its own type as one of its data members, or whether the
member declaration of the container is specifying an "incomplete" type.
If so, the program's behavior is, technically at least, undefined.

Greg

 
Reply With Quote
 
alex221@pisem.net
Guest
Posts: n/a
 
      01-21-2007
i surely did a misprint editing the message - in a compiler there is
BTree_node everywhere

 
Reply With Quote
 
Greg
Guest
Posts: n/a
 
      01-21-2007

Kai-Uwe Bux wrote:
> (E-Mail Removed) wrote:
>
> > In need to implement a tree structure in which every node has arbitrary
> > number of children the following code has come into mind:
> >
> > using std::list;
> > template < class Contents > class Tree_node{
> >
> > Contents cn;
> > list < BTree_node < Contents > > children;
> > .......
> > }

>
> You seem to be running into the trap
>
> class X {
>
> std::list< X > some_member;
>
> };


Unlikely, since the code is question is declaring a class template -
not a class - with the std::list<> of its own type as a data member.

> This is not required to compile and if it does, the behavior is undefined.
> The reason is that X is incomplete in std::list<X>. It is regrettable that
> the standard requires completeness for type arguments in std::list<>, but
> it does in [17.4.3.6/2].


But in this case, "X" would be a specialization of a class template.
Therefore, the std::list<> data member of X would be instantiated - if
it is instantiated at all - only after an instance of the template
class X itself had been instantiated - which of course requires that X
be a complete type. In other words, X must be a complete type before
its std::list data member could ever be instantiated.

> > What is the workaround for this?

>
> (a) Don't bother: fix the typo from BTree_node to Tree_node and hope for the
> best. Most implementation of std::list<> do actually not require the type
> argument to be a complete type. (You might run into trouble with g++
> installations that were built with the concept-checks option enabled. So
> much for portability.)


I think the type is the only evident problem at this point.

Greg

 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      01-21-2007
Greg wrote:

>
> Kai-Uwe Bux wrote:
>> (E-Mail Removed) wrote:
>>
>> > In need to implement a tree structure in which every node has arbitrary
>> > number of children the following code has come into mind:
>> >
>> > using std::list;
>> > template < class Contents > class Tree_node{
>> >
>> > Contents cn;
>> > list < BTree_node < Contents > > children;
>> > .......
>> > }

>>
>> You seem to be running into the trap
>>
>> class X {
>>
>> std::list< X > some_member;
>>
>> };

>
> Unlikely, since the code is question is declaring a class template -
> not a class - with the std::list<> of its own type as a data member.
>
>> This is not required to compile and if it does, the behavior is
>> undefined. The reason is that X is incomplete in std::list<X>. It is
>> regrettable that the standard requires completeness for type arguments in
>> std::list<>, but it does in [17.4.3.6/2].

>
> But in this case, "X" would be a specialization of a class template.
> Therefore, the std::list<> data member of X would be instantiated - if
> it is instantiated at all - only after an instance of the template
> class X itself had been instantiated - which of course requires that X
> be a complete type. In other words, X must be a complete type before
> its std::list data member could ever be instantiated.


Templates do not by-pass the completeness problem. Consider

template < typename T >
class X {

std::list< X > some_member; // (*)

};

On line (*) the type X is incomplete. You are right to observe that X will
be complete, once X<int> has been instantiated. However [14.6/7] kicks in:

...If a type used in a non-dependent name is incomplete at the point at
which a template is defined but is complete at the point at which an
instantiation is done, and if the completeness of that type affects
whether or not the program is well-formed or affects the semantics of the
program, the program is ill-formed; no diagnostic is required. [Note: if a
template is instantiated, errors will be diagnosed according to the other
rules in this Standard. Exactly when these errors are diagnosed is a
quality of implementation issue. ] ...

Thus, if completeness actually mattered with regard to std::list<>, we would
be doomed nonetheless.

Also, this is to be expected. After all

template < typename T >
class X {

std:air< X, X > data;

};

cannot work just because we turned the recursive type bomb into a template.


>> > What is the workaround for this?

>>
>> (a) Don't bother: fix the typo from BTree_node to Tree_node and hope for
>> the best. Most implementation of std::list<> do actually not require the
>> type argument to be a complete type. (You might run into trouble with g++
>> installations that were built with the concept-checks option enabled. So
>> much for portability.)

>
> I think the type is the only evident problem at this point.


Do you mean "type" or "typo"?



Best

Kai-Uwe Bux
 
Reply With Quote
 
Greg
Guest
Posts: n/a
 
      01-22-2007
Kai-Uwe Bux wrote:
> Greg wrote:
> >> > What is the workaround for this?
> >>
> >> (a) Don't bother: fix the typo from BTree_node to Tree_node and hope for
> >> the best. Most implementation of std::list<> do actually not require the
> >> type argument to be a complete type. (You might run into trouble with g++
> >> installations that were built with the concept-checks option enabled. So
> >> much for portability.)


The "workaround" I would suggest would actually be - in my view - a
better overall implementation. The idea would be to store the child
tree nodes in the list as smart pointers. Doing so solves the
"incomplete" type problem since a std::tr1::shared_ptr does not require
a complete type - yet a template instantiated with an incomplete type
is itself a complete type.

Moreover, managing the tree nodes without some kind of shared ptr is
apt to lead to dangling pointers, or leaks, or similar problems.

> > I think the type is the only evident problem at this point.

>
> Do you mean "type" or "typo"?


The word "type" in this case was a typo for "typo" - so the word was an
example of itself even as it was a word for something else. Glad I was
able to clear that up.

Greg

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Declaring a template class with two template params a friend in anon-template class A L C++ 1 08-25-2010 07:25 AM
r H2 deduce deduce template argument of a template class inheritingfrom a non template base? nguillot C++ 5 03-08-2009 05:56 PM
How to use the template member function of a template in the memberfunction of another template class? Peng Yu C++ 3 10-26-2008 03:51 PM
template template arguments: expected a class template, got `Component<T1, T2, T3> gary.bernstein@gmail.com C++ 1 06-08-2007 07:10 AM
A parameterized class (i.e. template class / class template) is not a class? christopher diggins C++ 16 05-04-2005 12:26 AM



Advertisments