rajutsav1234's blog

Role of container in priority_queue
By rajutsav1234, history, 3 years ago, In English

Role of container in priority_queue of C++ STL.

Why vectors are used in container.

And what are advantages and disadvantages if I use deque instead of vector.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The design of std::priority_queue is such that you're allowed to specify which container you want to use to internally represent the priority queue. All it requires is that the container allows for random access, and has the front, push_back and pop_back functions. So both std::vector and std::deque can be used as the underlying container.

There's not really much of a difference apart from the usual difference between std::vector and std::deque. However, in practice, std::vector tends to be faster.

Reference implementations: https://judge.yosupo.jp/submission/56329 (Dijkstra with deque) and https://judge.yosupo.jp/submission/52076 (Dijkstra with vector).

→ Reply