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

Question

Quiero 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 sustituyo std::list con std::vector que está funcionando bien. ¿Cómo puedo hacer este trabajo con std::list?

ventana de resultados 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 sería. No puedo encontrar nada en la norma tampoco, pero sizeof( std:;list <T>) no depende de lo que es una lista de. lista Supongamos que se implementó como (algunos pseudo 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 lo compilador que está utilizando? No hay nada inherentemente malo en lo que está haciendo. He intentado lo siguiente en el SP1 de VS2008 y compilado 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;
}

¿Usted tal vez se olvide de 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

Contrariamente a lo expuesto en las otras respuestas, de hecho es no legal para crear una instancia de cualquier contenedor estándar, incluyendo std::list, con un tipo incompleto. (Para una href="/questions/tagged/language-lawyer" class="post-tag" 'language-lawyer'" lenguaje abogado a esto, véase, por ejemplo ¿Cómo puede un tipo incompleto puede utilizar como un parámetro de plantilla para vector aquí? )

Este requisito sólo se pone relajado en C ++ 17 para std::forward_list, std::list y std::vector. Para cualquier norma anterior, el código original de trabajo con las nuevas versiones 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, es posible que sólo una instancia de la clase misma plantilla con un tipo incompleto. El tipo todavía debe ser completado cuando se crea una instancia de cualquier miembro.

Answer 4

Interesante - usted está tratando de crear un vector o list de tipo incompleto. De un vistazo rápido a la norma, no puedo encontrar nada decir si esto es o no se supone que debe ser permitido para este tipo de contenedores incluidos en la Biblioteca C ++ estándar. 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

por ejemplo. 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 resizeable, lo que exige 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.

A medida que este último párrafo, de la forma habitual de solucionar este problema es utilizar punteros o referencias a 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 5

El código se compila perfectamente con GCC 4.4 Y ejecuta perfectamente. MSVC ++ anteriores a la versión 7, no era totalmente compatible con las normas. Usted debe considerar el uso de un compilador más reciente.