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

Question

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

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

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

Мои вопросы:

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

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

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

Answer 1

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

Да.

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

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

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

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

Answer 2

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

Из документов:

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

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

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