Std lib-like C++ function to find nearest elements in a container

Initial problem

For a project I found myself in the need to search for elements in a container that are the closest neighbours to another precise element I have. In my case it was points in any dimension, but it can apply to various other things that we are not used to compute "distance" for.

So I decided to write a generic function to perform this search, so I can use it for whatever type I want, provided that I can compute the "distance" between two elements of this type. I tried to make it in the style of standard library's algorithm.

My solution

template
struct Comp
{
    using result_type = typename std::result_of::type;
    using type = std::less;
};

template::type>

std::vector find_n_nearest(
    InputIt start,
    InputIt end,
    const T& val,
    size_t n,
    Distance dist,
    Compare comp = Compare())
{
    std::vector result{start, end};

    std::sort(std::begin(result), std::end(result),
        [&] (const T& t1, const T& t2)
        {
            return comp(dist(val, t1), dist(val, t2));
        });

    result.erase(std::begin(result) + n, std::end(result));

    return result;
}

What this (the function) basically does is :

• create a copy of the range we want to look in

• sort it, by comparing values returned from the distance function between val and the element of the range, so that we have the nearest neighbours of val at the begining of our vector

• compare the distances with a custom operator if provided, std::less if not

• only keep the n elements we want

Now about the boilerplate :

I want to default the Compare type to std::less, which needs a type parameter. So we need to find the return type of the Distance object provided, and my solution here is what I found to work with both functions and lambdas.

Examples

Simple use case : retrieve the nearest values to an int. Distance between two ints will be the absolute value of their substraction.

```
const auto distance_int =
[] (int i, int j)
{

I think all you need is std::nth_element:

template
void find_n_nearest(const Q& q, I first, I nth, I last, Distance dist)
{
    using T = decltype(*first);
    auto compare = [&q, &dist] (T i, T j) { return dist(i, q)  v = {56, 10, 79841651, 45, 59, 68, -20, 0, 36, 23, -3256};
    auto res = {0, 10, 23, -20, 36};

    find_n_nearest(4, v.begin(), v.begin() + 5, v.end(), distance);
    assert(std::equal(v.begin(), v.begin() + 5, res.begin()));
}

If you just need the n nearest elements but not necessarily sorted, you can skip std::sort. Then complexity is linear in n.

I have skipped the initial copy part, because it's not always needed. Feel free to add it if you like.

StackExchange Code Review Q#48470, answer score: 6