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

Question

Я хочу реализовать систему очередей с таймером, используя C ++ STL priority_queue контейнерный адаптер.

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

Спасибо за вашу помощь.

Answer 1

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

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

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

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

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

Answer 2

Боюсь, 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) удалить.

Answer 3

Несмотря на то, что говорят некоторые другие ответы, можно получить доступ к нижележащему контейнеру любого стандартного контейнерного адаптера, включая priority_queue, поскольку контейнер открыт как защищенный элемент, называемый c.Вы можете либо наследовать от priority_queue и расширять интерфейс, либо использовать грязные приемы, такие как this , чтобы временно получить доступ к обычному priority_queue.

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

См. Разницу std :: set vs std :: priority_queue до принятия решения.