Блог пользователя gjaiswal108

Multiset vs priority_queue
Автор gjaiswal108, история, 5 лет назад, По-английски

The thing we can do with priority queue, can also be done with multiset. Then what is the quality that's unique in priority queue? Can anyone give any example where multiset fails and only priority queue works?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

More complicated data structures (those with more functionality) are usually slower. I think that's the case here too. Priority queue is faster.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

multiset has higher constant factor(for rotations and whatever) you can read more about how red-black trees works

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Others already compared tree data structures to priority queue. I want to add that I've had plenty TLE submissions with multiset I had to use map for counting number of appearance instead. multiset and multimap can be very slow when there are too many duplicated keys so keep that in mind when you use them.

→ Ответить