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

Question

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

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

例如，有集合的向量，如果集合 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），因为这种比较器“放松”。