Line 924: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h)

user_12138054 0
Viewed 24473

I am getting runtime error while running the following code on leetcode. When I am removing the user-defined comparator function it is working fine. But with user define comparator function it is giving runtime error as follows :

Line 924: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:933:9

class Solution {
private:
    static bool comp (vector<int> p1, vector<int> p2) {
        if(p1[0] < p2[0] || p1[1] < p2[1])
            return true;
        else
            return false;
    }
    
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty())
            return 0;
        sort(envelopes.begin(), envelopes.end(), comp);
        vector<int> dp(envelopes.size(), 1);
        int res = 0;
        
        for (int i = 0; i < envelopes.size(); i++) {
            for (int j = i-1; j >=0; j--) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1] && dp[j] + 1 > dp[i])
                    dp[i] = 1 + dp[j];
            }
            res = max(res, dp[i]);
        }
        
        return res;
    }
};
c++
2 Answers

It's a classic mistake. Consider this pair of vectors

p1 = {1, 4} and p2 = {2, 3}

Now comp(p1, p2) is true because 1 < 2 but comp(p2, p1) is also true because 3 < 4. So how is sorting supposed to work when p1 is less than p2 and p2 is less than p1?

You need to write a comparison function that makes sense. Perhaps something like this

static bool comp (vector<int> p1, vector<int> p2) {
    return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
user_8820030

As was pointed out in the answer given by @john, your comparison function needs to follow a strict-weak-order.

A layman's explanation is your comparison functions states that a comes before b in the ordering, but at the same time b comes before a in the ordering. That is a violation of the strict-weak-order, and thus the std::sort gets confused and goes into undefined-behavior land.

The answer given by @john should work, however there is a simple, almost foolproof way of doing the comparison. The simple way of comparing multiple items, where the comparison will cascade down from one item to the next, is to use std::tie.

For example you want to compare a, b, of two items, where if the a values are equal, then compare the b values (in your case, the a value is p1[0] and p2[0], and the b values are p1[1] and p2[1]:

static bool comp (const vector<int>& p1, const vector<int>& p2) {
    return std::tie(p1[0], p1[1]) < std::tie(p2[0], p2[1]);
}

This will automatically compare p1[0] to p2[0], and if they are equal p1[1] to p2[1]. If you had more items to compare, you just specify them in the std::tie calls.

user_31333160
Related