Thực hiện hàng đợi ưu tiên có thể được lặp lại trong C++

Question

Tôi cần triển khai hàng đợi ưu tiên cho một dự án, nhưng ST23's priority_queue không được chỉ định vì chúng ta cần lặp lại tất cả các phần tử và xóa chúng một cách ngẫu nhiên.

Chúng tôi đang suy nghĩ về việc sử dụng STL's set cho việc này, gói nó trong một lớp học để làm cho nó một ADT.

Có giải pháp thông minh hơn cho điều này không?

Làm cách nào để chúng tôi có thể sử dụng công khai một số chức năng thành viên công khai của set? Chúng tôi quan tâm đến việc lặp vv

Rõ ràng bắt nguồn STL là không khôn ngoan vì sự thiếu destructors ảo:/

---

Code mới:

#ifndef PRIORITYQUEUE_H_ 
#define PRIORITYQUEUE_H_ 

#include <set> 

template<typename T, template<typename X> class impl_type = std::set> 
class PriorityQueue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
public: 
    void push(const T& x) { 
     insert(x); 

    } 

    void pop() { 
     erase(begin()); 
    } 

    const T& top() const { 
     return *begin(); 
    } 
}; 

#endif /* PRIORITYQUEUE_H_ */ 

Vì vậy, chúng tôi hiện có điều này. Trình biên dịch không phàn nàn về chèn, nhưng nó không phàn nàn về erase(begin()) và return *begin():

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

Tại sao điều này?

Answer 1

Bạn sẽ có thể triển khai hàng đợi ưu tiên của riêng mình bằng cách sử dụng std::vector, std::make_heap, std::push_heap và std::pop_heap. Đây có phải là cách std::priority_queue được triển khai không? Bạn sẽ chỉ cần gọi lại std::make_heap để sửa cấu trúc dữ liệu khi bạn xóa một phần tử ngẫu nhiên.

Bạn có cần phải lặp qua các phần tử theo thứ tự không? Có một thuật toán std::sort_heap để đặt hàng số std::vector cơ bản.

Answer 2

Bạn có thực sự cần hàng đợi ưu tiên không?

Bạn cần lặp qua tất cả các mặt hàng và loại bỏ một cách ngẫu nhiên -> danh sách liên kết

Nếu bạn cần để giữ cho danh sách được sắp xếp, sắp xếp nó ngay từ đầu và sau đó, khi chèn mục mới, sử dụng sắp xếp chèn (chèn mục mới đúng nơi).

Answer 3

Tập hợp STL có thể sử dụng được để thực hiện những gì bạn muốn, mặc dù tôi phải lưu ý rằng danh sách các yêu cầu có vẻ hơi lạ. Bạn chỉ có thể xác định một loại mới.

template<typename T, template<typename X> class impl_type = std::set> class prio_queue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
    // etc 
public: 
    // Forward the set's members 
    T& top() { 
     return *begin(); 
    } 
    // etc 
}; 

Answer 4

Tôi sẽ làm theo ví dụ được thiết lập bởi một số bộ điều hợp vùng chứa khác trong thành phần sử dụng thư viện chuẩn và tạo kiểu chứa tham số mẫu bên dưới. Mặc dù đó là một dự án trường học có thể là quá linh hoạt. Bạn có thể bắt đầu bằng cách sử dụng bố cục với một trong các Vùng chứa hiện có và xây dựng từ đó nếu cần.