Come creare una struttura che contiene un elenco di se stesso?

Question

Voglio creare una struttura che contiene un elenco di stessa struttura come questa:

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

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

Questo codice non è la compilazione. Ma quando sostituisco std::list con std::vector si sta lavorando bene. Come posso fare questo lavoro con std::list?

finestra di output contiene il seguente errore.

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

Se avete bisogno di un workround per quello che sembra essere un bug VC6, creare dinamicamente la lista:

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

Alcuni hanno chiesto il motivo per cui le liste dello stesso tipo come membri sono autorizzati (e secondo me lo sono) quando

Url array[5]; 

per esempio come membro non sarebbe. Non riesco a trovare nulla nella norma sia, ma sizeof( std:;list <T>) non dipende cosa si tratta di un elenco di. Lista Supponiamo che è stato implementato come (alcuni pseudo C ++ qui):

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

allora non c'è dimensioni sconosciute da affrontare. Si consideri il seguente codice minimo che affronta il problema interroganti:

template <typename T> struct A {
};

struct B {
    A <B> b;
};

Non riesco a vedere ogni possibile ragione per cui questo non dovrebbe essere legale.

Answer 2

Puoi dirci cosa compilatore che si sta utilizzando? Non c'è niente di intrinsecamente sbagliato con quello che stai facendo. Ho provato quanto segue su VS2008 SP1 ed è compilato nessun 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;
}

Ti sei forse dimenticato di includere lista?

Modifica

OP sta usando Visual Studio 6.0 e Neil è stato in grado di confermare che è davvero un bug in VS6

Answer 3

Contrariamente a quanto affermato in altre risposte, è infatti non legale di creare un'istanza di qualsiasi contenitore standard, compreso std::list, con un tipo incompleto. (Per un 'language-lawyer'" lingua avvocato di questo, si veda ad esempio come può un tipo incompleto essere utilizzato come parametro di template a vettoriale qui? )

Questo requisito solo si rilassato in C ++ 17 per std::forward_list, std::list e std::vector. Per ogni punto di vista in precedenza, il codice originale di lavoro con le nuove versioni di VC e gcc è un'estensione non standard. Questo vale anche per le vostre osservazioni con std::vector.

Nel pre-C ++ 17, per avere un portabile std::list di qualche T classe come membro di detta classe, si ha bisogno di una soluzione alternativa come std::list<T*> o utilizzare la libreria boost.container, che già implementa portabile i requisiti rilassato.

Si noti che anche in C ++ 17, si può istanziare solo il modello di classe in sé con un tipo incompleto. Il tipo deve essere ancora completato quando ogni membro è istanziato.

Answer 4

Interessante - si sta cercando di creare un vector o list di tipo incompleto. Da un rapido sguardo alla standard, non riesco a trovare nulla da dire se questo è o non dovrebbe essere consentito per i tipi di contenitori inclusi nel C ++ Standard Library. In entrambi i sentenza sembrerebbe essere ragionevole:

Perché potrebbe non essere consentito:. Non è possibile dichiarare un oggetto di tipo X all'interno della definizione di X

es. il seguente codice non riesce a compilare, perché creerebbe una struttura di dati infinitamente profondo:

struct X {
    X x;
};

Perché potrebbe essere consentito: La maggior parte dei contenitori sono ridimensionabile, che richiede un livello di indirezione (puntatori) per gli elementi di dati reali in pratica. E 'legale per dichiarare un puntatore a X all'interno della definizione di X.

Come l'ultimo paragrafo suggerisce, il solito modo per aggirare questo problema è quello di utilizzare i puntatori o riferimenti a X. Per esempio. le seguenti due frammenti di compilare bene:

struct Y {
    Y* y;
};

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

Qualcuno (OK, intendo :-P litb) sa quali sono i requisiti in realtà sono per i tipi di container standard?

Answer 5

Il codice compila perfettamente con GCC 4.4 Ed esegue perfettamente. MSVC ++ precedenti alla versione 7, non era del tutto conforme agli standard. Si dovrebbe considerare l'utilizzo di un compilatore più recente.