Перезаписать элементы в конце очереди с приоритетами, как только указанная емкость будет достигнута?
Я пытаюсь найти ближайшие N точек в четырехугольном дереве и использую очередь приоритетов STL для хранения точек по мере их нахождения (отсортировано по расстоянию от точки запроса).
Точки, превышающие максимальное расстояние от точки запроса, никогда не добавляются в очередь. Тем не менее, я также хотел бы сократить количество элементов, которые могут быть возвращены при поиске. В настоящее время я добавляю все точки, которые ближе к точке запроса, чем максимальное расстояние, а затем считываю только верхние N точек из очереди.
В тестировании это слишком медленно — простое добавление каждой точки ближе, чем максимальное расстояние, приводит к замедлению по мере добавления большего количества точек. Вместо этого я хотел бы добавить больше точек в очередь, если либо: в очереди находится меньше, чем N точек, или рассматриваемая точка находится ближе к точке запроса, чем N-ая точка в очереди, и в этом случае эта точка переопределяется и не увеличивает количество элементов в очереди.
Есть ли способ сделать это с приоритетной очередью STL, или я могу написать свою собственную единственную?
Решение
Нужно ли знать текущие N лучших точек, пока вы их просматриваете? Если нет, возможно, вы можете добавить все точки в контейнер с произвольным доступом (например, std::vector) и просто позвонить std::partial_sort в конце, чтобы получить N лучше.
Если вам действительно нужно сделать это с приоритетной очередью, std::priority_queue не хватит Вы могли бы положить что-то вместе с std::algorithm куча функций, которая позволяет вам получить доступ к базовому контейнеру.
Другие решения
Других решений пока нет …