1

この単純な型のカスタム コンパレータはtuple<int, int, int>、以下のテスト例でクラッシュします。各呼び出しが戻り値を取得するコンパレーターのcoutステートメントで確認したので、タプル t1 と t2 の値がジャンクではないようです。cmpcmp

なぜこれがクラッシュしているのか分かりますか？この非常に単純なカスタム コンパレータに問題はありますか?

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) は両方とも true であり、厳密な弱い順序付けに違反します。

あなたはすでにタプルを持っているので、なぜ

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

std::sortまたは、デフォルトの forが（おそらく）すでに望んでいることを行うため、コンパレーターを完全に省略するだけです。

于 2020-09-09T19:44:08.480 に答える