¿Cómo crear una estructura que contiene una lista de sí mismo?

Question

que quieren crear una estructura que contiene una lista de misma estructura como esta:

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

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

Este código no está compilando. Pero cuando reemplazo std::list con std::vector, funciona bien. ¿Cómo puedo hacer que esto funcione con std::list?

La ventana de salida contiene el siguiente 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

Si necesita un workround de lo que parece ser un error VC6, crear la lista de forma dinámica:

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

Algunos han preguntado por qué se permiten listas del mismo tipo que los miembros (y en mi opinión son) cuando

Url array[5]; 

por ejemplo como un miembro no lo sería. Tampoco puedo encontrar nada en el estándar, pero sizeof(std:;list <T>) no depende de lo que sea una lista. Supongamos que la lista se implementó como (algunos seudo C++ aquí):

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

entonces no hay tamaño desconocido que tratar. Considere el siguiente código mínimo que aborda el problema interrogadores:

template <typename T> struct A { 
}; 

struct B { 
    A <B> b; 
}; 

no puedo ver ninguna razón posible que esto no debería ser legal.

Answer 2

¿Puede decirnos qué compilador está utilizando? No hay nada intrínsecamente incorrecto con lo que estás haciendo. Probé lo siguiente en VS2008 SP1 y compiló ningún problema

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

¿Olvidaste incluir la lista?

EDITAR

OP está utilizando Visual Studio 6.0 y Neil pudo confirmar que se trata efectivamente de un error en VS6

Answer 3

Interesante - Está intentando crear un vector o list de tipo incompleto. A partir de un vistazo rápido al estándar, no puedo encontrar nada que indique si esto se permite o no para los tipos de contenedores incluidos en la Biblioteca estándar de C++. De cualquier fallo parece ser razonable:

¿Por qué no podría permitirse: No se puede declarar un objeto de tipo X dentro de la definición de X.

E.g. el siguiente código falla al compilar porque crearía una estructura de datos infinitamente profunda:

struct X { 
    X x; 
}; 

por qué podría ser permitido: mayoría de los contenedores son de tamaño variable, requiriendo un nivel de indirección (punteros) a los elementos de datos reales en la práctica. Es legal declarar un puntero a X dentro de la definición de X.

Como sugiere el último párrafo, la forma habitual de evitar este problema es utilizar punteros o referencias al X. P.ej. los siguientes dos fragmentos compilan bien:

struct Y { 
    Y* y; 
}; 

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

¿Alguien (OK, me refiero a :-P litb) saben cuáles son los requisitos en realidad son para tipos de contenedores de transporte?

Answer 4

El código compila perfectamente con GCC 4.4 Y se ejecuta perfectamente. MSVC++ anterior a la versión 7, no era totalmente compatible con los estándares. Debería considerar usar un compilador más nuevo.

Answer 5

Contrariamente a lo que se afirma en las otras respuestas, de hecho es no legal para instanciar cualquier contenedor estándar, incluido std::list, con un tipo incompleto. (Para una discusión language-lawyer de esto, véase, por ejemplo How can an incomplete type be used as a template parameter to vector here?)

Este requisito sólo se pone relajado en C++ 17 para std::forward_list, std::list y std::vector. Para cualquier estándar anterior, el código original que trabaja con las versiones más recientes de VC y gcc es una extensión no estándar. Esto también se aplica a sus observaciones con std::vector.

En el pre-C++ 17, que tienen una forma portátil std::list de alguna clase T como miembro de dicha clase, usted no necesita una solución como std::list<T*> o utilizar la biblioteca boost.container, que ya se implementa de forma portátil los requisitos relajados .

Tenga en cuenta que incluso en C++ 17, solo puede crear una instancia de la plantilla de clase con un tipo incompleto. El tipo debe estar completo cuando se crea una instancia de cualquier miembro.