Cách tạo cấu trúc chứa danh sách của chính nó?

Question

Tôi muốn tạo ra một cấu trúc, trong đó có một danh sách các giống cấu trúc như thế này:

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

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

Mã này không được biên dịch. Nhưng khi tôi thay thế std::list bằng std::vector nó hoạt động tốt. Tôi làm cách nào để làm việc này với std::list?

Cửa sổ đầu ra chứa lỗi sau.

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

Nếu bạn cần một workround cho những gì có vẻ là một lỗi VC6, tạo danh sách động:

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

Một số người được hỏi tại sao danh sách các loại tương tự như các thành viên được phép (và trong quan điểm của tôi họ) khi

Url array[5]; 

ví dụ như một thành viên sẽ không được. Tôi không thể tìm thấy bất cứ điều gì trong tiêu chuẩn hoặc, nhưng sizeof(std:;list <T>) không phụ thuộc vào điều đó là một danh sách. Danh sách giả sử được triển khai dưới dạng (một số giả C++ ở đây):

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

thì không có kích thước không xác định để xử lý. Hãy xem xét mã tối thiểu sau giải quyết vấn đề của người hỏi:

template <typename T> struct A { 
}; 

struct B { 
    A <B> b; 
}; 

Tôi không thấy lý do nào có thể khiến điều này không hợp pháp.

Answer 2

Bạn có thể cho chúng tôi biết bạn đang sử dụng trình biên dịch nào không? Không có gì sai với những gì bạn đang làm. Tôi đã thử những điều sau đây trên VS2008 SP1 và nó biên dịch không có vấn đề

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

Bạn có lẽ quên bao gồm danh sách?

EDIT

OP đang sử dụng Visual Studio 6.0 và Neil đã có thể xác nhận rằng nó thực sự là một lỗi trong VS6

Answer 3

Thú vị - bạn đang cố gắng tạo một loại vector hoặc list loại không đầy đủ. Từ một cái nhìn nhanh về tiêu chuẩn, tôi không thể tìm thấy bất cứ điều gì nói rằng điều này là hoặc không được cho phép được cho các loại container có trong Thư viện chuẩn C++. Hoặc cầm quyền sẽ có vẻ là hợp lý:

Tại sao nó có thể không được phép: Bạn không thể khai báo một đối tượng kiểu X bên trong định nghĩa của X.

Ví dụ: đoạn mã sau thất bại trong việc biên dịch bởi vì nó sẽ tạo ra một cấu trúc dữ liệu vô cùng sâu:

struct X { 
    X x; 
}; 

Tại sao nó có thể được phép: Hầu hết các container là resizeable, cần một mức gián tiếp (con trỏ) với các yếu tố dữ liệu thực tế trong thực tế. Đó là hợp pháp để khai báo một con trỏ đến X bên trong định nghĩa của X.

Như đoạn cuối cho thấy, cách thông thường để giải quyết vấn đề này là sử dụng con trỏ hoặc tham chiếu đến X. Ví dụ. hai đoạn mã sau đây chỉ biên dịch tốt:

struct Y { 
    Y* y; 
}; 

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

Có ai (OK, ý tôi là litb :-P) biết những yêu cầu thực sự dành cho các loại thùng chứa chuẩn không?

Answer 4

Mã biên dịch hoàn hảo với GCC 4.4 Và thực hiện hoàn hảo. MSVC++ trước phiên bản 7, không hoàn toàn tuân thủ các tiêu chuẩn. Bạn nên cân nhắc sử dụng trình biên dịch mới hơn.

Answer 5

Trái ngược với xác nhận quyền sở hữu trong các câu trả lời khác, thực sự là không hợp pháp để khởi tạo bất kỳ vùng chứa tiêu chuẩn nào, bao gồm std::list, với loại không đầy đủ. (Đối với một cuộc thảo luận language-lawyer điều này, xem ví dụ How can an incomplete type be used as a template parameter to vector here?)

Yêu cầu này chỉ được nới lỏng trong C++ 17 cho std::forward_list, std::list và std::vector. Đối với bất kỳ tiêu chuẩn nào trước đó, mã gốc hoạt động với các phiên bản VC và gcc mới hơn là một phần mở rộng không chuẩn. Điều này cũng áp dụng cho các quan sát của bạn với std::vector.

Trong pre-C++ 17, để portably có một std::list của một số lớp T như một thành viên của lớp cho biết, bạn cần một workaround như std::list<T*> hoặc sử dụng thư viện boost.container, mà đã portably thực hiện các yêu cầu thư giãn .

Lưu ý rằng ngay cả trong C++ 17, bạn chỉ có thể nhanh chóng tự tạo mẫu lớp với loại không hoàn chỉnh. Loại vẫn phải được hoàn thành khi bất kỳ thành viên nào được khởi tạo.