std::list of template class

[alex221]

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 <inttree;

What is the workaround for this?
Thanks in advance

[Kai-Uwe Bux]

al*****@pisem.net 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 <inttree;

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

[Daniel T.]

al*****@pisem.net 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 <inttree;

What is the workaround for this?

Define class BTree_node.

[Greg]

al*****@pisem.net 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 <inttree;

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

[alex221]

i surely did a misprint editing the message - in a compiler there is
BTree_node everywhere

[Greg]

Kai-Uwe Bux wrote:

al*****@pisem.net 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

[Kai-Uwe Bux]

Greg wrote:

>
Kai-Uwe Bux wrote:

>al*****@pisem.net 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<inthas 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::pair< 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

[Greg]

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