Преимущества настройки контейнера priority_queue

Question

С помощью stl priority_queue вы можете установить базовый контейнер, например, vector.Каковы некоторые преимущества указания контейнера для stl priority_queue?

Answer 1

Установка нижележащего контейнера позволяет выделить две логически разделенные задачи:

1. Как вы храните фактические элементы, которые составляют приоритетную очередь (контейнер), и
2. Как организовать эти элементы для эффективной реализации очереди приоритетов (класс адаптера priority_queue).

В качестве примера, стандартная реализация vector не обязана сжиматься, когда ее емкость значительно превышает ее фактический размер. Это означает, что если у вас есть приоритетная очередь, подкрепленная vector, вы можете в конечном итоге тратить память, если ставите в очередь много элементов, а затем удаляете все из них в очередь, поскольку vector сохранит свою прежнюю емкость. Если, с другой стороны, вы реализуете свой собственный класс shrinking_vector, который фактически уменьшает его емкость при необходимости, вы можете получить все преимущества интерфейса priority_queue, в то время как хранилище будет использоваться более эффективно.

Другой возможный пример - вы можете захотеть изменить используемый распределитель так, чтобы элементы очереди с приоритетами выделялись из специального пула ресурсов. Вы можете сделать это, просто установив тип контейнера priority_queue равным vector с пользовательским распределителем.

Еще одна мысль - предположим, что вы храните priority_queue очень больших объектов, время копирования которых очень велико. В этом случае тот факт, что vector динамически изменяет свой размер и копирует свои старые элементы (или, по крайней мере, в компилятор C ++ 03), может быть тем, за что вы не готовы платить. Таким образом, вы могли бы переключиться на какой-то другой тип, например deque, который старается не копировать элементы при изменении размера и мог бы добиться больших выигрышей в производительности.

Надеюсь, это поможет!

Answer 2

Класс priority_queue является примером шаблона адаптера . Он предоставляет способ предоставления услуг очереди с приоритетами над существующим набором данных. Как адаптер, он на самом деле требует базового контейнера. По умолчанию указывается vector. (с здесь ).

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

• front
• push_back
• pop_back

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

Два примера, которые реализуют это в STL: vector и deque. Оба имеют разные характеристики производительности. Например, vector обычно является непрерывным в памяти, тогда как deque обычно не является. Операция push_back в векторе является только амортизированным постоянным временем (возможно, придется перераспределить вектор), тогда как для deque она указана в постоянном времени.