CODEWITHSUNDEEP
c++sortingstdcomparatorcustom-compare
Joe Black
Joe Black

Reputation: 653

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

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);
}

Upvotes: 1

Views: 183

Answers (3)

Remy Lebeau
Remy Lebeau

Reputation: 597111

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;
        }
    }
}

Upvotes: 1

cigien
cigien

Reputation: 60238

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);     
}

Upvotes: 7

john
john

Reputation: 87952

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.

Upvotes: 3

Related Questions