Ưu điểm của việc đặt Prior_queue Container

Question

Với stl priority_queue, bạn có thể đặt vùng chứa bên dưới, chẳng hạn như vector. Một số lợi thế của việc xác định một container cho stl priority_queue là gì?

Answer 1

Thiết container tiềm ẩn làm cho nó có thể tách ra hai mối quan tâm một cách logic riêng biệt:

1. Làm thế nào để bạn lưu trữ các yếu tố thực tế tạo nên hàng đợi ưu tiên (container), và
2. Làm thế nào để bạn tổ chức các yếu tố đó để triển khai hiệu quả hàng đợi ưu tiên (lớp học priority_queue bộ điều hợp).

Ví dụ, việc thực hiện tiêu chuẩn vector không bắt buộc phải giảm xuống khi dung lượng của nó lớn hơn kích thước thực tế của nó. Điều này có nghĩa rằng nếu bạn có một hàng đợi ưu tiên được hỗ trợ bởi một vector, bạn có thể sẽ lãng phí bộ nhớ nếu bạn enqueue rất nhiều yếu tố và sau đó dequeue tất cả chúng, kể từ khi vector sẽ giữ công suất cũ của nó. Mặt khác, nếu bạn thực hiện lớp shrinking_vector của riêng bạn thực sự làm giảm dung lượng khi cần, bạn có thể nhận được tất cả lợi ích của giao diện priority_queue trong khi lưu trữ được sử dụng hiệu quả hơn.

Ví dụ khác có thể - bạn có thể muốn thay đổi trình phân bổ đang được sử dụng để các phần tử của hàng đợi ưu tiên được phân bổ từ một nhóm tài nguyên đặc biệt. Bạn có thể thực hiện việc này bằng cách chỉ đặt loại vùng chứa của priority_queue thành vector với trình phân bổ tùy chỉnh.

Một ý tưởng khác - giả sử bạn đang lưu trữ priority_queue đối tượng rất lớn có thời gian sao chép rất lớn. Trong trường hợp đó, thực tế là vector tự động thay đổi kích thước bản thân và sao chép các phần tử cũ của nó (hoặc ít nhất, trong trình biên dịch C++ 03) có thể là thứ bạn không sẵn sàng trả. Do đó, bạn có thể chuyển sang một số loại khác, có lẽ là deque, mà cố gắng không sao chép các phần tử khi thay đổi kích thước và có thể nhận ra một số chiến thắng hiệu suất lớn.

Hy vọng điều này sẽ hữu ích!

Answer 2

Lớp priority_queue là ví dụ về số adapter pattern. Nó cung cấp một cách để cung cấp các dịch vụ của một hàng đợi ưu tiên trên một tập dữ liệu hiện có. Là một bộ điều hợp, nó thực sự đòi hỏi một container bên dưới. Theo mặc định, nó chỉ định một vector. (từ here).

Về mặt lợi thế, nó đơn giản là linh hoạt hơn. priority_queue sử dụng các phương pháp sau của cửa hàng sao lưu và yêu cầu nó hỗ trợ các trình vòng lặp truy cập ngẫu nhiên.

• front
• push_back
• pop_back

Bằng cách cung cấp nó như một bộ chuyển đổi, bạn có thể kiểm soát các đặc tính hiệu suất bằng cách cung cấp một thực hiện khác nhau.

Hai ví dụ thực hiện điều này trong STL là vector và deque. Cả hai đều có đặc điểm hiệu suất khác nhau. Ví dụ, một số vector thường có tính chất mâu thuẫn trong bộ nhớ, trong khi thông thường, deque thì không.Các hoạt động push_back trong một vector chỉ là thời gian cố định phân bổ (nó có thể phải phân bổ lại các vector), trong khi đối với deque nó được chỉ định trong thời gian không đổi.