STL приоритетная очередь с дублирующимися ключами - возможно ли это?

Question

Мне нужно сохранить объекты класса А в некоторой структуре данных. Кроме того, я бы хотел, чтобы они автоматически сортировались в соответствии с ключом, который в моем случае является встроенным объектом другого класса B.

Таким образом, я решил использовать очередь приоритетов STL.

Однако возможно, что два или более объекта B имеют одинаковое значение ключа.

Мои вопросы:

очереди Приоритет STL позволяют ли дубликаты ключей ??

Если это так, что я должен рассмотреть и какой предикат использовать?

Я знаю, что я мог бы использовать мультимножество, но его производительность нотации Big O хуже, поэтому я хочу использовать очередь приоритетов.

Answer 1

Очередь очереди STL позволяет дублировать ключи?

Да.

Если это то, что я должен считать

Это порядок между равными элементами могут изменяться произвольно.

и какой предикат использовать?

Это вы имеете в виду? Это полностью зависит от вашей семантики.

Answer 2

Да, он поддерживает дубликаты ключей.

От doucumentation:

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

Простой тест подтверждает это:

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

Выходы:

5 
5 

Что касается предиката, использования, что вы использовали бы раньше - ничто, гарантированное приоритетной очередью, не разбивается, позволяя равным элементам, поэтому ваш алгоритм должен работать просто отлично.

Answer 3

У Konrad есть отличный ответ, чтобы добавить к этому. Вы должны знать, что priority_queue не обязательно имеет отличную производительность. Согласно этой странице http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, похоже, что она реализована путем создания make_heap, pop_heap и т. Д. Для всех операций, чтобы получить наивысший приоритет.

Повторное копирование может быть дорогим по сравнению с другими структурами данных в зависимости от вашего варианта использования.