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 funziona correttamente. Come posso farlo funzionare con std::list?

La 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 la lista in modo dinamico:

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

ad esempio come membro non lo sarebbe. Neanche io riesco a trovare nulla nello standard, ma lo standard sizeof(std:;list <T>) non dipende dalla cosa di cui si tratta. 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 vedo alcuna ragione possibile che questo non dovrebbe essere legale.

Answer 2

Puoi dirci quale compilatore stai utilizzando? Non c'è nulla di intrinsecamente sbagliato in quello che stai facendo. Ho provato quanto segue su VS2008 SP1 e non ho 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 dimenticato di includere l'elenco?

EDIT

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

Answer 3

Interessante - si sta tentando di creare un vector o list di tipo incompleto. Da un rapido sguardo allo standard, non riesco a trovare nulla che dica se questo è o non dovrebbe essere consentito per i tipi di container inclusi nella libreria standard C++. 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.

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

struct X { 
    X x; 
}; 

Perché potrebbe essere consentito: maggior parte dei contenitori sono ridimensionabili, che richiedono un livello di indirezione (puntatori) per gli elementi dei dati effettivi in pratica. È legale dichiarare un puntatore-a-X all'interno della definizione di X.

Come suggerisce l'ultimo paragrafo, il modo usuale per ovviare a questo problema è l'utilizzo di 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) sanno quali sono i requisiti in realtà sono per i tipi di container standard?

Answer 4

Il codice si integra perfettamente con GCC 4.4 ed esegue perfettamente. MSVC++ precedente alla versione 7, non era totalmente conforme agli standard. Dovresti considerare l'utilizzo di un compilatore più recente.

Answer 5

Contrariamente alle affermazioni nelle altre risposte, è infatti non legale per creare un'istanza di qualsiasi contenitore standard, incluso std::list, con un tipo incompleto. (Per una language-lawyer discussione di questo, si veda ad esempio How can an incomplete type be used as a template parameter to vector here?)

Questo requisito solo si rilassato in C++ 17 per std::forward_list, std::list e std::vector. Per qualsiasi standard precedente, il codice originale che funziona con le versioni più recenti di VC e gcc è un'estensione non standard. Questo vale anche per le tue osservazioni con std::vector.

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

Si noti che anche in C++ 17 è possibile creare un'istanza del modello di classe stesso con un tipo incompleto. Il tipo deve essere ancora completo quando un membro viene istanziato.