Sự khác biệt giữa SGI slist và C++ 11 forward_list là gì?

Question

Cả SGI slist và C++ 11 std::forward_list xuất hiện giống hệt với tôi trừ khi tôi đã bỏ sót điều gì đó; cả hai đều thực hiện một danh sách liên kết đơn lẻ.

Tôi giả sử có sự khác biệt mặc dù C++ Standard Commitee không chấp nhận tên slist và thay vào đó chọn tên mới, forward_list, khi họ thêm vùng chứa vào Thư viện chuẩn cho C++ 0x.

Answer 1

Một khác biệt lớn là std::forward_list thiếu chức năng thành viên size(), trong đó sgi::slist thì không. Động cơ cho điều này là một O (N) size() đã có vấn đề. N2543 có thêm chi tiết về các quyết định thiết kế cho forward_list.

Cập nhật:

tôi thời gian gần đây đã có một lý do tốt để xem xét kỹ hơn vấn đề này. slist cũng có các chức năng thành viên khác mà một trong những sẽ bị cám dỗ để suy nghĩ là O (1), nhưng thực sự là O (N). Chúng bao gồm:

iterator previous(iterator pos); 
const_iterator previous(const_iterator pos) const; 
iterator insert(iterator pos, const value_type& x); 
iterator erase(iterator pos); 
void splice(iterator position, slist& x); 
void splice(iterator position, slist& x, iterator i); 

Nói tóm lại, nếu bạn không rất cẩn thận, bạn có thể kết thúc với vấn đề hiệu suất đáng kể bằng cách sử dụng slist. Sử dụng std::forward_list thay vì đảm bảo rằng bạn sẽ nhận được hiệu suất O (1) dự kiến ​​trong danh sách được liên kết đơn lẻ của bạn.

Answer 2

Vì vậy, hãy đặt đơn giản, sgi :: slist và forward_list rất giống nhau.

Sự khác biệt là forward_list thiếu hàm thành viên size() được bao gồm trong sgi :: slist và forward_list bao gồm hàm thành viên emplace_after không được bao gồm trong sgi :: slist. Ngoài ra, forward_list không cung cấp chèn và xóa các hàm thành viên như sgi :: slist.

Nếu bạn biết về bất kỳ sự khác biệt nào khác, vui lòng đề cập đến chúng.

Answer 3

Gần đây tôi đã gặp sự cố khác. Phương thức splice_after có giao diện khác và hành vi khác.

1) forward_list Đòi hỏi bạn để vượt qua container bạn đang di chuyển từ như một cuộc tranh luận thứ hai:

void splice_after(const_iterator pos, forward_list& other, 
        const_iterator first, const_iterator last); 

slist:

void splice_after(iterator pos, iterator before_first, iterator before_last) 

này cũng tương tự đối với các quá tải.

2) Cụ thể cho tình trạng quá tải nêu trên: trình lặp cuối cùng được diễn giải khác nhau! Khi slist di chuyển phạm vi [before_first + 1, before_last + 1>, forward_list sẽ di chuyển phạm vi < đầu tiên, cuối cùng>. Vì vậy, khi chuyển đổi mã (vì slist không được dùng trong GCC chẳng hạn), hãy đảm bảo sử dụng: last = before_last + 1.