Преимущества установки 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 является примером adapter pattern. Он предоставляет способ предоставления услуг очереди приоритетов по существующему набору данных. В качестве адаптера на самом деле требуется базовый контейнер. По умолчанию он задает vector. (от here).

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

• front
• push_back
• pop_back

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

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