Comment créer une structure qui contient une liste d'elle-même?

Question

Je veux créer une structure qui contient une liste de même structure comme ceci:

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

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

Ce code ne compile. Mais quand je remplacerai std::list avec std::vector il fonctionne très bien. Comment puis-je faire ce travail avec std::list?

fenêtre de sortie contient l'erreur suivante.

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 vous avez besoin d'un workround pour ce qui semble être un bug VC6, créez la liste dynamique:

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

Certains ont demandé pourquoi les listes du même type que les membres sont autorisés (et à mon avis ils sont) lorsque

Url array[5]; 

par exemple en tant que membre ne serait pas. Je ne trouve rien dans la norme non plus, mais sizeof( std:;list <T>) ne dépend pas de la chose est une liste de. la liste a été mis en œuvre comme On suppose que (certains pseudo C ++ ici):

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

alors il n'y a pas de taille inconnue à traiter. Considérez le code suivant minimal qui aborde le problème de questionneurs:

template <typename T> struct A {
};

struct B {
    A <B> b;
};

Je ne vois aucune raison possible que cela ne devrait pas être légal.

Answer 2

Pouvez-vous nous dire quel compilateur que vous utilisez? Il n'y a rien d'intrinsèquement mauvais avec ce que vous faites. J'ai essayé ce qui suit sur VS2008 SP1 et compilé aucun problème

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

Avez-vous oublié peut-être inclure la liste?

EDIT

OP utilise Visual Studio 6.0 et Neil a pu confirmer qu'il est en effet un bogue dans VS6

Answer 3

Contrairement aux affirmations des autres réponses, il est en effet pas juridique instancier un conteneur standard, y compris std::list, avec un type incomplet. (Pour un de ce fait, voir par exemple Comment un type incomplet est utilisé en tant que paramètre de modèle au vecteur ici? )

Cette exigence ne se fait détendue en C ++ 17 pour std::forward_list, std::list et std::vector. Pour toute norme antérieure, le code d'origine de travail avec les versions les plus récentes de VC et gcc est une extension non standard. Cela vaut également pour vos observations avec std::vector.

En pré-C ++ 17, d'avoir un portably std::list de certains T de classe en tant que membre de ladite classe, vous avez besoin d'une solution de contournement comme std::list<T*> ou utiliser la bibliothèque boost.container, qui met en œuvre les exigences déjà portably détendue.

Notez que même en C ++ 17, vous ne pouvez instancier le modèle de la classe elle-même avec un type incomplet. Le type doit encore être complet lorsqu'un membre est instancié.

Answer 4

Intéressant - vous essayez de créer un vector ou list de type incomplet. D'un coup d'œil à la norme, je ne trouve rien dire si cela est ou non censé être autorisé pour les types de conteneurs inclus dans la bibliothèque standard C ++. Soit la décision semble être raisonnable:

Pourquoi il pourrait ne pas être autorisé. Vous ne pouvez pas déclarer un objet de type X dans la définition de X

par exemple. le code suivant ne peut pas compiler car elle créerait une structure de données infiniment profonde:

struct X {
    X x;
};

Pourquoi il pourrait être permis: La plupart des conteneurs sont redimensionnable, ce qui nécessite un niveau d'indirection (pointeurs) aux éléments de données réels dans la pratique. Il est légal de déclarer un pointeur à X dans la définition de X.

Comme le dernier paragraphe indique, de la manière habituelle de contourner ce problème est d'utiliser des pointeurs ou des références à X. Par exemple. les deux extraits suivants compilent très bien:

struct Y {
    Y* y;
};

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

Quelqu'un (OK, je veux dire :-P litb) savent ce que les exigences sont en fait pour les types de conteneurs standards?

Answer 5

Le code compile parfaitement avec GCC 4.4 Et parfaitement exécute. MSVC ++ avant la version 7, n'a pas été totalement conforme aux normes. Vous devriez envisager d'utiliser un compilateur plus récent.