Hàng đợi ưu tiên STL với các phím trùng lặp - có thể không?

Question

Tôi cần lưu trữ các đối tượng lớp A trong một số cấu trúc dữ liệu. Ngoài ra, tôi muốn chúng được sắp xếp tự động theo một khóa, trong trường hợp của tôi, một đối tượng nhúng của một lớp khác B.

Do đó tôi quyết định sử dụng hàng đợi ưu tiên STL.

Tuy nhiên, có thể có từ 2 đối tượng trở lên B có cùng giá trị khóa.

Câu hỏi của tôi:

Có hàng đợi ưu tiên STL phép phím trùng lặp ??

Nếu tôi nên xem xét điều gì và nên sử dụng vị ngữ nào?

Tôi biết tôi có thể sử dụng đa điểm nhưng hiệu suất ký hiệu Big O của nó tệ hơn, vì vậy tôi muốn sử dụng hàng đợi ưu tiên.

Answer 1

Hàng đợi ưu tiên STL có cho phép khóa trùng lặp không ??

Có.

Nếu nó làm những gì tôi nên xem xét

Đó là trật tự giữa các yếu tố bình đẳng có thể thay đổi tùy tiện.

và tôi nên sử dụng vị từ nào?

Ý của bạn là gì? Điều đó phụ thuộc hoàn toàn vào ngữ nghĩa của bạn.

Answer 2

Có, nó hỗ trợ các phím trùng lặp.

Từ doucumentation:

void push(const value_type& x) Inserts x into the priority_queue. 
           Postcondition: size() will be incremented by 1. 

Một xét nghiệm đơn giản khẳng định nó:

int main() { 
    priority_queue<int> q; 
    q.push(5); 
    q.push(5); 
    cout << q.top() << endl; 
    q.pop(); 
    cout << q.top() << endl; 
    q.pop(); 
} 

Đầu ra:

5 
5 

Đối với các vị ngữ, sử dụng bất cứ điều gì bạn có thể đã sử dụng trước đó - không có gì đảm bảo bởi hàng đợi ưu tiên bị hỏng bằng cách cho phép các phần tử bằng nhau, vì vậy thuật toán của bạn nên làm việc tốt.

Answer 3

Konrad có câu trả lời tuyệt vời, để thêm vào đó. Bạn nên biết rằng priority_queue không nhất thiết phải có hiệu suất tuyệt vời. Theo trang này http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, có vẻ như nó được thực hiện bằng cách thực hiện một make_heap, pop_heap, vv trên tất cả các hoạt động để có được ưu tiên cao nhất.

Tái phân loại, có thể tốn kém so với các cấu trúc dữ liệu khác, tùy thuộc vào trường hợp sử dụng của bạn.