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

Question

对于下面的示例测试，tuple<int, int, int> 类型的这个简单的自定义比较器会崩溃。我检查了 cmp 比较器中的 cout 语句，每次调用 cmp 都会得到一个 return 值，所以它不像元组 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() 没有严格的弱排序。例如在比较 w1 < w2 等之前，您需要检查是否 d1 == d2 。这违反了调用未定义行为的 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 开始，您可以使用结构化绑定稍微清理一下：

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

Answer 2

您的自定义比较器没有严格的弱排序。例如。如果 t1 = {1, 2, 0}，并且 t2 = {2, 1, 0} 那么 cmp(t1,t2) 和 cmp(t2, t1) 都为真，这违反了严格的弱排序。

既然你已经有了元组，为什么不直接

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

或者更简单的只是完全省略比较器，因为 std::sort 的默认值已经做了你（大概）想要的。

Answer 3

您的 operator 实际上并未正确实施严格的弱排序，因此您对 std::sort() 的调用具有 未定义的行为.

您在评论中说：

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.

但是您的比较器缺少对这些元组值的 相等性 的任何检查。

因为 d 是第一个元组元素，w 是第二个元组元素，b 是第三个元组元素，那么最简单的解决方案是不比较完全手动元组元素，只需比较元组本身 as-is。默认 std::tuple::operator< 将根据您的需要对严格的弱排序执行正确的比较：

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

因此，您可以这样做：

bool ret = t1 < t2;

手动比较元组元素是有意义的只有当你想以不同的顺序比较元素时，这不是你的例子所显示的。

如果您确实想手动比较元组元素，您应该使用 std::tie 并让它为您处理比较，例如：

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

但是，如果您不想（或不能）使用 std::tie()，那么您可能需要更像这样的东西：

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?

c++

sorting

std

comparator

custom-compare