c++sortingstrict-weak-ordering

could std::sort with not strict weak ordering comparator work as topological sorting?


I do know that I should follow strict weak ordering for c++ comparator. And the main reason is that !(a > b) && !(b > a) should act as equivalence operator.

But the problem is only sorting where you don't need equivalence operator not like std::set.

For example, there is vector of sets and if set A is proper subset of B, then after sorting, index of set A should be smaller than index of set B.

So assume that you write comparator like this

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

Then does std::sort with this comparator always work like topological sorting?

plus)

thanks for Oliver Charlesworth for missing information.

I really want to know that such comparator works with like quick sort or insertion sort (some famous comparison-based sorting algorithms) as topological sort.


Solution

  • No, it is likely not to work. std::sort contract requires a strict weak ordering comparator; violating it results in undefined behavior. BTW, I've seen several times libstdc++ std::sort brutally crash (reading elements outside the container, IIRC) for this kind of comparator "relaxing".