Why does this simple custom-comparator of tuples crash even with strict-weak ordering?

Question

This simple custom-comparator for type tuple<int, int, int> crashes for the example test below. I checked with the cout statements in the cmp comparator that each call to cmp gets a return value, so it's not like the values in the tuples t1 and t2 are junk.

Any idea why this is crashing? Is there anything wrong with this very simple custom-comparator?

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& ws, vector<vector<int>>& bs) {
        int n = ws.size(), m = bs.size();        
        vector<tuple<int, int, int>> dist;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int d = abs(ws[i][0]-bs[j][0]) + abs(ws[i][1]-bs[j][1]);
                dist.push_back(make_tuple(d, i, j)); 
            }
        }     
        sort(dist.begin(), dist.end(), cmp());
    }
    
    struct cmp {
         bool operator() (tuple<int, int, int>& t1, tuple<int, int, int>& t2) {
            int d1 = get<0>(t1), d2 = get<0>(t2), w1 = get<1>(t1), w2 = get<1>(t2), b1 = get<2>(t1), b2 = get<2>(t2);
            cout << d1 << " " << w1 << " " << b1 << " " << d2 << " " << w2 << " " << b2 ;
            bool ret = false;
            if (d1 < d2) ret = true;
            else if (w1 < w2) ret = true;
            else if (b1 < b2) ret = true;
            cout << " " << ret  << " " << endl;
            return ret;
        }
    };
};

int main() {
   Solution s;
   vector<vector<int>> ws = {{0,0},{1,0},{2,0},{3,0},{6,0}};
   vector<vector<int>> bs = {{0,999},{1,999},{2,999},{3,0},{6,0}};
   s.assignBikes(ws, bs);
}

Your `assignBikes` has undefined behavior for two reasons: One is given by the answers concerning the sorting error. The other reason that a crash may occur is that you did not return anything from `Solution::assignBikes` when you are supposed to return a `std::vector`. Your compiler should have warned you that you were not returning a value from that function. — PaulMcKenzie, Sep 09 '20 at 20:53

cigien · Accepted Answer · 2020-09-09T19:51:13.063

6

Your cmp operator() does not have a strict weak ordering. e.g. you need to check if d1 == d2 before comparing w1 < w2 and so on. This violates the requirements of std::sort which invokes undefined behavior. This could lead to a crash.

A simple implementation that is correct would be:

bool operator() (std::tuple<int, int, int> const & t1, std::tuple<int, int, int> const & t2) {
    int d1 = std::get<0>(t1), d2 = std::get<0>(t2), w1 = std::get<1>(t1), w2 = std::get<1>(t2), b1 = std::get<2>(t1), b2 = std::get<2>(t2);
    return std::tie(d1, w1, b1) < std::tie(d2, w2, b2);     
}

As it stands, this custom comparator doesn't need to be implemented, since it's using the default ordering for std::tuple, which can be used by std::sort.

From c++17, you can clean this up a little with structured bindings:

bool operator() (std::tuple<int, int, int> const & t1, std::tuple<int, int, int> const & t2) {
    auto [d1, w1, b1] = t1;
    auto [d2, w2, b2] = t2;
    return std::tie(d1, w1, b1) < std::tie(d2, w2, b2);     
}

edited Sep 09 '20 at 19:51

answered Sep 09 '20 at 19:42

cigien

57,834
11
73
112

Good solution; perhaps not the easiest to read, in its current form. – Asteroids With Wings Sep 09 '20 at 19:44
@AsteroidsWithWings True, cleaned it up a little. – cigien Sep 09 '20 at 19:48
How are your comparators different from `t1 < t2`? Am I missing something? – john Sep 09 '20 at 19:48
1

Oh, much better. And better than my suggested improvement lol – Asteroids With Wings Sep 09 '20 at 19:49
Recommend adding `const` to the parameter types, and standardising on `std::` or not-`std::`. – Asteroids With Wings Sep 09 '20 at 19:49
@john It isn't. We assume the OP will change the ordering. If not, fair enough they don't need the comparator, but that's not what was being asked about. – Asteroids With Wings Sep 09 '20 at 19:50
@john Clarified that it's not necessary with this ordering. – cigien Sep 09 '20 at 19:52
1

ah, didn't realize it wasn't strictly weak-ordered. Is there a stadardized way of making sure that for a complex type one writes a comparator with strict-weak ordering always _correctly and easily_ when the utils like the above in your code are not available? – Joe Black Sep 09 '20 at 20:10
does `tie` not allow directly using tuple as argument like `return std::tie(t1) < std::tie(t2);`. if it doesn't, any reason why not? – Joe Black Sep 09 '20 at 20:11
1

