std :: forward_list và std :: forward_list :: push_back

Question

Tôi muốn sử dụng std::forward_list

Bởi vì:

Chuyển danh sách là một container mà hỗ trợ chèn nhanh và loại bỏ của các yếu tố từ bất cứ nơi nào từ vùng chứa

Nhưng không có * std :: forward_list :: push_back * implementation.

Có cách hiệu năng cao để thêm hỗ trợ cho một hoặc không có lý do để làm điều đó không?

Answer 1

std::forward_list hỗ trợ chèn nhanh và xóa, nhưng không chuyển tải đến cuối. Để thực hiện .push_back, trước tiên bạn sẽ cần đến cuối danh sách, là O (N) và không nhanh chút nào, đó có thể là lý do tại sao nó không được triển khai.

 

Bạn có thể tìm ra iterator tới phần tử cuối cùng bằng cách tăng .before_begin N lần

auto before_end = slist.before_begin(); 
for (auto& _ : slist) 
    ++ before_end; 

và sau đó sử dụng .insert_after hoặc .emplace_after để chèn các phần tử:

slist.insert_after(before_end, 1234); 

Answer 2

Có không push_back vì danh sách không theo dõi mặt sau của danh sách , chỉ có mặt trước.

Bạn có thể viết trình bao bọc quanh danh sách duy trì một trình lặp đến phần tử cuối cùng và triển khai push_back bằng cách sử dụng insert_after hoặc push_front tùy thuộc vào việc danh sách có trống không. Điều này sẽ trở nên khá phức tạp nếu bạn muốn hỗ trợ các hoạt động phức tạp hơn (ví dụ: sort và splice_after).

Hoặc, nếu bạn không cần push_back để nhanh chóng, thật dễ dàng để thực hiện điều đó trong thời gian tuyến tính.

Trừ khi bộ nhớ vô cùng chặt chẽ, giải pháp tốt nhất là sử dụng list. Điều này có các đặc điểm hiệu suất giống như forward_list và là hai chiều, hỗ trợ push_back cũng như push_front; chi phí là một con trỏ thêm cho mỗi phần tử.

Answer 3

Điểm của lệnh std :: forward_list là một phiên bản std :: stripped-stripped xuống, vì vậy nó không lưu trữ một iterator cho phần tử cuối cùng. Nếu bạn cần một, bạn sẽ phải duy trì nó cho mình, như vậy:

forward_list<int> a; 

auto it = a.before_begin(); 

for(int i = 0; i < 10; ++i) 
    it = a.insert_after(it, i); 

Answer 4

Tôi khuyên bạn nên chống lại std::forward_list giống như tôi khuyên bạn nên chống lại std::list trong hầu hết mọi tình huống. Cá nhân, tôi chưa bao giờ tìm thấy một tình huống trong mã của tôi, nơi một danh sách liên kết là cấu trúc dữ liệu tốt nhất.

Trong C++, bộ sưu tập dữ liệu truy cập mặc định của bạn phải là std::vector. Nó cung cấp cho bạn hiệu quả push_back, nếu đó là những gì bạn thực sự cần. Về mặt kỹ thuật, nó không cung cấp cho bạn hiệu quả xóa và chèn từ giữa nếu bạn chỉ nhìn vào các phép đo phức tạp lớn-O trừu tượng của một phép toán đó.Tuy nhiên, trong thế giới thực, std::vector vẫn thắng ngay cả khi chèn và xóa ở giữa.

Ví dụ: Bjarne Stroustrup đã tạo thử nghiệm 100.000 phần tử std::list và std::vector. Anh ta sẽ tìm kiếm từng phần tử và xóa nó. Sau đó, anh ta sẽ tìm thấy một điểm chèn và chèn vào giữa. Anh ta có thể sử dụng tìm kiếm nhị phân trên std::vector, nhưng không làm cho việc so sánh 'công bằng hơn'.

Kết quả cho thấy một chiến thắng mạnh mẽ cho std::vector, ngay cả trong trường hợp này, nơi std::list được cho là mạnh mẽ. Đơn giản chỉ cần đi qua các std::list mất nhiều thời gian hơn vì cách xa nhau trong bộ nhớ tất cả các đối tượng được. std::list không thân thiện với bộ nhớ cache, có thể là điều quan trọng nhất đối với các bộ vi xử lý hiện đại.

The complete talk by Bjarne Stroustrup

Thorough explanation of the effects, with benchmarks at multiple sizes

Lưu ý rằng liên kết thứ hai này ở đây đưa ra một số tình huống mà bạn có thể có thể muốn sử dụng một std::list, chẳng hạn như khi kích thước của các yếu tố là lớn. Tuy nhiên, tôi đã ở trong một tình huống mà tôi có nhiều yếu tố theo một thứ tự cụ thể và cần phải xóa một số.

Các thành phần này lớn hơn bất kỳ loại được cài sẵn nào, nhưng không lớn, có lẽ 20-30 byte mỗi trên máy tính 32 bit). Số lượng các phần tử đủ lớn để toàn bộ cấu trúc dữ liệu của tôi là vài trăm MiB. Thu thập dữ liệu là tập hợp các giá trị về mặt lý thuyết có thể là hợp lệ dựa trên thông tin hiện đã biết. Thuật toán được lặp lại trên tất cả các phần tử và các phần tử đã xóa không còn hợp lệ dựa trên thông tin mới nữa, với mỗi lần vượt qua có thể xóa khoảng 80% các phần tử còn lại.

Triển khai đầu tiên của tôi là cách tiếp cận đơn giản std::vector nơi tôi đã xóa các phần tử không hợp lệ khi tôi duyệt qua. Điều này làm việc cho các bộ dữ liệu thử nghiệm nhỏ, nhưng khi tôi cố gắng làm điều thực sự, nó quá chậm để có ích. Tôi đã chuyển sang std::list làm vùng chứa, nhưng sử dụng cùng một thuật toán và tôi thấy các cải thiện hiệu suất đáng kể. Tuy nhiên, nó vẫn còn quá chậm để có ích. Thay đổi chiến thắng là chuyển đổi về số std::vector, nhưng thay vì xóa các yếu tố ở vị trí xấu, tôi đã tạo một std::vector mới và bất kỳ yếu tố nào tôi thấy tốt đều được đưa vào đó std::vector và sau đó ở cuối hàm Tôi chỉ đơn giản là loại bỏ các std::vector cũ và sử dụng mới, và điều này đã cho tôi về nhiều tốc độ lên trên std::list như std::list đã cho tôi hơn thực hiện std::vector ban đầu của tôi, và điều này chỉ đủ nhanh để có ích.

Answer 5

Unfortunatelly Tôi không thể thêm nhận xét (danh tiếng thấp) nhưng tôi chỉ muốn đề cập rằng một trong những lợi thế của danh sách forward232 là các thao tác chèn-xóa không làm mất hiệu lực vòng lặp. Tôi đã có một ứng dụng mà bộ sưu tập các phần tử đang phát triển trong khi lặp lại và xử lý các phần tử riêng lẻ. Sự vắng mặt của việc vô hiệu hóa vòng lặp cho phép tôi thực hiện quét phân đoạn (bắt đầu danh sách khi bắt đầu phân đoạn và bắt đầu phân khúc cuối cùng là kết thúc).