第924行，第9个字符：运行时错误：引用绑定到空指针类型为'int'的指针（stl_vector.h）

Question

在Leetcode上运行以下代码时，我遇到了运行时错误。当我删除用户定义的比较函数时，它可以正常工作。但使用用户定义的比较函数时，会出现以下运行时错误： “在第924行，第9个字符处：运行时错误：引用绑定到空指针类型为'int'的指针(stl_vector.h)总结：UndefinedBehaviorSanitizer: 未定义行为 /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;
    }
};

- heapster

---

我在363天前点赞了这个答案，结果又回到了这里！ - Akshat Shah

Answer 1

这是一个经典的错误。考虑这对向量

p1 = {1, 4} 而且 p2 = {2, 3}

现在 comp(p1, p2) 是 true，因为 1 小于 2，但 comp(p2, p1) 也是 true, 因为 3 小于 4。那么当 p1 小于 p2 并且 p2 小于 p1 时，排序应该如何工作呢？

您需要编写一个看起来合理的比较函数。也许像这样

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

- john

---

你的回答如何针对运行时错误？我理解OP问题中存在逻辑错误，但是你的回答没有解决由代码检查器发现的未定义行为。 - Radu C

Answer 2

实际的消毒剂错误与比较器的逻辑无关。它实际上是在一个向量为空时触发，并且您尝试对该向量中的元素进行解引用时触发。 您已经检查了envelopes不为空，但在稍后的代码中，您继续使用envelopes[i][0]而没有检查envelopes[i]是否实际上有任何元素。

- Radu C

---

尽管其他答案有助于修复未来的错误，但只有这个答案解决了问题，即运行时错误（这也是我一直在寻找的答案）。 - undefined

Answer 3

正如 @john 给出的答案所指出的那样，您的比较函数需要遵循严格弱序。

一个外行人的解释是，您的比较函数说明了在排序中 a 在 b 之前，但同时 b 在 a 之前。这是严格弱序的违规行为，因此 std::sort 会混淆并进入未定义的行为领域。

@john 给出的答案应该可以解决问题，不过有一种简单、几乎万无一失的方法来进行比较。比较多个项目的简单方法，其中比较将从一个项目级联到下一个项目，就是使用 std::tie。

例如，您想比较两个项目的a、b，如果a的值相等，则比较b的值（在您的情况下，a值是p1[0]和p2[0]，而b值是p1[1]和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]);
}

这将自动比较 p1[0] 和 p2[0]，如果它们相等，则比较 p1[1] 和 p2[1]。如果您有更多要比较的项目，只需在 std::tie 调用中指定它们即可。

- PaulMcKenzie