`std::tie` is available from c++11. And yes, you can tie tuples, but all that gives you back is a tuple, which you can compare directly anyway. – cigien Sep 09 '20 at 20:12
@Joe: _"Is there a stadardized way of making sure that"_ Nope (the compiler couldn't prove it in general anyway) - but `std::tie` can help (as long as you're after a lexicographic ordering!). Try to compose built-in comparators where you can, to avoid mistakes – Asteroids With Wings Sep 09 '20 at 21:05

john · Answer 2 · 2020-09-09T19:45:39.557

3

Your custom comparator does not have strict weak ordering. E.g. if t1 = {1, 2, 0}, and t2 = {2, 1, 0} then cmp(t1,t2) and cmp(t2, t1) are both true which violates strict weak ordering.

Since you already have tuples why not just

bool operator() (const tuple<int, int, int>& t1, const tuple<int, int, int>& t2) {
    return t1 < t2;     
}

Or even simpler just omit the comparator altogether, since the default for std::sort does what you (presumably) want already.

edited Sep 09 '20 at 19:45

answered Sep 09 '20 at 19:44

john

85,011
4
57
81

1

One assumes there is a good reason for the custom comparator, even though a divergent ordering has not been shown in the question (bug notwithstanding). So the suggestions here may have been better suited as part of a request-for-clarification comment... – Asteroids With Wings Sep 09 '20 at 19:45
Ah, I thought i had satisfied the strict-weak ordering requirement by making sure for a given t1 and t2, the comparator gives me an answer. Didn't realize that answer for (t1, t2) should be inverse of answer for (t2, t1). Is there a stadardized way of making sure that for a complex type one writes a comparator with strict-weak ordering always _correctly and easily_? – Joe Black Sep 09 '20 at 20:05
@john `return t1 < t2;` this alone wouldn't work in what i want the comparator to do. I needed to sort them so that lower `d` is picked first, if `d` is same lower `w` is picked first, if `w` same lower `b` is picked first. – Joe Black Sep 09 '20 at 20:09
@JoeBlack "*if `d` is same ... if `w` same ...*" - that is the part your comparator is missing. You are not checking for equality on any of the tuple values. Without `std::tie`, you would need something more like this: `bool ret = false; if (d1 < d2) { ret = true; } else if (d1 == d2) { if (w1 < w2) { ret = true; } else if (w1 == w2) { if (b1 < b2) { ret = true; } } } ... return ret;` – Remy Lebeau Sep 09 '20 at 20:23
I guess you can always write unit tests for your comparator, based on the requirements documented [here](https://en.cppreference.com/w/cpp/named_req/Compare). Not perhaps always necessary, but it's certainly an easy way to narrow down or rule out a bug. – Useless Sep 09 '20 at 20:51
@JoeBlack I'm sorry but that's exactly what `t1 < t2` would do. – john Sep 10 '20 at 06:40

Remy Lebeau · Answer 3 · 2020-09-09T20:42:33.273

Your operator is not actually implementing strict weak ordering correctly, so your call to std::sort() has undefined behavior.

You said in comments:

I needed to sort them so that lower d is picked first, if d is same lower w is picked first, if w same lower b is picked first.

But your comparator is missing any checks for equality on those tuple values.

Since d is the 1st tuple element, w is the 2nd tuple element, and b is the 3rd tuple element, then the simplest solution would be to NOT compare the tuple elements manually at all, just compare the tuple themselves as-is. The default std::tuple::operator< will perform the correct comparison for strict weak ordering, as you wanted:

Compares lhs and rhs lexicographically by operator<, that is, compares the first elements, if they are equivalent, compares the second elements, if those are equivalent, compares the third elements, and so on.

For non-empty tuples, (3) is equivalent to
if (std::get<0>(lhs) < std::get<0>(rhs)) return true;
if (std::get<0>(rhs) < std::get<0>(lhs)) return false;
if (std::get<1>(lhs) < std::get<1>(rhs)) return true;
if (std::get<1>(rhs) < std::get<1>(lhs)) return false;
...
return std::get<N - 1>(lhs) < std::get<N - 1>(rhs);

Thus, you can do:

bool ret = t1 < t2;

It makes sense to compare the tuple elements manually only when you want to comparing the elements in a different order, which is not what your example is showing.

If you did want to compare tuple elements manually, you should use std::tie and let it handle the comparisons for you, eg:

bool ret = std::tie(d1, w1, b1) < std::tie(d2, w2, b2);

However, if you don't want to (or can't) use std::tie(), then you would need something more like this:

bool ret = false;
if (d1 < d2) {
    ret = true;
}
else if (d1 == d2) { // <-- add this!
    if (w1 < w2) {
        ret = true;
    }
    else if (w1 == w2) { // <-- add this!
        if (b1 < b2) {
            ret = true;
        }
    }
}

Why does this simple custom-comparator of tuples crash even with strict-weak ordering?

3 Answers3