标准排序有时会抛出分段错误

Question

我编写了以下函数，用于对数组向量进行部分稳定排序。当向量的大小像 1G 它总是工作，当向量的大小很大（5 或 6 Gig）时有时它会工作，有时它会抛出分段错误，有人可以帮我找出解决这个问题的方法。

template <typename T, size_t SIZE>
void sort(std::vector<std::array<T, SIZE>>& vec, size_t depth = SIZE) {
        std::sort(vec.begin(), vec.end(),
                  [&](const auto& t1, const auto& t2)->bool {
                        for(size_t s = 0; s < depth; s++) {
                                if(t1[s] == t2[s]) {
                                        continue;
                                }
                                return t1[s] < t2[s];
                        }
                        return true;
                  });
}

我使用 g++ 10.2，这些是开关，我用 -DNDEBUG -march=native -msse3 -ftree-vectorize -O3 编译代码。

Answer 1

std::sort requires that the comparison function be a "strict weak ordering"，需要：

it is irreflexive: for all x, r(x, x) is false;

你的比较函数不符合这个要求，因为，，你returntrue当t1 == t2。您的比较基本上是 <= 而不是 <，并且您需要 <.

最简单的解决方法是使用 std::lexicographical_compare:

template <typename T, size_t SIZE>
void sort(std::vector<std::array<T, SIZE>>& vec, size_t depth = SIZE) {
        std::sort(vec.begin(), vec.end(),
                  [depth](const auto& t1, const auto& t2)->bool {
                        return std::lexicographical_compare(t1.begin(), t1.begin() + depth,
                                                            t2.begin(), t2.begin() + depth);
                  });
}

为了完整起见，请注意，如果您不关心 depth，您可以直接排序，因为 std::array 带有内置的 operator<，可以按字典顺序进行比较。

标准排序有时会抛出分段错误

std sort sometimes throws seqmention fault

c++

std