c++ - 不严格弱排序比较器的 std::sort 可以用作拓扑排序吗？

Question

我知道我应该严格遵守 C++ 比较器的弱排序。主要原因是 !(a > b) && !(b > a) 应该充当等价运算符。

但问题只是在不需要等价运算符的地方排序，不像 std::set。

例如，有一个集合 vector ，如果集合A是集合B的真子集，那么经过排序后，集合A的索引应该小于集合B的索引。

所以假设你这样写比较器

bool comparator(vector<int> &A, vector<int> &B) const {
    // if A is proper subset of B, return true
    // otherwise, return false
}

那么使用这个比较器的 std::sort 是否总是像拓扑排序一样工作？

加上)

感谢 Oliver Charlesworth 提供的缺失信息。

我真的很想知道这样的比较器可以像拓扑排序一样与快速排序或插入排序(一些著名的基于比较的排序算法)一起工作。

Answer 1

不，它很可能不起作用。 std::sort 合约需要一个严格的弱排序比较器；违反它会导致未定义的行为。顺便说一句，我已经多次看到 libstdc++ std::sort 因这种比较器“放松”而残酷地崩溃(读取容器外的元素，IIRC)。