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

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

Поэтому я решил использовать приоритетную очередь STL.

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

Мои вопросы:

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

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

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


c++ stl
person Community    schedule 30.10.2008    source источник

Ответы (3)


arrow_upward
18
arrow_downward

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

да.

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

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

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

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

person Konrad Rudolph    schedule 30.10.2008

arrow_upward
5
arrow_downward

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

Из документации:

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

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

person hazzen    schedule 30.10.2008

arrow_upward
3
arrow_downward

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

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

person Evan Teran    schedule 30.10.2008
comment
Из того, что я узнал из раздела «Структуры данных», это в основном способ создания приоритетных очередей ( en.wikipedia.org /wiki/Priority_queue#Implementation, например). - person Max Lybbert; 30.10.2008
comment
Согласен, я просто указал, что приоритетные очереди не обязательно суперэффективны, потому что он упомянул, что выбрал их из-за низкой производительности набора. - person Evan Teran; 31.10.2008