Как перебрать на boost :: mutable_queue

Question

Мне нужна очередь приоритетов, в которой я могу увеличить или уменьшить клавишу приоритета. Так что boost :: mutable_queue показался идеальным, несмотря на отсутствие документации.

Проблема в том, что в какой-то момент мне нужно выполнить итерацию по всем элементам в очереди. Как я могу это сделать?

Или есть какая-то другая структура данных, которая будет работать (желательно в ускорении)?

Answer 1

Очереди не для итерации. Весь смысл очереди в том, что вы можете только смотреть на элемент в начале очереди.

Если вы хотите повторить, то я предлагаю просто использовать std::set, который упорядочен. Если вы хотите изменить элемент, вам придется удалить его и заново вставить его с новым ключом. Вы можете получить элемент с наивысшим приоритетом, используя mySet.begin() (который возвращает итератор).

В идеале, вы захотите использовать кучу. STL предоставляет функции для создания кучи, и это то, что std::priority_queue использует. Однако вы не можете изменять ключи в куче, потому что нет интерфейса для этого.

Если вы сами управляете кучей, тогда можете. Однако вам необходимо использовать функцию std::__adjust_heap из <heap.h>, которая не имеет документов. Вы можете прочитать все о том, почему эта функция недокументирована в этом интервью с Александром Степановым (изобретатель STL). Его пришлось «удалить», потому что очевидно, что STL был слишком большим, что также произошло с хэш-картами из исходного стандарта.

Answer 2

Проблема в том, что в какой-то момент мне нужно выполнить итерацию по всем элементам в очереди. Как я могу это сделать?

mutable_queue - это просто адаптер. Пройдите в соответствующий нижележащий контейнер. Также обратите внимание, что, будучи адаптером, он изменяет интерфейс, который вам доступен. По определению очереди, как правило, не допускают итерации. Если бы это было так, не было бы необходимости иметь этот адаптер. См. Документацию SGI STL по этому ограничению.

Или есть какая-то другая структура данных, которая будет работать (желательно в ускорении)?

Возможно, вам нужно использовать другую структуру данных для ваших целей. Выбор зависит от того, как вы хотите хранить ваши данные и получать к ним доступ. Возможно, вы захотите взглянуть на контейнер std::deque. Однако вам нужно будет кодировать приоритет как часть состояния содержащихся объектов.