# C++: k-Nearest Neighbours with Lambdas and Priority Queues

I implemented getting the $$\k\$$-nearest neighbours of an origin point to a set of points in C++17. I tried to use some more modern C++ lambda techniques and was looking for feedback on use of lambdas, auto return types, and using a custom comparison function with priority queue.

1. Should other lambdas be captured by referenced or by value?
2. For auto return types, when should you use the arrow notation to signify a return type?
3. Is there a cleaner way to declare the type of queue in the code below?

Other feedback is welcome too.

#include <algorithm>
#include <iostream>
#include <queue>

using Point = std::pair<int, int>;

auto knn(const std::vector<Point>& points,
const Point& origin,
const int k) -> std::vector<Point> {
auto squared_distance = [&origin](const Point& p) {
const int dx = std::get<0>(p) - std::get<0>(origin);
const int dy = std::get<1>(p) - std::get<1>(origin);
return dx*dx + dy*dy;
};

auto closer = [&squared_distance](const Point& p1, const Point& p2) {
return squared_distance(p1) > squared_distance(p2);
};
std::priority_queue<Point, std::vector<Point>, decltype(closer)> queue(closer);

for (const auto& point : points) {
queue.push(point);
}

std::vector<Point> nearest_neighbours;
for (int i = 0; i < k; ++i) {
nearest_neighbours.emplace_back(std::move(queue.top()));
queue.pop();
}
return nearest_neighbours;
}


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 <iostream>
#include <vector>
#include <algorithm>

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

for(auto &v: vs) {
std::generate_n(std::back_inserter(v), 5, generator); // try using iota directly
for(auto i: v)
std::cout << i << ' ';
std::cout << '\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) -> 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("Square root of 4 is %d\n", 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<(), another one (as pointed out by Mikael H) is to just define a global overload for operator< that takes two Points:

bool operator<(const Point& p1, const Point& p2) {
return closer(p1, p2);
}


Then you can just write:

std::priority_queue<Point> 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<Point> nearest_neighbours(k);
std::partial_sort_copy(points.begin(), points.end(), nearest_neighbours.begin(), neareset_neighbours.end(), closer);
return nearest_neighbours;

• I don't agree lambdas are like passing a function pointer (in C). A lambda is basically a class, containing members corresponding to its closure. The same rules as for classes should hold for lambdas - if the lambda/class is small, a copy is suitable, otherwise a reference might be better (ignoring lifetime). Jun 15 '20 at 10:20
• Also note that Point does not need to be a class to define the operator>. It is sufficient to create a free function bool operator>(const Point& p1, const Point& p2) for std::priority_queue to find the comparison operator without having to have it passed. Jun 15 '20 at 10:22
• @MikaelH You're correct that a lambda expression is basically an object, which has storage if there are captures. But I don't think it matters if it is captured by reference or not, since if anything is captured, it can only be passed to template functions, which will always be inlined, so the compiler is always able to optimize it regardless of whether it's a reference or not? It's different for mutable lambdas though, there copy vs. reference would make a semantic difference. Jun 15 '20 at 12:18
• I think that it's still an object, regardless of what you do with it. A lambda is a class like any other, with the type being unnamed. Putting the code to cppinsights gives cppinsights.io/s/7fe0d32a. Using reference or value will create an object reference or object - impacting size. Just as you would use value or reference when adding a member to a class, you should probably do the same for lambdas. Jun 15 '20 at 12:45
• @MikaelH Interestingly, passing the lambda by value results in slightly shorter assembly output by both GCC and Clang, see this diff for example: godbolt.org/z/cL3W8X Jun 15 '20 at 12:56