How to create a structure containing a list of itself?

Question

I want to create a structure that contains a list of the same structure as this:

#include <list> struct Url { CString strUrl; std::list<Url> children; }; int main() { Url u1, u2; u1.children.push_back(u2); } 

This code does not compile. But when I replace std::list with std::vector , it works fine. How can I make this work with std::list ?

The 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 desktop for what seems like a VC6 bug, create a 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 ask why lists of the same type as members are allowed (and, in my opinion, they are) when

 Url array[5]; 

for example, will not be a member. I can not find anything in the standard, but sizeof( std:;list <T>) does not depend on what the list is. Suppose the list was implemented as (some pseudo C ++ here):

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

then there is no unknown size. Consider the following minimal code that addresses the questionnaire problem:

 template <typename T> struct A { }; struct B { A <B> b; }; 

I see no possible reason that this was not legal.

Answer 2

Can you tell us which compiler you are using? There is nothing inherent in what you do. I tried the following on VS2008 SP1 and did not compile the 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 forget to include the list?

EDIT

OP uses Visual Studio 6.0, and Neil was able to confirm that this is really a bug in VS6

Answer 3

Unlike claims in other answers, it is really not legal to instantiate any standard container, including std::list , with an incomplete type. (For a language-lawyer discussion of this, see for example, How can I use an incomplete type as a template parameter for a vector here? )

This requirement is only relaxed in C ++ 17 for std::forward_list , std::list and std::vector . For any earlier standard, source code that works 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, for portability of std::list some class T as a member of the specified class, you will need a workaround, for example std::list<T*> , or use the boost.container library, which already implements the easy-to-use requirements portable.

Note that even in C ++ 17 you can create an instance of the class template itself with an incomplete type. The type must be completed when any element is created.

Answer 4

Interesting - you are trying to create a vector or list incomplete type. From a brief look at the standard, I cannot find anything saying whether this is allowed or not allowed for container types included in the C ++ standard library. Any decision seems reasonable:

Why this cannot be resolved: You cannot declare an object of type X inside the definition of X

eg. The following code does not compile because it will create an infinitely deep data structure:

 struct X { X x; }; 

Why this can be resolved: Most containers are resized, which actually requires actual data elements (pointers) on the actual data elements. It is legal to declare a pointer to- X inside a definition of X

As the last paragraph shows, the usual way around this problem is to use pointers or references to X For example. The following two snippets compile simply:

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

Does anyone (well, I mean the light bulb: -P) know what requirements really exist for standard types of containers?

Answer 5

The code compiles fine with GCC 4.4 and works great. MSVC ++ prior to version 7 was not fully compliant with the standards. You should consider using a newer compiler.