Hàng đợi ưu tiên STL - xóa một mục

Question

Tôi muốn triển khai hệ thống xếp hàng giờ bằng bộ chuyển đổi container C++ STL priority_queue.

Vấn đề của tôi là thỉnh thoảng tôi muốn hủy hẹn giờ, tuy nhiên không có giao diện cho phép tôi dễ dàng xóa một mục trong priority_queue không phải là mục trên cùng.

Mọi đề xuất ?.

Cảm ơn sự giúp đỡ của bạn.

Answer 1

tôi đã có kịch bản chính xác cùng một lần và đã làm như sau: cấu trúc tôi giữ trong std::priority_queue

• chứa chỉ có thời gian để sắp xếp theo và một chỉ số để một std::vector<Handler> (trong trường hợp của tôi Handler là boost::function, nhưng cũng có thể là con trỏ đến giao diện hoặc chức năng)
• khi thêm bộ hẹn giờ, tôi sẽ tìm thấy chỉ mục miễn phí trong vectơ của bộ xử lý và lưu trình xử lý tại chỉ mục đó. Lưu trữ chỉ mục và thời gian trong priority_queue. Trả lại chỉ mục cho khách hàng dưới dạng mã thông báo để hủy
• để hủy hẹn giờ, chuyển chỉ mục nhận được khi thêm nó. Xóa bộ xử lý tại chỉ mục đó (đối với boost::function gọi clear(), nếu sử dụng con trỏ, đặt thành 0)
• khi đến lúc gọi lại bộ đếm thời gian, nhận chỉ số xử lý từ hàng đợi ưu tiên và kiểm tra bộ xử lý vectơ - nếu trình xử lý tại vị trí đó trống()/NULL, bộ hẹn giờ đã bị hủy. Đánh dấu chỉ mục xử lý đó là miễn phí .

Để thực hiện việc tìm kiếm một chỉ số miễn phí nhanh chóng, tôi đã sử dụng một riêng biệt std::stack của chỉ số. Khi thêm bộ hẹn giờ và ngăn xếp đó trống, hãy thêm vào cuối vectơ; nếu không thì hãy bật chỉ mục trên cùng và sử dụng nó.

Đây là thời điểm khi bạn đẩy chỉ số để các chỉ số miễn phí ngăn xếp

Toàn bộ điều là hơi khó khăn và dễ bị lỗi, đặc biệt là nếu callbacks hẹn giờ của bạn cần phải thêm hoặc hủy bỏ giờ. Here's a link to my canceling timer class described above, this code is public domain

Answer 2

Vùng chứa STL priority_queue được thiết kế đặc biệt để chỉ có thể truy cập vào mục trên cùng, vì vậy nếu bạn cần xóa các mục không phải trên cùng, bạn sẽ phải tìm một lớp khác để sử dụng.

Answer 3

Tôi sợ STL priority_queue không cung cấp chức năng như vậy. Bạn có thể viết lớp heap của riêng bạn (mà không phải là khó). Bạn thậm chí có thể sử dụng các chức năng std::xxx_heap bằng các thủ thuật bẩn như sau:

delete_heap(iterator to_delete, iterator heap_begin, iterator heap_end) 
{ 
    to_delete->key = something that would compare less to everything; // make sure it gets to the top in the next step 
    std::push_heap(heap_begin, to_delete+1); 
    std::pop_heap(heap_begin, heap_end); 
} 

sẽ giúp bạn xóa O(log n) xóa.

Answer 4

Vấn đề của tôi là thỉnh thoảng tôi muốn hủy hẹn giờ, tuy nhiên không có giao diện cho phép tôi dễ dàng xóa một mục trong priority_queue không phải là mục trên cùng.

Nếu hủy hẹn giờ xảy ra thường xuyên, thì bạn cần sử dụng một số cấu trúc khác. std :: bản đồ không phải là xấu quá, mặc dù chi phí của delete_min sẽ đi lên.

Nếu hủy hẹn giờ xảy ra hiếm khi, hãy đánh dấu phần tử là đã xóa (và bỏ qua phần tử trong lúc :: pop) có thể thực hiện thủ thuật.

Answer 5

Mặc dù một số câu trả lời khác nói, có thể truy cập vào thùng chứa bên dưới của bất kỳ bộ điều hợp container tiêu chuẩn nào, bao gồm priority_queue, vì thùng chứa được tiếp xúc với tư cách thành viên được bảo vệ có tên c. Bạn có thể kế thừa từ priority_queue và mở rộng giao diện hoặc sử dụng các thủ thuật bẩn như this để tạm thời có quyền truy cập vào một số thông thường priority_queue.

Answer 6

Tôi có cùng yêu cầu. Nếu bạn có quyền tự do thay đổi vùng chứa, người có thể giải quyết vấn đề này là std::set (không cho phép trùng lặp) hoặc std::multiset.

Cả hai được đặt hàng và có thể xóa một phần tử lôgarít trong kích thước vùng chứa (xem tài liệu để biết chi tiết). Để được trợ giúp xóa nhiều tập, bạn có thể muốn xem this.

Xem sự khác biệt std::set vs std::priority_queue trước khi quyết định.