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

Question

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

template<class InputIt, typename T, class Distance,
class Compare = typename Comp<T, Distance>::type>

std::vector<T> find_n_nearest(
    InputIt start,
    InputIt end,
    const T& val,
    size_t n,
    Distance dist,
    Compare comp = Compare())
{
    std::vector<T> 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)
    {
        return std::abs(i-j);
    };

std::vector<int> 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 << "Success !" << 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<int> 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<int>());

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

Review

When I used this function, it was convenient to me to receive the results as a std::vector<T> 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.

Answer 1

I think all you need is std::nth_element:

template<typename Q, typename I, typename Distance>
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) < 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<int> 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.

Answer 2

From a design point of view, when the standard library algorithms have to return a [begin, end) range of values, they don't return a container but take an additional OutputIterator iterator (e.g. std::copy). Therefore, you function declaration should be along these lines:

template<
    typename T,
    typename InputIt,
    typename OutputIt,
    typename Distance,
    typename Compare = typename Comp<T, Distance>::type
>
void find_n_nearest(
    InputIt first,
    InputIt last,
    OutputIt d_first,
    const T& val,
    std::size_t n,
    Distance dist,
    Compare comp = Compare());

That said, the standard library algorithms also tend to return the first iterator of the output range, so the declaration would become:

template<
    typename T,
    typename InputIt,
    typename OutputIt,
    typename Distance,
    typename Compare = typename Comp<T, Distance>::type
>
OutputIt find_n_nearest(
    InputIt first,
    InputIt last,
    OutputIt d_first,
    const T& val,
    std::size_t n,
    Distance dist,
    Compare comp = Compare());

That way, your code and the client's one do no rely on a particular container type, but work with any compatible range. That's how genericity is achieved in the standard library.

Answer 3

You have a function which is performing three steps:

1. Copy the input range
2. Sort the copied range by distance to a given element
3. Erase elements from the result range

I would omit the first and last step. These are convenience elements providing no real functionality. In addition, the third step is erasing possible useful information and involves undefined behavior if the input range has not the number of requested elements (result.erase(std::begin(result) + n, std::end(result);).

Leaving the second step: Here we have a std::sort with a custom comparator operating on distances. Your comparator depends on the result type of a distance function and is not more than a type trait. You might avoid that.

An alternative implementation might be:

#include <algorithm>
#include <iterator>

// Distance
// ========

template <typename T>
struct Distance {
    T operator () (const T& a, const T&  b) {
        return std::abs(a - b);
    }
};

// Compare Distance
// ================

template <
    typename T,
    typename DistanceFunctor = Distance<T>,
    typename CompareFunctor = std::less<decltype(
        std::declval<DistanceFunctor>()(std::declval<T>(), std::declval<T>()))>>
struct CompareDistance
{
    T pivot;
    DistanceFunctor distance;
    CompareFunctor compare;
    CompareDistance(T&& pivot)
    :   pivot(std::move(pivot))
    {}

    CompareDistance(T&& pivot, DistanceFunctor&& distance)
    :   pivot(std::move(pivot)),
        distance(std::move(distance))
    {}

    CompareDistance(T&& pivot, DistanceFunctor&& distance, CompareFunctor&& compare)
    :   pivot(std::move(pivot)),
        distance(std::move(distance)),
        compare(std::move(compare))
    {}

    bool operator () (const T& a, const T& b) {
        return compare(distance(a, pivot), distance(b,  pivot));
    }
};

// Distance Sort
// =============

template <typename Iterator, typename T>
inline void distance_sort(
    Iterator first,
    Iterator last,
    T&& pivot)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    CompareDistance<value_type> compare_distance(std::move(pivot));
    std::sort(first, last, compare_distance);
}

template <typename Iterator, typename T, typename Distance>
inline void distance_sort(
    Iterator first,
    Iterator last,
    T&& pivot,
    Distance&& distance)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    CompareDistance<value_type, Distance> compare_distance(
        std::move(pivot),
        std::move(distance));
    std::sort(first, last, compare_distance);
}

template <typename Iterator, typename T, typename Distance, typename Compare>
inline void distance_sort(
    Iterator first,
    Iterator last,
    T&& pivot,
    Distance&& distance,
    Compare&& compare)
{
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    CompareDistance<value_type, Distance, Compare> compare_distance(
        std::move(pivot),
        std::move(distance),
        std::move(compare));
    std::sort(first, last, compare_distance);
}

// Test
// ====

#include <iostream>

int main() {
    std::vector<int> original = { 56, 10, 79841651, 45, 59, 68, -20, 0, 36, 23, -3256 };

    // Find closest neighbours [less]:
    std::vector<int> elements(original);
    distance_sort(begin(elements), end(elements), 4);

    for(const auto& e : elements)
        std::cout << e << ' ';
    std::cout << '\n';

    // Find closest neighbours [greater]:
    distance_sort(begin(elements), end(elements), 4, Distance<int>(), std::greater<int>());

    for(const auto& e : elements)
        std::cout << e << ' ';
    std::cout << '\n';

    // Without distance_sort, but with existing tools
    std::sort(
        begin(elements),
        end(elements),
        [](int a, int b) {
            const int pivot = 4;
            return std::abs(a - pivot) < std::abs(b - pivot);
        }
    );

    for(const auto& e : elements)
        std::cout << e << ' ';
    std::cout << '\n';
}

Please notice the option not to provide anything and rely on existing tools.