class containing a list of itself

Discussion in 'C++' started by Old Wolf, Aug 25, 2004.

  1. Old Wolf

    Old Wolf Guest

    The following code causes a segfault for me, why?

    #include <list>

    template<typename T>
    struct Tree
    {
    std::list< Tree<T> > child;
    };

    int main()
    {
    Tree<int> bar;
    std::list< Tree<int> > foo;
    foo.push_back(bar);
    }

    If I reverse the order of the 'foo' and 'bar' declarations then I instead
    get a compiler error "Compiler could not generate default constructor
    for class Tree<int>". The problem is the same with other types instead of
    'int', but if I change list to vector or deque then there is no problem
    at all.
     
    Old Wolf, Aug 25, 2004
    #1
    1. Advertising

  2. Old Wolf

    Sharad Kala Guest

    "Old Wolf" <> wrote in message
    news:...
    > The following code causes a segfault for me, why?
    >

    [snip]
    > If I reverse the order of the 'foo' and 'bar' declarations then I instead
    > get a compiler error "Compiler could not generate default constructor
    > for class Tree<int>". The problem is the same with other types instead of
    > 'int', but if I change list to vector or deque then there is no problem
    > at all.


    Which compiler are you using ? I can't see both the problems on VC 7.1 and
    g++ 3.3.1.

    -Sharad
     
    Sharad Kala, Aug 25, 2004
    #2
    1. Advertising

  3. Old Wolf wrote in news: in
    comp.lang.c++:

    > The following code causes a segfault for me, why?
    >
    > #include <list>
    >
    > template<typename T>
    > struct Tree
    > {
    > std::list< Tree<T> > child;


    Tree< T > is at this point an incomplete type, all the standard library
    containers require that there paramiters are complete.

    > };
    >
    > int main()
    > {
    > Tree<int> bar;
    > std::list< Tree<int> > foo;
    > foo.push_back(bar);
    > }
    >
    > If I reverse the order of the 'foo' and 'bar' declarations then I
    > instead
    > get a compiler error "Compiler could not generate default constructor
    > for class Tree<int>". The problem is the same with other types instead
    > of 'int', but if I change list to vector or deque then there is no
    > problem at all.


    It just so happens that vector and deque on you implementation *don't*
    require a complete type, IOW it may work but it isn't portable.

    The good news is this is really a Quality of Implementation issue.
    I.e. there is no "good" reason the the standard library containers
    *need* to require a complete argument type.

    So if you're not worried about having complete portablity you could
    upgrade your standard library, both g++ and dinkumware compile
    your code without any problem. I don't now about stlport but my
    experience with rougewave suggest it will not. But your code will
    be non-standard until/unless the standard gets changed.

    Rob.
    --
    http://www.victim-prime.dsl.pipex.com/
     
    Rob Williscroft, Aug 25, 2004
    #3
  4. Old Wolf

    Sharad Kala Guest

    > But your code will
    > be non-standard until/unless the standard gets changed.


    I think Standard does mention about this in Section 14.3.1/2
    " ...[Note: a template type argument may be an incomplete type. ] "

    -Sharad
     
    Sharad Kala, Aug 25, 2004
    #4
  5. Sharad Kala wrote in news: in comp.lang.c++:

    >> But your code will
    >> be non-standard until/unless the standard gets changed.


    With hindsight I should have possibly been clearer that the requirment
    for completeness of argument types, is only for instantiation *not*
    for declaration:

    #include <list>

    struct X;

    extern std::list< X > xlist;

    struct X {};

    std::list< X > xlist;


    >
    > I think Standard does mention about this in Section 14.3.1/2
    > " ...[Note: a template type argument may be an incomplete type. ] "
    >



    14.3.1 == Templates / Template type arguments.

    Not really relevent to wether or not std::list< T > can take
    an incomplete T and be instantiated *before* T is complete.

    IOW: you can always (*) declare a specialization which has an incomplete
    argument type, what is dependant on the template defenition is wether
    you can instantiate such a specialization.

    *) Unless such a declaration requires instantition of an
    un-instantiatable specialization:

    template < typename > struct empty {};

    template < typename T, typename U = typename empty< T >::type >
    struct no
    {
    };

    extern no< int > nope;

    Rob.
    --
    http://www.victim-prime.dsl.pipex.com/
     
    Rob Williscroft, Aug 25, 2004
    #5
  6. Old Wolf

    tom_usenet Guest

    On Wed, 25 Aug 2004 19:47:50 +0530, "Sharad Kala"
    <> wrote:

    >> But your code will
    >> be non-standard until/unless the standard gets changed.

    >
    >I think Standard does mention about this in Section 14.3.1/2
    >" ...[Note: a template type argument may be an incomplete type. ] "


    17.4.3.6 Other functions
    1 In certain cases (replacement functions, handler functions,
    operations on types used to instantiate standard library template
    components), the C + + Standard Library depends on components supplied
    by a C + + program. If these components do not meet their
    requirements, the Standard places no requirements on the
    implementation.
    2 In particular, the effects are undefined in the following cases:
    [snip]
    — if an incomplete type (3.9) is used as a template argument when
    instantiating a template component.

    Tom
     
    tom_usenet, Aug 25, 2004
    #6
  7. Old Wolf

    Old Wolf Guest

    tom_usenet <> wrote:
    >
    > 2 In particular, the effects are undefined in the following cases:
    > [snip]
    > ? if an incomplete type (3.9) is used as a template argument when
    > instantiating a template component.


    I think I am confused about the meaning of "instantiating"?

    > #include <list>
    >
    > template<typename T>
    > struct Tree
    > {
    > std::list< Tree<T> > child;

    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    declaration (no objects are yet created)

    > };
    >
    > int main()
    > {
    > Tree<int> bar;

    ^^^^^^^^^^^^^^
    instantiation (a 'Tree<int>' object is created, which involves
    creation of any sub-objects of Tree<int>).
    Surely at this point, Tree<int> is a complete type,
    so std::list< Tree<int> > would be OK.

    > std::list< Tree<int> > foo;
    > foo.push_back(bar);
    > }
     
    Old Wolf, Aug 26, 2004
    #7
  8. Old Wolf wrote in news: in
    comp.lang.c++:

    > tom_usenet <> wrote:
    >>
    >> 2 In particular, the effects are undefined in the following cases:
    >> [snip]
    >> ? if an incomplete type (3.9) is used as a template argument when
    >> instantiating a template component.

    >
    > I think I am confused about the meaning of "instantiating"?


    Its when a template (class or function) is used to create a new
    type or function (a specialization in standardeze).

    >
    >> #include <list>
    >>
    >> template<typename T>
    >> struct Tree
    >> {
    >> std::list< Tree<T> > child;

    > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    > declaration (no objects are yet created)


    Correct, and the declaration isn't the problem.

    >
    >> };
    >>
    >> int main()
    >> {
    >> Tree<int> bar;

    > ^^^^^^^^^^^^^^
    > instantiation (a 'Tree<int>' object is created, which involves
    > creation of any sub-objects of Tree<int>).


    Yes, however the type "Tree< int >" isn't *complete* until
    instantiation is finnished.

    > Surely at this point, Tree<int> is a complete type,
    > so std::list< Tree<int> > would be OK.


    Yes, but instantiating Tree< int > requires that Tree< int >
    be *complete* before Tree< int > is instantiated, a catch 22,
    as a template isn't complete until its been instantiated.

    >
    >> std::list< Tree<int> > foo;
    >> foo.push_back(bar);
    >> }

    >


    Note: with class templates "complete" and "instantiated" are
    equvalent terms, however non-templates can also be incomplete:

    struct X; /* incomplete */
    struct x {}; /* complete */

    Rob.
    --
    http://www.victim-prime.dsl.pipex.com/
     
    Rob Williscroft, Aug 26, 2004
    #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. Joseph Lanctot
    Replies:
    1
    Views:
    399
    John Carson
    Jun 21, 2004
  2. alon
    Replies:
    6
    Views:
    371
  3. Poppy
    Replies:
    1
    Views:
    397
    Poppy
    May 30, 2008
  4. scg_
    Replies:
    6
    Views:
    358
    Noah Roberts
    Feb 3, 2009
  5. dhruvbird
    Replies:
    16
    Views:
    1,344
    John Nagle
    Jul 16, 2010
Loading...

Share This Page