c++sortingstdcomparatorcustom-compare

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

Solution

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