Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

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

Role of container in priority_queue
Автор rajutsav1234, история, 3 года назад, По-английски

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.

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

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

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).

→ Ответить