std::list of template class

Discussion in 'C++' started by alex221@pisem.net, Jan 21, 2007.

  1. Guest

    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
    , Jan 21, 2007
    #1
    1. Advertising

  2. Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Jan 21, 2007
    #2
    1. Advertising

  3. Daniel T. Guest

    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.
    Daniel T., Jan 21, 2007
    #3
  4. Greg Guest

    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
    Greg, Jan 21, 2007
    #4
  5. Guest

    i surely did a misprint editing the message - in a compiler there is
    BTree_node everywhere
    , Jan 21, 2007
    #5
  6. Greg Guest

    Kai-Uwe Bux wrote:
    > 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
    Greg, Jan 21, 2007
    #6
  7. Kai-Uwe Bux Guest

    Greg wrote:

    >
    > Kai-Uwe Bux wrote:
    >> 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::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
    Kai-Uwe Bux, Jan 21, 2007
    #7
  8. Greg Guest

    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
    Greg, Jan 22, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,275
    Ivan Vecerina
    Mar 17, 2005
  2. christopher diggins
    Replies:
    16
    Views:
    738
    Pete Becker
    May 4, 2005
  3. Replies:
    6
    Views:
    634
    Jim Langston
    Oct 30, 2005
  4. Juha Nieminen
    Replies:
    22
    Views:
    996
    Kai-Uwe Bux
    Oct 12, 2007
  5. A L
    Replies:
    1
    Views:
    505
    Alf P. Steinbach /Usenet
    Aug 25, 2010
Loading...

Share This Page