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;
}
};
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]);
}
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With