为什么在自定义比较器时出现空指针错误

Question

我正在尝试在 Leetcode 上解决这个问题：https://leetcode.com/problems/merge-intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Constraints:
intervals[i][0] <= intervals[i][1]

我只是有一个简单的想法：对输入进行排序并进行合并。

这是我的代码：

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;
}

实际上错误来自 std::sort.

行

当我在 Leetcode 上执行代码时，出现错误：

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

但是如果我如下更改比较器：

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];
});

它将按预期工作，没有任何错误。

我不知道为什么。

Answer 1

在你的比较器中，这个比较：

return e1[1] <= e2[1];

不满足被比较元素的严格弱排序。例如如果

e1: {1, 2}
e2: {1, 2}

然后比较e1，而e2将return true，不管比较顺序如何。

违反 std::sort 的这一要求会引发未定义的行为。在这种情况下，UB-sanitizer 已帮助您诊断出问题。

另一方面，这个比较：

return e1[1] < e2[1];

非常好，因为它根据需要建立了 strict-weak-ordering。

Answer 2

看起来不错！快到了！
我们会做一个常规的 std::sort()，然后使用 std::min() 和 std::max()，实际上不必使用比较器：

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto improve_runtime = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();



struct Solution {
    static const std::vector<std::vector<int>> merge(
            std::vector<std::vector<int>>& intervals
    ) {
        std::sort(std::begin(intervals), std::end(intervals));
        std::vector<std::vector<int>> merged;

        if (std::size(intervals) >= 1) {
            merged.emplace_back(intervals[0]);
        }

        for (std::size_t index = 0; index < std::size(intervals); ++index) {
            const std::vector<int> interval = intervals[index];
            const std::vector<int> tail = merged.back();

            if (tail[1] >= interval[0]) {
                merged.pop_back();
                merged.emplace_back(std::vector<int> {
                    std::min(tail[0], interval[0]),
                    std::max(interval[1], tail[1])
                });

            } else {
                merged.emplace_back(interval);
            }
        }

        return merged;
    }

};


// int main() {
//     std::vector<std::vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//     std::vector<std::vector<int>> merged = Solution().merge(intervals);

//     for (auto& interval : merged) {
//         std::cout << "[" << interval[0] << "\t" << interval[1] << "]\n";
//     }
// }

PS:

LeetCode 在 C++17 上运行。
另外请务必始终如一地使用 std::，比赛除外。

这是你的工作算法，不使用比较器：

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>

// The following block might slightly improve the execution time;
// Can be removed;
static const auto improve_runtime = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();


struct Solution {
    std::vector<std::vector<int>> merge(
                                   std::vector<std::vector<int>>& intervals
    ) {
        std::vector<std::vector<int>> res;

        if (intervals.empty()) {
            return res;
        }

        std::sort(intervals.begin(), intervals.end());

        res.push_back(intervals[0]);

        for (std::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;
    }

};


int main() {
    std::vector<std::vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    std::vector<std::vector<int>> merged = Solution().merge(intervals);

    for (auto& interval : merged) {
        std::cout << "[" << interval[0] << "\t" << interval[1] << "]\n";
    }
}

根据 Pete 的建议编辑：

Names that contain two consecutive underscores (optimize) and names that begin with an underscore followed by a capital letter are reserved for use by the implementation. Don't use them in your code.

为什么在自定义比较器时出现空指针错误

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

c++

lambda

comparator

c++11

根据 Pete 的建议编辑：