1

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

3 回答 3

6

您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 开始，您可以使用结构化绑定稍微清理一下：

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);     
}
于 2020-09-09T19:42:42.703 回答
3

您的自定义比较器没有严格的弱排序。例如，如果 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;     
}

或者甚至更简单，只是完全省略比较器，因为默认值 forstd::sort可以满足您（大概）已经想要的功能。

于 2020-09-09T19:44:08.480 回答
1

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

你在评论中说：

我需要对它们进行排序，以便d首先选择较低的值，如果相同的较低值首先选择，如果相同的较低值d首先选择。wwb

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

由于d是第一个元组元素，w是第二个元组元素，并且b是第三个元组元素，那么最简单的解决方案是根本不手动比较元组元素，只需按原样比较元组本身。默认值std::tuple::operator<将按照您的需要对严格的弱排序执行正确的比较：

按字典顺序比较lhs，即比较第一个元素，如果它们等价，则比较第二个元素，如果它们等价，则比较第三个元素，依此类推。rhsoperator<

对于非空元组，(3) 等价于

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;
        }
    }
}
于 2020-09-09T20:33:15.797 回答