标准排序有时会抛出序列错误

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要求比较函数是“严格弱排序”，这要求：

它是反身性的：对于所有的x，r(x, x)都是假的；

您的比较函数不符合此要求，因为正如 Mark Ransom 在评论中指出的那样，您true在 时返回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<字典顺序进行比较的内置函数。