STL Priority Queue — удаление элемента

Однажды у меня был точно такой же сценарий, и я сделал следующее:

• структура, которую я сохранил в std::priority_queue, содержала только время для сортировки и индекс для std::vector<Handler> (в моем случае Handler было boost::function, но также могло быть указателем на интерфейс или функцию)
• при добавлении таймера я находил свободный индекс в векторе обработчиков¹ и сохранял обработчик по этому индексу. Сохраните индекс и время в priority_queue. Верните индекс клиенту в качестве токена для отмены
• чтобы отменить таймер, передайте индекс, полученный при его добавлении. Очистите обработчик по этому индексу (для boost::function вызовите clear(), если используете указатели, установите его равным нулю)
• когда пришло время вызвать таймер, получить его индекс обработчика из очереди приоритетов и проверить вектор обработчиков - если обработчик в этой позиции пуст ()/NULL, таймер был отменен. Отметьте этот индекс обработчика как свободный².

¹ Чтобы быстро найти свободный индекс, я использовал отдельные std::stack индексов. При добавлении таймера, когда этот стек пуст, добавьте в конец вектора; в противном случае вытащите верхний индекс и используйте его.

² Вот момент, когда вы помещаете индекс в стек свободных индексов

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

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

delete_heap(iterator to_delete, iterator heap_begin, iterator heap_end)
{
  to_delete->key = something that would compare less to everything; // make sure it gets to the top in the next step
  std::push_heap(heap_begin, to_delete+1);
  std::pop_heap(heap_begin, heap_end);
}

что позволит вам O(log n) удалить.

Несмотря на то, что говорят некоторые другие ответы, можно получить доступ к базовому контейнеру любого стандартного адаптера контейнера, включая priority_queue, поскольку контейнер отображается как защищенный член с именем c. Вы можете либо наследовать от priority_queue и расширить интерфейс, либо использовать грязные приемы, такие как deque-from-a-stack/3034221#3034221">это, чтобы временно получить доступ к обычному файлу priority_queue.

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

Если отмена таймера происходит часто, вам нужно использовать какую-то другую структуру. std::map тоже не так уж плох, хотя стоимость delete_min возрастет.

Если отмена таймера происходит редко, то пометка элемента как удаленного (и игнорирование его во время ::pop) может помочь.

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

У меня было такое же требование. Если у вас есть возможность изменить контейнер, проблему может решить std:: set (дубликаты не допускаются) или std::multiset.

Оба упорядочены и могут стирать элемент, логарифмический по размеру контейнера (подробности см. в документации). Для помощи в удалении в мультинаборе вы можете увидеть это.

Посмотрите разницу std::set vs std::priority_queue, прежде чем принять решение.