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

Potion

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.

Hardfeatured

+1, but as I said to JaredPar: How come you're so confident that this should be allowed? You certainly can't declare an array of X inside the definition of X (this would lead to an infinite-size data structure), so why should a list<X> be allowed? I can't find anything in the standard, so I think the fact that is is allowed on some implementations is probably just an implementation detail. Thoughts? – Eakin

The best workaround for VC6 bugs is to use a compiler written in this millenium, and after the language was standardized. ;) – Drunken

@j_random_hacker: But you can declare a pointer to an array of X inside the definition of X (or just a pointer to X). And here, he is storing a pointer to a list. But I can't remember all the details of when and how incomplete types are allowed, so not sure if that makes it legal. :) – Drunken

Please use a smart pointer instead of a pointer. Here, a std::auto_ptr should be enough. – Hen

Sorry, my 1st comment was unclear -- I was referring to Neil's claim that this was due to a bug on VS6. Neil's actual code OTOH is 100% guaranteed to work. – Eakin

Perfect place to use std::auto_ptr – Lutist

Unless he wants to start assigning one URL to another. In which case, a raw pointer with suitable assignment op & copy ctor may be better. – Hardfeatured

This answer is incorrect, the template arguments for the containers may not be incomplete types. – Selfdeceit

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

Swahili

@Shino, could you post the error message? VS 6.0 has known issues with STL and it's likely you're running into one of them. – Swahili

@Shino: VS 6.0 unfortunately has many bugs and inconsistencies with the more modern parts of C++ (the STL, templates etc.). If at all possible, try upgrading to a newer compiler -- free Express versions are available. – Eakin

I just tried it with VC6, and there are indeed errors. Definite bug. – Hardfeatured

@Neil, you have VC6 on your machine? – Swahili

I can't bring myself to delete it. But I do all my current stuff with g++ 4.4.0 and Code::Blocks. – Hardfeatured

@Jared: How come you're so confident that this should be allowed? You certainly can't declare an array of X inside the definition of X (this would lead to an infinite-size data structure), so why should a list<X> be allowed? I can't find anything in the standard, so I think the fact that is is allowed on some implementations is probably just an implementation detail. Thoughts? – Eakin

@j_random_hacker, my standards interpretation i perfer to consult litb :). But generally speaking if it compiles on VS2005 or higher and gcc 4.0 and higher I tend to think of it as allowed and legal. It's by no means a standards interpretation but I consider it a fairly good bar to judge by. – Swahili

14.3.1 has a note "a template type argument may be an incomplete type (3.9), but 17.3.3.6:2 says undefined "if an incomplete type (3.9) is used as a template argument when instantiating a template component." Not exactly sure how to interpret this, but I'm guessing the type must be complete when any members of it are instantiated, but since he just creates a pointer to a list of an incomplete type, it should be safe. Or what? – Drunken

@jalf: Yikes, I don't have a 17.3.3.6! My copy (inherited from the previous guy) says "ISO/IEC 14882, Second edition 2003-10-15", what's yours? – Eakin

@jalf: Interesting point BTW. My guess is that incomplete types would be allowed for template args just as "usual" (i.e. as function arg/return types, and as pointers-to/refs-to). IMHO the issue is whether a standard container is allowed to use the template arg type in ways that require it to be a complete type. (Imagine a fixed-size vector type that stored an array of T directly in the object -- that would obviously require a complete type.) – Eakin

@j_random - I suspect a typo - it's section 17.4.3.6 in my copy – Hardfeatured

Oops yes, it was a typo. I meant 17.4.3.6. And I don't think there are any special requirements regarding the standard container. When any component of the template is instantiated, the type must be complete (17.4.3.6), so it has to be complete for standard containers as well as all other templates. But since he's only storing a pointer to the type, I don't think anything actually gets instantiated at that point. I agree, if he stored a list of T directly in the object, that would require a complete type. – Drunken

@jalf - Please re-read the question and the answers - my answer which uses a pointer is just a hack to get round the VC6 issue. The original question had no pointer. – Hardfeatured

This answer is incorrect, the template arguments for the containers may not be incomplete types. – Selfdeceit

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.

Selfdeceit

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?

Eakin

There's no answer to the man's problem, just some observation. And a question. – Alimentary

@Dave: I meant to emphasise that the standard doesn't guarantee that his code should work -- so his code is unportable, likely to work on some compilers and not on others. But fair enough, there's a lot of commentary and not much emphasis on this useful tidbit. – Eakin

You cannot instantiate the standard containers with an incomplete type. – Funchal

Last item in section 17.4.3.6 of the 2003 standard. – Funchal

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.

Gadget

You cannot have an std::list of incomplete type pre-C++17. – Selfdeceit