Custom sort based on 3 objects

Question

I would like to sort a 2D array based on the similarity between elements compared to the element at index 0.

How is a custom sort function defined that can use the external 3rd object, the element at index 0?

The compare function needs to do the following

bool compare(float *a, float *b) {
    float *source = 2DArray[0];
    return distance(source, a) > distance(source, b);
}

when calling it

std::sort(std::begin(2DArray), std::end(2DArray), compare);

there is obviously no access to 2DArray.

How can this be written so that an object can call a function to call the sort function and give access to the 2DArray[0]?

`2DArray` is not a valid C++ identifier. Make sure that your code compiles before posting (by the way, what is the type of `2DArray`?) — user202729, Jul 28 '18 at 09:41
Use a [lambda expression](http://en.cppreference.com/w/cpp/language/lambda) instead of a function? — Some programmer dude, Jul 28 '18 at 09:42
@user202729 The question does *not* specify a C++ standard version, so the assumption is "current version", which currently is C++17. So, lambdas are very much something that can be assumed to be available. — Jesper Juhl, Jul 28 '18 at 10:00
@jarryd Don't post pseudo code. Post *really*, compilable code. — Jesper Juhl, Jul 28 '18 at 10:10

πάντα ῥεῖ · Answer 1 · 2018-07-28T10:04:00.653

1

The simplest way to do that should be to create a Comparer class like this:

struct Comparer {
    float *source;
    bool operator()(const float* a, const float* b) {
        return distance(source, a) > distance(source, b);
    } 
};

create an instance

Comparer compare;
comparer.source = 2DArray;

and pass it to std::sort:

std::sort(std::begin(2DArray), std::end(2DArray), compare);

A lambda function capturing the source pointer would be the more modern way to do that.

It ends up being more or less the same, but captures would be wrapped into an anonymous class generated by the compiler.

edited Jul 28 '18 at 10:04

answered Jul 28 '18 at 09:57

πάντα ῥεῖ

1
13
116
190

1

the remaining problem: you still need a linear traversal order to have a defined "begin" and "end" – skeller Jul 28 '18 at 10:03
@skeller I don't see a problem. `std::begin()` and `std::end()` work well with raw arrays. Everything beyond that is out of question here. – πάντα ῥεῖ Jul 28 '18 at 10:06
yes, but internally this means it is traversed linarly (row by row or column by column) and the resulting 2d structure depends on the internal traversal order. In general in a 2d structure the definition of "next element" is ambiguus. (maybe i am too picky on the details here) – skeller Jul 28 '18 at 10:13
@πάνταῥεῖ - thanks, I solved it with a lambda, much easier. – some_id Jul 28 '18 at 10:17
@jarryd As mentioned that's merely the same, just a little bit syntactic sugar on top. – πάντα ῥεῖ Jul 28 '18 at 10:22

score 1 · Answer 2 · answered Jul 28 '18 at 09:57

So if i understand correctly, you want to sort by distance to a fixed point. This could work, since this metric will give you a "strict weak order" (https://en.wikipedia.org/wiki/Weak_ordering), which is required for any comparison operator to be used for sorting.

However your actual problem is: sorting in general is a 1-dimentional thing as it just gives you a A is smaller than B relationship which you cannot trivially map to 2D. so what you need is a idea on how to linearly order your 2d structure, which depends on what it represents. (then you can have a "begin" and "end")

My advice is: first convert to a 1d-structure, e.g. by just appending all rows of your 2d array, then sort it. after that you can think of how you want to represent them in 2d, if applicable. (Alternatively at least have a defined 1d view on your structure)

If you get into detail what your actual problem is, i might be able to provide a more concrete advice.

Marek R · Accepted Answer · 2018-07-28T10:14:46.353

Assuming you have got some function which can measure "similarity between elements" you can use lambda to adopt this function as predicate for sorting.

#include <iostream>
#include <algorithm>
#include <array>
#include <vector>

int dist2(const std::array<int, 2> &a, const std::array<int, 2> &b) {
    auto dx = a[0] - b[0];
    auto dy = a[1] - b[1];
    return dx * dx + dy * dy;
}

int main() {
    int x, y;
    std::vector<std::array<int, 2>> tab;

    while (std::cin >> x >> y) {
        tab.push_back({ x, y });
    }

    auto origin = tab.front();

    std::sort(std::begin(tab), std::end(tab), 
              [&origin](const auto &a, const auto &b) {
                  return dist2(a, origin) < dist2(b, origin);
              });

    for (const auto &a : tab) {
        std::cout << a[0] << ", " << a[1] << '\n';
    }

    return 0;
}

https://wandbox.org/permlink/5pWL2N5AOHcr20Wi

While this code may answer the question, providing additional context regarding *how* and/or *why* it solves the problem would improve the answer's long-term value. See [this meta post](https://meta.stackoverflow.com/questions/300837). — user202729, Jul 28 '18 at 10:05
yes this is a good rule, but in this case I can't find description which could add value. — Marek R, Jul 28 '18 at 10:11

Custom sort based on 3 objects

3 Answers3