Приоритетная Очередь STL - удаление объекта
Я хочу реализовать систему массового обслуживания таймера с помощью STL C++ priority_queue контейнерный адаптер.
Моя проблема состоит в том, что я хочу иногда отменить таймер, однако нет никаких интерфейсов, которые позволяют мне легко удалить объект в priority_queue, который не является главным объектом.
Какие-либо предложения?.
Спасибо за помощь.
5 ответов
Однажды у меня был точно такой же сценарий, и я сделал следующее:
- структура, которую я хранил в
std::priority_queue, содержала только время сортировки и индекс кstd:: vector(в моем случаеHandlerбылboost::function, но мог быть и указателем на интерфейс или функцию) - при добавлении таймера я бы нашел свободный индекс в векторе обработчиков1 и сохранил обработчик по этому индексу. Храните индекс и время в priority_queue. Верните индекс клиенту как токен для отмены
- Для отмены таймера передайте индекс, полученный при его добавлении. Очистите обработчик по этому индексу (для
boost::functionвызовитеclear(), при использовании указателей установите его в ноль) - когда придет время обратного вызова таймера, получите индекс его обработчика из очереди приоритетов и проверьте вектор обработчиков - если обработчик в этой позиции пуст()/NULL, таймер был отменен. Пометьте этот индекс обработчика как свободный2.
1 Чтобы быстро найти свободный индекс, я использовал отдельный std::stack индексов. Если добавляется таймер и этот стек пуст, добавляйте в конец вектора; в противном случае извлеките верхний индекс и используйте его.
2 Вот момент, когда вы выталкиваете индекс в стек свободных индексов
Вся эта процедура несколько сложна и чревата ошибками, особенно если ваши обратные вызовы таймеров должны добавлять или отменять таймеры. Вот ссылка на мой класс отменяющего таймера, описанный выше, этот код является общественным достоянием
Несмотря на то, что говорят некоторые другие ответы, можно получить доступ к базовому контейнеру любого стандартного адаптера контейнера, включая priority_queue , поскольку контейнер представлен как защищенный элемент с именем c . Вы можете либо унаследовать от priority_queue и расширить интерфейс, либо использовать грязные уловки, такие как this , чтобы временно получить доступ к обычной priority_queue .
Моя проблема в том, что я хочу иногда отменять таймер, но не существует интерфейсов, позволяющих легко удалить элемент в priority_queue, который не является верхним.
Если отмена таймера происходит часто, то нужно использовать какую-то другую структуру. std::map тоже не так уж плох, хотя стоимость delete_min увеличится.
Если отмена таймера происходит редко, то пометка элемента как удаленного (и игнорирование его во время ::pop) может сработать.
Боюсь, что 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) delete.
Контейнер priority_queue STL специально разработан так, что доступен только верхний элемент, поэтому, если вам нужно иметь возможность удалять не верхние элементы, вам придется найти другой класс для использования.