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

Ответ 1

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

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

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

² Здесь точка, когда вы нажимаете индекс на стек бесплатных индексов

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

Ответ 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).

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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