Изменить функцию сортировки приоритетной очереди во время выполнения

Question

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

Возможно ли это? Или я могу сделать указатель на очередь, чтобы при необходимости указывать на отсортированную очередь?

Answer 1

Это невозможно, поскольку функция Compare, заданная для priority_queue, является типом шаблона, это означает, что сам Compare принадлежит этому типу.

Эти:

std::priority_queue<int, std::vector<int>, std::less<int>>;
std::priority_queue<int, std::vector<int>, std::greater<int>>;

Хотя на вид похожи, есть два разных типа.

То, что вы можете сделать, - это адаптировать вашу функцию Compare для просмотра какого-либо внешнего состояния и сортировки на основе этого.

Answer 2

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

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

Единственный способ изменить порядок std::priority_queue - это создать новую очередь с новой функцией упорядочения, а затем скопировать элементы из старого в новая очередь.