How to create a structure which contains a list of itself

Question

I want to create a structure which contains a list of same structure like this.

#include <list>
struct Url
{
    CString strUrl;
    std::list<Url> children;
};

void main()
{
    Url u1, u2;
    u1.children.push_back(u2);
}

This code is not compiling. But when I replace std::list with std::vector it is working fine. How can I make this working with std::list.

Output window contains the following error.

c:\program files\microsoft visual studio\vc98\include\list(29) : error C2079: '_Value' uses undefined struct 'Url'
        E:\test\Test.cpp(23) : see reference to class template instantiation 'std::list<struct Url,class std::allocator<struct Url> >' being compiled
c:\program files\microsoft visual studio\vc98\include\functional(185) : error C2079: 'value' uses undefined struct 'Url'
        c:\program files\microsoft visual studio\vc98\include\list(285) : see reference to class template instantiation 'std::binder2nd<struct std::not_equal_to<struct Url> >' being compiled
        E:\test\Test.cpp(23) : see reference to class template instantiation 'std::list<struct Url,class std::allocator<struct Url> >' being compiled

Answer 1

Can you tell us what compiler you are using? There is nothing inherently wrong with what you are doing. I tried the following on VS2008 SP1 and it compiled no problem

#include <list>

struct Url
{
    std::string name;
    std::list<Url> children;
};

int _tmain(int argc, _TCHAR* argv[])
{
    Url u1,u2;
    u1.children.push_back(u2);
    return 0;
}

Did you perhaps forget to include list?

EDIT

OP is using Visual Studio 6.0 and Neil was able to confirm that it is indeed a bug in VS6

Answer 2

If you need a workround for what seems to be a VC6 bug, create the list dynamically:

#include <list>
#include <string>     // I don't use MFC

struct Url
{
    std::string strUrl;
    std::list<Url> * children;

    Url() {
       children = new std::list <Url>;
    }

    ~Url() {
     delete children;
    }
};

int  main()
{
    Url u1, u2;
    u1.children->push_back(u2);
}

Some have asked why lists of the same type as members are allowed (and in my view they are) when

Url array[5];

for example as a member would not be. I can't find anything in the standard either, but sizeof( std:;list <T>) is not dependent on the thing it is a list of. Suppose list was implemented as (some pseudo C++ here):

list <T> {
   listEntry <T> * first;
};

then there is no unknown size to deal with. Consider the following minimal code that addresses the questioners problem:

template <typename T> struct A {
};

struct B {
    A <B> b;
};

I can't see any possible reason that this should not be legal.

Answer 3

Interesting -- you are trying to create a vector or list of incomplete type. From a quick look at the standard, I can't find anything saying whether this is or is not supposed to be allowed for container types included in the C++ Standard Library. Either ruling would seem to be reasonable:

Why it might not be allowed: You can't declare an object of type X inside the definition of X.

E.g. the following code fails to compile because it would create an infinitely-deep data structure:

struct X {
    X x;
};

Why it might be allowed: Most containers are resizeable, necessitating a level of indirection (pointers) to the actual data elements in practice. It's legal to declare a pointer-to-X inside the definition of X.

As the last paragraph suggests, the usual way to get around this problem is to use pointers or references to X. E.g. the following two snippets compile just fine:

struct Y {
    Y* y;
};

struct Z {
    std::list<Z*> zl;
    std::vector<Z*> zv;
};

Does anyone (OK, I mean litb :-P) know what the requirements actually are for standard container types?

Answer 4

The code compiles perfectly well with GCC 4.4 And executes perfectly. MSVC++ prior to version 7, was not totally standards compliant. You should consider using a newer compiler.