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&lt;typename T, class Distance&gt;
struct Comp
{
    using result_type = typename std::result_of&lt;Distance(const T&amp;, const T&amp;)&gt;::type;
    using type = std::less&lt;result_type&gt;;
};

template&lt;class InputIt, typename T, class Distance,
class Compare = typename Comp&lt;T, Distance&gt;::type&gt;

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

    std::sort(std::begin(result), std::end(result),
        [&amp;] (const T&amp; t1, const T&amp; 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)
    {
        return std::abs(i-j);
    };

std::vector&lt;int&gt; v = {56, 10, 79841651, 45, 59, 68, -20, 0, 36, 23, -3256};
auto res = {0, 10, 23, -20, 36};
auto found = find_n_nearest(std::begin(v), std::end(v), 4, 5, distance_int);

if(std::equal(std::begin(res), std::end(res), std::begin(found)))
    std::cout &lt;&lt; "Success !" &lt;&lt; std::endl;


To illustrate the use of the comparator, let's say I now define my "neighbourhood" of ints as being as distant as possible. In a word, the opposite of the precedent example.

std::list&lt;int&gt; v = {56, 10, 79841651, 45, 59, 68, -20, 0, 36, 23, -3256};
auto res = {79841651, -3256, 68, 59, 56};
auto found = find_n_nearest(std::begin(v), std::end(v), 4, 5, distance_int, std::greater&lt;int&gt;());

if(std::equal(std::begin(res), std::end(res), std::begin(found)))
    std::cout &lt;&lt; "Success !" &lt;&lt; std::endl;


Review

When I used this function, it was convenient to me to receive the results as a std::vector&lt;T&gt; but this is not very good as a generic algorithm.

There are two problems with this : I think we should not alter the original range, so sorting it is not an option. Then we have to copy it elsewhere, and for that I used my cache vector (not that much time to think about it during the project, and it was not a critical piece of code). I thought of replacing this by providing an OutputIt to the function, indicating where to put the results (for example an user-provided vector or whatever container), but I don't think I could sort the range in my algorithm, because the Output Iterator concept is used only to ... output things.

If there are more efficient algorithms (instead of sorting from distance) to do it feel free to tell me, but that's not my main concern. I'd like to have an elegant solution, and pieces of advice on anything you think is not quite good in my code.
I think all you need is std::nth_element:

template&lt;typename Q, typename I, typename Distance&gt;
void find_n_nearest(const Q&amp; q, I first, I nth, I last, Distance dist)
{
    using T = decltype(*first);
    auto compare = [&amp;q, &amp;dist] (T i, T j) { return dist(i, q) &lt; dist(j, q); };
    std::nth_element(first, nth, last, compare);
    std::sort(first, last, compare);
}

int main()
{
    auto distance = [] (int i, int j) { return std::abs(i-j); };
    std::vector&lt;int&gt; 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.