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

int 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

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 2

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 3

Contrary to the claims in the other answers, it is indeed not legal to instantiate any standard container, including std::list, with an incomplete type. (For a language-lawyer discussion of this, see e.g. How can an incomplete type be used as a template parameter to vector here?)

This requirement only gets relaxed in C++17 for std::forward_list, std::list and std::vector. For any earlier standard, the original code working with newer versions of VC and gcc is a non-standard extension. This also applies to your observations with std::vector.

In pre-C++17, to portably have an std::list of some class T as an member of said class, you do need a workaround like std::list<T*> or use the boost.container library, which already portably implements the relaxed requirements.

Note that even in C++17, you may only instantiate the class template itself with an incomplete type. The type must still be complete when any member is instantiated.

Answer 4

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 5

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.