c++ - 为什么这个简单的元组自定义比较器即使在严格弱排序的情况下也会崩溃？

Question

这个简单的自定义比较器类型 tuple<int, int, int>下面的示例测试崩溃。我检查了cout cmp 中的声明每次调用 cmp 的比较器得到一个返回值，所以它不像元组 t1 和 t2 中的值是垃圾。
知道为什么这会崩溃吗？这个非常简单的自定义比较器有什么问题吗？

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

Answer 1

您的 cmp operator()没有严格的弱排序。例如您需要检查 d1 == d2比较前w1 < w2等等。这违反了 std::sort 的要求。它调用未定义的行为。这可能导致崩溃。
一个正确的简单实现是:

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

就目前而言，这个自定义比较器不需要实现，因为它使用 std::tuple 的默认排序。 , std::sort 可以使用.
从 c++17 开始，您可以使用结构化绑定(bind)稍微清理一下:

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