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.

  • I am afraid you are overcomplicating things. With a proper comparator, std::partial_sort does exactly what you need. And I don't think it is a great burden for the caller to make an alterable copy prior to the call. – vnp Apr 29 '14 at 18:15
up vote 6 down vote accepted

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.

  • Clever, I feel ashamed that I looked quickly at nth_element but did not see the use for it. One thing to say, we drop the modularity of the comparator here. Not that it would be incredibly useful though (well idk, but I wanted to achieve it while writing my function). – teh internets is made of catz Apr 30 '14 at 21:10
  • If you want the modularity of the comparator, then I would suggest to drop dependence on dist and point q as well. Then you have a new and more generic function that is actually just nth_element followed by sort. You could name this nth_sorted and have find_n_nearest call that one after constructing compare, which encapsulates q and dist. This way you are just splitting find_n_nearest into two steps. I think that's much cleaner. – iavr Apr 30 '14 at 21:38

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.

  • 1
    If I started from some code and it ended up four times longer for the same functionality, I would ask myself if something has gone wrong. Plus, why is everything moved and not forwarded? – iavr Apr 30 '14 at 20:19
  • @iavr Any advice on when to use rvalue references for template parameters ? If I refer to the standard lib's algorithms, they never use them. – teh internets is made of catz Apr 30 '14 at 21:14
  • @tehinternetsismadeofcatz (you mean function parameters?) Depends on expected input and algorithm. Iterators typically contain just a pointer, and function objects are empty; in both cases it's better to pass by value, so this is common in STL. Typically iterators need to be copied, so pass-by value is the only option. Function objects may be non-empty (like a compare containing a data point) or have mutable state. In such cases, the most generic option is rvalue (universal) references that are std::forwarded unless used more than once (in which case std::forward only on last use). – iavr Apr 30 '14 at 22:02
  • @iavr I meant function parameters that depend on a template, like for example Distance&& distance in Dieter's answer. In fact I was wondering if the compiler can deduce that the Distance type passed is a (rvalue) reference or not. But I bet it's clearer to specify it with && in the function parameters anyway. I think I'll have a deeper read on type deduction for templates. – teh internets is made of catz May 1 '14 at 9:47
  • @tehinternetsismadeofcatz With && it's not just clearer: skipping && means "pass-by-value". You can check universal references and pages 7-8 of perfect forwarding. – iavr May 1 '14 at 10:06

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.

  • So I was heading in the right direction, thanks :) – teh internets is made of catz Apr 30 '14 at 20:57
  • @tehinternetsismadeofcatz Probably. But look at iavr's answer. They tend to give incredibly good advice :) – Morwenn Apr 30 '14 at 21:06
  • Yeah I'm reading through all of your answers ! – teh internets is made of catz Apr 30 '14 at 21:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.