Tôi nên sử dụng container STL nào cho FIFO?

Question

Container STL nào phù hợp với nhu cầu của tôi nhất? Về cơ bản tôi có một thùng chứa 10 phần tử rộng, trong đó tôi liên tục push_back các phần tử mới trong khi pop_front nhập phần tử cũ nhất (khoảng một triệu lần).

Tôi hiện đang sử dụng một std::deque cho công việc nhưng đã tự hỏi nếu một std::list sẽ hiệu quả hơn vì tôi sẽ không cần phải phân bổ lại bản thân (hoặc có lẽ tôi đang nhầm một std::deque cho một std::vector?). Hoặc là có một container hiệu quả hơn cho nhu cầu của tôi?

P.S. Tôi không cần truy cập ngẫu nhiên

Answer 1

Vì có vô số các câu trả lời, bạn có thể bị nhầm lẫn, nhưng để tóm tắt:

Sử dụng một std::queue. Lý do cho điều này là đơn giản: nó là một cấu trúc FIFO. Bạn muốn FIFO, bạn sử dụng một std::queue.

Điều này làm cho ý định của bạn rõ ràng với bất kỳ ai khác và thậm chí cả chính bạn. Một std::list hoặc std::deque thì không. Một danh sách có thể chèn và loại bỏ bất cứ nơi nào, mà không phải là những gì một cấu trúc FIFO là giả sử để làm, và một deque có thể thêm và loại bỏ từ hai đầu, mà cũng là một cái gì đó một cấu trúc FIFO không thể làm.

Đây là lý do bạn nên sử dụng queue.

Bây giờ, bạn đã hỏi về hiệu suất. Trước tiên, hãy luôn nhớ quy tắc quan trọng này: Đầu tiên là mã tốt, hiệu suất cuối cùng.

Lý do cho việc này rất đơn giản: những người cố gắng thực hiện trước khi làm sạch và sang trọng hầu như luôn luôn kết thúc cuối cùng. Mã của họ trở thành một mảnh của mush, bởi vì họ đã từ bỏ tất cả những gì là tốt để thực sự không có gì ra khỏi nó.

Bằng cách viết mã tốt, dễ đọc trước, hầu hết các vấn đề về hiệu năng sẽ tự giải quyết. Và nếu sau này bạn thấy hiệu suất của mình thiếu, giờ đây bạn có thể dễ dàng thêm một trình lược tả vào mã đẹp, sạch sẽ của bạn và tìm ra vấn đề ở đâu.

Điều đó tất cả đã nói, std::queue chỉ là bộ điều hợp. Nó cung cấp giao diện an toàn, nhưng sử dụng một container khác ở bên trong. Bạn có thể chọn vùng chứa cơ bản này và điều này cho phép một sự linh hoạt tốt.

Vì vậy, bạn nên sử dụng vùng chứa cơ bản nào? Chúng tôi biết rằng std::list và std::deque đều cung cấp các chức năng cần thiết (push_back(), pop_front() và front()), vì vậy, làm cách nào để chúng tôi quyết định?

Trước tiên, hãy hiểu rằng việc cấp phát bộ nhớ (và deallocating) không phải là một việc nhanh chóng để làm, nói chung, bởi vì nó liên quan đến việc đi ra ngoài hệ điều hành và yêu cầu nó làm điều gì đó. Một list phải phân bổ bộ nhớ mỗi lần một cái gì đó được thêm vào, và deallocate nó khi nó biến mất. Mặt khác,

Mặt khác, phân bổ theo khối. Nó sẽ phân bổ ít thường xuyên hơn list. Hãy coi nó như một danh sách, nhưng mỗi đoạn bộ nhớ có thể chứa nhiều nút. (Tất nhiên, tôi muốn đề nghị bạn really learn how it works.)

Vì vậy, với điều đó một mình deque sẽ hoạt động tốt hơn, vì nó không xử lý bộ nhớ thường xuyên. Trộn lẫn với thực tế bạn đang xử lý dữ liệu có kích thước không đổi, nó có thể sẽ không phải phân bổ sau khi vượt qua đầu tiên thông qua dữ liệu, trong khi một danh sách sẽ liên tục phân bổ và deallocating.

Điều thứ hai cần hiểu là cache performance. Đi ra ngoài RAM chậm, vì vậy khi CPU thực sự cần, nó làm cho tốt nhất trong thời gian này bằng cách lấy một đoạn của bộ nhớ trở lại với nó, vào bộ nhớ cache. Bởi vì deque phân bổ trong các khối bộ nhớ, có khả năng là việc truy cập vào một phần tử trong vùng chứa này sẽ khiến CPU mang lại phần còn lại của vùng chứa. Giờ đây, mọi truy cập thêm vào deque sẽ nhanh chóng, vì dữ liệu nằm trong bộ nhớ cache.

Điều này không giống như danh sách, trong đó dữ liệu được phân bổ một lần. Điều này có nghĩa rằng dữ liệu có thể được trải rộng khắp nơi trong bộ nhớ, và hiệu suất bộ nhớ cache sẽ là xấu.

Vì vậy, hãy xem xét rằng, một deque phải là lựa chọn tốt hơn. Đây là lý do tại sao nó là container mặc định khi sử dụng queue. Điều đó tất cả đã nói, đây vẫn chỉ là một (rất) giáo dục đoán: bạn sẽ phải cấu hình mã này, bằng cách sử dụng một deque trong một thử nghiệm và list trong khác để thực sự biết chắc chắn.

Nhưng hãy nhớ: lấy mã làm việc với giao diện sạch, sau đó lo lắng về hiệu suất.

John nêu lên mối quan tâm bao gồm list hoặc deque sẽ làm giảm hiệu suất. Một lần nữa, anh ta và tôi cũng không thể nói chắc chắn mà không tự mình lược tả nó, nhưng rất có thể là trình biên dịch sẽ nội tuyến các cuộc gọi mà queue tạo ra. Tức là, khi bạn nói queue.push(), nó sẽ thực sự chỉ nói queue.container.push_back(), bỏ qua cuộc gọi hàm hoàn toàn.

Một lần nữa, đây chỉ là một phỏng đoán được giáo dục, nhưng việc sử dụng queue sẽ không làm suy giảm hiệu suất, khi so sánh với việc sử dụng vùng chứa bên dưới. Như tôi đã nói trước đây, sử dụng queue, vì nó sạch sẽ, dễ sử dụng và an toàn, và nếu nó thực sự trở thành một hồ sơ vấn đề và thử nghiệm.

Answer 2

A queue có lẽ là giao diện đơn giản hơn deque nhưng đối với danh sách nhỏ như vậy, sự khác biệt về hiệu suất có thể không đáng kể.

Tương tự với số list. Nó chỉ là một sự lựa chọn của những gì API bạn muốn.

Answer 3

Kiểm tra std :: queue. Nó kết thúc tốt đẹp một loại container cơ bản, và container mặc định là std :: deque.

Answer 4

Tại sao không std::queue? Tất cả nó có là push_back và pop_front.

Answer 5

tôi liên tục push_back yếu tố mới khi pop_front ing yếu tố lâu đời nhất (khoảng một triệu lần).

Một triệu thực sự không phải là một số lớn trong tính toán. Như những người khác đã đề xuất, hãy sử dụng một giải pháp đầu tiên là std::queue. Trong trường hợp không chắc của nó là quá chậm, xác định các nút cổ chai bằng cách sử dụng một hồ sơ (không đoán!) Và tái triển khai bằng cách sử dụng một container khác nhau với cùng một giao diện.

Answer 6

Trường hợp hiệu suất thực sự quan trọng, hãy xem Boost circular buffer library.