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.
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".