mercredi 11 novembre 2020

Why did I get an error about null pointer while customizing a comparator

I'm trying to solve this problem on Leetcode: https://leetcode.com/problems/merge-intervals

I simply got a simple idea: sort the input and do the merge.

Here is my code:

vector<vector<int>> merge(vector<vector<int>> &intervals)
{
    vector<vector<int>> res;
    if (intervals.empty()) {
        return res;
    }
    std::sort(intervals.begin(), intervals.end(), [](const vector<int> e1, const vector<int> e2) {
        if (e1[0] == e2[0]) {
            return e1[1] <= e2[1];     // ERROR!!!
        }
        return e1[0] < e2[0];
    });
    res.push_back(intervals[0]);
    for (size_t i = 1; i < intervals.size(); i++) {
        if (res.back()[1] >= intervals[i][0]) {
            if (res.back()[1] <= intervals[i][1]) {
                res.back()[1] = intervals[i][1];
            }
        } else {
            res.push_back(intervals[i]);
        }

    }
    return res;
}

In fact the error comes from the line of std::sort.

When I execute the code on Leetcode, I get an error:

Line 1052: Char 9: runtime error: reference binding to null pointer of type 'const __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' (aka 'const int') (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1061:9

But If I change the comparator as below:

std::sort(intervals.begin(), intervals.end(), [](const vector<int> e1, const vector<int> e2) {
    if (e1[0] == e2[0]) {
        return e1[1] < e2[1];    // change <= into <
    }
    return e1[0] < e2[0];
});

It will work as expected without any error.

I don't know why.

Aucun commentaire:

Enregistrer un commentaire