C++: k-Nearest Neighbours with Lambdas and Priority Queues
Answers to your questions

Should other lambdas be captured by referenced or by value?

Functionally, for non-mutable lambdas, it doesn't matter. However, if a lambda is marked mutable then capturing by value will make a copy of the lambda's state, whereas if it's a reference no copy is made. Here is an example you can try out yourself:
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

int main() {
    std::vector&lt;int&gt; vs[2];
    auto iota = [i=0]() mutable {return i++;};
    auto generator = [&amp;iota]() mutable {return iota();}; // try removing the &amp;

    for(auto &amp;v: vs) {
        std::generate_n(std::back_inserter(v), 5, generator); // try using iota directly
        for(auto i: v)
            std::cout &lt;&lt; i &lt;&lt; ' ';
        std::cout &lt;&lt; '\n';
    }
}

It's probably best to capture them by reference, unless mutable lambdas are used and you want a copy of the state to be made.

For auto return types, when should you use the arrow notation to signify a return type?

You should use it when it is important to constrain the return type, so that you don't accidentily return the wrong type. For example, if I want to write a function that calculates the square root of something, and always return the same type as the input, you should write:
auto square_root(auto value) -&gt; decltype(value) {
    return std::sqrt(value);
}

If you omit the trailing return type, then calling the above function with an int will return a double instead. And that might then be a problem if you would do something like:
printf(&quot;Square root of 4 is %d\n&quot;, square_root(4)); // runtime error


Is there a cleaner way to declare the type of queue in the code below?

Yes, if you can make the compiler deduce that it should use closer() to compare two Points. One option is to make Point a class and implement operator&lt;(), another one (as pointed out by Mikael H) is to just define a global overload for operator&lt; that takes two Points:
bool operator&lt;(const Point&amp; p1, const Point&amp; p2) {
    return closer(p1, p2);
}

Then you can just write:
std::priority_queue&lt;Point&gt; queue;

Use std::partial_sort_copy
Using a priority queue is one way to solve it, but it is a bit cumbersome here, since there is no fast way to get the first k elements out. Also, by adding all input elements to the queue, you have sorted all elements, which means you have done more work than necessary. What you want is just to do a partial sort, where you sort the input array until you get the first k smallest elements, and you don't care about the order of the rest. std::partial_sort_copy() allows you to do that, while still allowing a const reference to the input vector:
std::vector&lt;Point&gt; nearest_neighbours(k);
std::partial_sort_copy(points.begin(), points.end(), nearest_neighbours.begin(), neareset_neighbours.end(), closer);
return nearest_neighbours;