Я написал несколько методов запроса K-ближайших соседей, которые строят список точек, ближайших к данной точке запроса.Чтобы поддерживать этот список соседей, я использую std::priority_queue так, чтобы верхний элемент был самым дальним соседом к точке запроса.Таким образом, я знаю, должен ли я нажать новый элемент, который в данный момент проверяется (если он находится на меньшем расстоянии, чем текущий самый дальний сосед), и может выдавать () самый дальний элемент, когда моя очередь приоритетов имеет более K элементов.
Пока все хорошо.Однако при выводе элементов я бы хотел упорядочить их от ближайшего к самому дальнему.В настоящее время я просто извлекаю все элементы из очереди приоритетов и помещаю их в выходной контейнер (через итератор), что приводит к последовательности точек, упорядоченных от самого дальнего к ближайшему, поэтому затем я вызываю std::reverse длядиапазон итератора вывода.
В качестве простого примера приведем линейный поиск, использующий очередь приоритетов (очевидно, используемые мной методы запросов к ближайшим соседям гораздо сложнее):
template <typename DistanceValue,
typename ForwardIterator,
typename OutputIterator,
typename GetDistanceFunction,
typename CompareFunction>
inline
OutputIterator min_dist_linear_search(ForwardIterator first,
ForwardIterator last,
OutputIterator output_first,
GetDistanceFunction distance,
CompareFunction compare,
std::size_t max_neighbors = 1,
DistanceValue radius = std::numeric_limits<DistanceValue>::infinity()) {
if(first == last)
return output_first;
typedef std::priority_queue< std::pair<DistanceValue, ForwardIterator>,
std::vector< std::pair<DistanceValue, ForwardIterator> >,
detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction> > PriorityQueue;
PriorityQueue output_queue = PriorityQueue(detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction>(compare));
for(; first != last; ++first) {
DistanceValue d = distance(*first);
if(!compare(d, radius))
continue;
output_queue.push(std::pair<DistanceValue, ForwardIterator>(d, first));
while(output_queue.size() > max_neighbors)
output_queue.pop();
if(output_queue.size() == max_neighbors)
radius = output_queue.top().first;
};
OutputIterator it = output_first;
while( !output_queue.empty() ) {
*it = *(output_queue.top().second);
output_queue.pop(); ++it;
};
std::reverse(output_first, it);
return it;
};
Все вышеперечисленное - просто отличная вещь, за исключением одного: требуется, чтобы тип выходного итератора был двунаправленным и, по сути, указывал на предварительно выделенный контейнер.Теперь эта практика хранения выходных данных в диапазоне, заданном каким-либо итератором вывода, также великолепна и довольно стандартна (например, std::copy и другие алгоритмы STL являются хорошими примерами этого).Однако в этом случае я хотел бы иметь возможность требовать только тип прямого итератора вывода, который позволил бы использовать итераторы обратного вставки, подобные тем, которые предусмотрены для контейнеров STL и iostreams.
Итак, все сводится к обращению очереди приоритетов перед тем, как выгрузит содержимое в итератор вывода.Итак, вот лучшие варианты, которые я смог придумать:
Создайте std::vector, поместите в него содержимое очереди приоритетов и сбросьте элементы вИтератор вывода с использованием обратного итератора для вектора.
Замените std::priority_queue отсортированным контейнером (например, std::multimap), а затем выгрузите содержимое в итератор вывода.используя соответствующий порядок обхода.
Есть ли другой разумный вариант?
Я использовал std::multimap в предыдущей реализации этого алгоритма и других, так какмоего второго варианта выше.Однако когда я переключился на std::priority_queue, прирост производительности был значительным.Поэтому я бы предпочел не использовать второй вариант, так как действительно кажется, что использование очереди приоритетов для ведения списка соседей намного лучше, чем использование отсортированного массива.Кстати, я также попробовал std::vector, который я поддерживаю отсортированным с std::inplace_merge, который был лучше, чем multimap, но не соответствовал приоритетной очереди.
Что касается первого варианта, которыймой лучший вариант на данный момент, мне просто кажется расточительным делать эту двойную передачу данных (очередь -> вектор -> вывод).Я просто склонен думать, что должен быть более простой способ сделать это ... что-то, чего мне не хватает ..
Первый вариант действительно не так уж плох в этом приложении (учитывая сложностьалгоритма, который предшествует этому), но если есть хитрость, чтобы избежать этой двойной передачи памяти, я хотел бы знать об этом.